1.1 Definition und Beispiele

Definition 1.1

Eine Folge von Zufallsgrößen $(X_{n})_{n\in \mathbb {N} }$ über Fehler beim Parsen (Syntaxfehler): {\displaystyle (\Omega, \mathcal F, P)} mit abzählbarem Zustandsraum

Fehler beim Parsen (Syntaxfehler): {\displaystyle I := \bigcup_{n\in\N} X_n(\Omega)}

(o. B. d. A. gelte $I\subseteq \mathbb {Z}$ ) heißt Markov-Kette in diskreter Zeit, falls für alle $n\in \mathbb {N} _{0}$ , $i_{0},\ldots ,i_{n+1}\in I$ mit $P(X_{n}=i_{n},\ldots ,X_{0}=i_{0})>0$ gilt:

P(X_{n+1}=i_{n+1}|X_{n}=i_{n},\ldots ,X_{0}=i_{0})=P(X_{n+1}=i_{n+1}|X_{n}=i_{n})=:p_{i_{n},i_{n+1}}^{(n,n+1)}.

Die Markov-Kette heißt homogen, falls $p_{i,j}:=p_{i,j}^{(n,n+1)}$ unabhängig von $n$ ist.

Die $p_{i,j}^{(n,n+1)}$ heißen 1-Schritt-Übergangswahrscheinlichkeiten.

$P^{(n,n+1)}:=(p_{i,j}^{(n,n+1)})_{i,j\in I}$ heißt Matrix der 1-Schritt-Übergangswahrscheinlichkeiten.

Anmerkung 1.2

$(p_{i,j})_{i,j\in I}$ ist eine stochastische Matrix, d. h.:

p_{i,j}\geq 0

für alle

i,j\in I

und

\sum _{j\in I}p_{i,j}=1

für alle

i\in I

.

Beispiel 1.1

Ein Spieler gewinnt 1 € mit Wk. $p$ und verliert 1 € mit Wk. $q=1-p$ . Er spielt, bis er entweder 0 oder $M$ € hat. Die Spiele seien unabhängig. $X_{0}\in \{0,\ldots ,M\}$ sei gegeben. $X_{n}$ - zufälliges Vermögen nach $n$ Spielen. $(X_{n})_{n\geq 0}$ ist eine homogene Markovkette mit folgender Matrix der 1-Schritt-Übergangswahrscheinlichkeiten:

P={\begin{pmatrix}p_{0,0}&p_{0,1}&\ldots &p_{0,M}\\p_{1,0}&p_{1,1}&\ddots &\vdots \\\vdots &\ddots &\ddots &p_{M-1,M}\\p_{M,0}&\ldots &p_{M,M-1}&p_{M,M}\end{pmatrix}}={\begin{pmatrix}1&0&0&0&\ldots &0\\q&0&p&0&\ldots &0\\0&q&0&p&\ddots &\vdots \\0&0&\ddots &\ddots &\ddots &0\\\vdots &\vdots &\ddots &q&0&p\\0&0&\ldots &0&0&1\end{pmatrix}}.

Satz 1.3

Sei $(X_{n})_{n\in \mathbb {N} }$ eine homogene Markov-Kette. Die Verteilung von $(X_{n})_{n\in \mathbb {N} }$ ist eindeutig festgelegt durch ihre Matrix $P:=(p_{i,j})_{i,j\in I}$ der Übergangswahrscheinlichkeiten und die Anfangsverteilung von $X_{0}$ . Mit $p_{k}:=P(X_{0}=k)$ gilt:

P(X_{0}=i_{0},\ldots ,X_{n}=i_{n})=p_{i_{0}}\cdot p_{i_{0},i_{1}}\cdots p_{i_{n-1},i_{n}}.

Satz 1.4

Sei $(X_{n})_{n\in \mathbb {N} }$ eine Markov-Kette, $i,j\in I,k<m<n$ . Dann gilt die Chapman-Kolmogoroff-Gleichung:

P(X_{n}=j|X_{k}=i)=\sum _{l\in I}P(X_{m}=l|X_{k}=i)\cdot P(X_{n}=j|X_{m}=l)

oder kurz:

p_{i,j}^{k,n}=\sum _{l\in I}p_{i,l}^{k,m}p_{l,j}^{m,n}.

Sei nun $(X_{n})_{n\in \mathbb {N} }$ eine homogene Markov-Kette. Es gilt also: $p_{i,j}^{k,k+m}=p_{i,j}^{(m)}$ (die $m$ -Schritt-Übergangswahrscheinlichkeiten sind unabhängig von $k$ ).

Satz 1.5

Mit $P:=(p_{i,j})_{i,j\in I}$ gilt:

$\left(p_{i,j}^{(m)}\right)_{i,j\in I}=P^{m}$ ( $m$ -faches Matrix-Produkt).

Satz 1.6

$(X_{n})_{n\in \mathbb {N} }$ homogene Markov-Kette, $p_{k}=P(X_{0}=k)$ . Dann gilt:

P(X_{n}=k)=\sum _{l\in I}p_{l}\cdot p_{l,k}^{(n)}.

Beispiel 1.2 (Summe unabhängiger Zufallsgrößen)

Seien $X_{0},Y_{1},Y_{2},\ldots ,Y_{n}$ unabhängige Zufallsgrößen auf $(\Omega ,{\mathcal {F}},P)$ mit Werten in $\mathbb {Z}$ . Sei $X_{n}:=X_{0}+Y_{1}+\ldots +Y_{n}.\Rightarrow Y_{k}=X_{k}-X_{k-1}.$

$(X_{n})_{n\in \mathbb {N} }$ ist Markov-Kette, denn:

P(X_{n+1}=i_{n+1}|X_{n}=i_{n},\ldots ,X_{0}=i_{0})

(1.1)

={\frac {P(X_{n+1}=i_{n+1},\ldots ,X_{0}=i_{0})}{P(X_{n}=i_{n},\ldots ,X_{0}=i_{0})}}

(1.2)

={\frac {P(X_{0}=i_{0},Y_{1}=i_{1}-i_{0},Y_{n+1}=i_{n+1}-i_{n})}{P(X_{0}=i_{0},Y_{1}=i_{1}-i_{0},Y_{n}=i_{n}-i_{n-1})}}

(1.3)

=P(Y_{n+1}=i_{n+1}-i_{n})

(1.4)

=P(X_{n+1}=i_{n+1}|X_{n}=i_{n}).

Die Markov-Kette ist homogen $\Leftrightarrow (Y_{n})$ i. i. d.

Beispiel 1.3 (Irrfahrt)

Spezialfall für Summe unabhängiger Zufallsgrößen mit $(Y_{n})$ i. i. d., $P(Y_{n}=1)=p,P(Y_{n}=-1)=q=1-p,X_{0}\in \mathbb {Z}$ . Dann gilt:

P={\begin{pmatrix}\ddots &&&&&&0\\&q&0&p&&&\\&&q&0&p&&\\&&&q&0&p&\\0&&&&&&\ddots \end{pmatrix}}.

Beispiel 1.4 (Irrfahrt mit absorbierenden Rändern)

$X_{0}\in \{0,\ldots ,M\}.$

P={\begin{pmatrix}1&0&&&&&0\\q&0&p&&&&\\&q&0&p&&&\\&&&\ddots &&&\\&&&q&0&p&\\&&&&q&0&p\\0&&&&&0&1\end{pmatrix}}.

1.2 Klassifikation der Zustände

$(X_{n})_{n\in \mathbb {N} }$ homogene Markov-Kette. $i,j\in I$ .

Definition 1.7

Ein Zustand $j$ heißt aus $i$ erreichbar $(i\rightsquigarrow j)$ , falls $\exists n\in \mathbb {N} _{0}$ mit $p_{i,j}^{(n)}>0$ . Die Zustände $i$ und $j$ heißen verbunden $(i\leftrightsquigarrow j)$ , falls $i\rightsquigarrow j$ und $j\rightsquigarrow i$ .

Satz 1.8

" $\leftrightsquigarrow$ " ist eine Äquivalenzrelation. Mit $I(j):=\{i\in I|i\leftrightsquigarrow j\}$ gilt also:

I(i)=I(j)\Leftrightarrow i\leftrightsquigarrow j.

Definition 1.9

d(i):={\begin{cases}0,&falls\ p_{i,i}^{n}=0\forall n\in \mathbb {N} \\\gcd\{n\in \mathbb {N} |p_{i,i}^{n}>0\},&sonst\end{cases}}

heißt die Periode von

i

. Die Markov-Kette heißt aperiodisch, falls $d(i)=1$ für alle $i\in I$ .

Satz 1.10

Es gilt:

a) $i\leftrightsquigarrow j\Rightarrow d(i)=d(j).$

b) Für alle $i\in I$ existiert ein $n_{i}\in \mathbb {N}$ , so dass $p_{i,i}^{nd(i)}>0$ für alle $n\geq n_{i}$ .

c) Sei $p_{i,j}^{m}>0$ für ein $m\in \mathbb {N}$ . Dann gilt:

$\exists n_{j}\in \mathbb {N} :p_{i,j}^{nd(j)+m}>0$ für alle $n\geq n_{i}$ .

Definition 1.11

Ein Zustand $i$ heißt absorbierend, falls $p_{i,i}=1$ .

Beispiel 1.5 (Irrfahrt mit absorbierendem Rand)

$d(0)=d(M)=1$ und $d(1)=\ldots =d(M-1)=2$ .

1.3 Rekurrenz und Transienz

Bezeichne $\tau _{i,j}$ den Zeitpunkt des 1. Erreichens von $j$ , startend in $i$ . Also:

P(\tau _{i,j}=n):=\rho _{i,j}^{n}:=P(X_{n}=j,X_{n-1}\neq j,\ldots ,X_{1}\neq j|X_{0}=i)

={\frac {1}{p_{i}}}P(X_{n}=j,X_{n-1}\neq j,\ldots ,X_{1}\neq j,X_{0}=i)

={\frac {1}{p_{i}}}\sum _{i_{1},\ldots ,i_{n-1}\in I\setminus \{j\}}P(X_{n}=j,X_{n-1}=i_{n-1},\ldots ,X_{1}=i_{1},X_{0}=i)

={\frac {1}{p_{i}}}\sum _{i_{1},\ldots ,i_{n-1}\in I\setminus \{j\}}P(X_{n}=j,X_{n-1}=i_{n-1},\ldots ,X_{1}=i_{1}|X_{0}=i)p_{i}=\sum _{i_{1},\ldots ,i_{n-1}\in I\setminus \{j\}}p_{i,i_{1}}p_{i_{1},i_{2}}\cdots p_{i_{n-1},j}.

Weiter sei

\rho _{i,j}:=P(\tau _{i,j}<\infty )=\sum _{n\in \mathbb {N} }\rho _{i,j}^{n}

die Wahrscheinlichkeit, dass nach endlicher Zeit $j$ erreicht wird, startend in $i$ .

Definition 1.12

Ein Zustand $i$ heißt rekurrent, falls $\rho _{i,i}=1$ , transient, falls $\rho _{i,i}<1$ . Ein rekurrenter Zustand $i$ heißt positiv-rekurrent, falls

\mathbb {E} \tau _{i,i}=\sum _{n\in \mathbb {N} }n\rho _{i,i}^{n}<\infty

und null-rekurrent, falls $\mathbb {E} \tau _{i,i}=\infty$ .

Anmerkung 1.13

$\tau _{i,i}$ - Zeitpunkt der 1. Rückkehr nach $i$

i

rekurrent:

\tau _{i,i}<\infty

P

-fast sicher

i

positiv-rekurrent:

\mathbb {E} \tau _{i,i}<\infty

i

null-rekurrent:

\mathbb {E} \tau _{i,i}=\infty

i

transient:

P(\tau _{i,i}=\infty )>0

.

Satz 1.14

Es gilt:

(1.5)

p_{i,j}^{n}=\sum _{k=0}^{n}\rho _{i,j}^{k}p_{j,j}^{n-k}

für alle

n\geq 0,i\neq j\in I

,

(1.6)

p_{i,i}^{n}=\sum _{k=0}^{n}\rho _{i,i}^{k}p_{i,i}^{n-k}

für alle

n\in \mathbb {N} ,i\in I

.

Ziel ist es nun, die Eigenschaft der Rekurrenz nur mit Hilfe der $p_{i,j}^{n}$ zu charakterisieren.

Definition 1.15

Sei $(a_{n})_{n\in \mathbb {N} }$ Zahlenfolge in $\mathbb {R}$ . Die Funktion $a:(-1,1)\to \mathbb {R}$ mit

$a(s):=\sum _{n=0}^{\infty }a_{n}s^{n}$ für alle $s\in (-1,1)$

heißt die erzeugende Funktion von $(a_{n})_{n\in \mathbb {N} }$ .

Dementsprechend seien also

\rho _{i,j}(s):=\sum _{n=0}^{\infty }\rho _{i,j}^{n}s^{n},\quad p_{i,j}(s):=\sum _{n=0}^{\infty }p_{i,j}^{n}s^{n}

die erzeugenden Funktionen von $(\rho _{i,j}^{n})_{n\in \mathbb {N} }$ und $(p_{i,j}^{n})_{n\in \mathbb {N} }$ .

Lemma 1.16

Für alle $|s|<1$ gilt:

(1.7) $\rho _{i,i}(s)p_{i,i}(s)=p_{i,i}(s)-1$ für alle $i\in I$ ,

(1.8) $\rho _{i,j}(s)p_{i,j}(s)=p_{i,j}(s)$ für alle $i\neq j\in I$ .

Lemma 1.17 (Abel)

Sei $(a_{n})_{n\in \mathbb {N} _{0}}\subseteq \mathbb {R}$ . Dann gilt:

a) $\sum _{n=0}^{\infty }a_{n}<\infty \quad \Rightarrow \quad \lim _{s\uparrow 1}\sum _{n=0}^{\infty }a_{n}s^{n}=\sum _{n=0}^{\infty }a_{n}.$

b) $a_{n}\geq 0,\lim _{s\uparrow 1}\sum _{n=0}^{\infty }a_{n}s^{n}=:a\leq \infty \quad \Rightarrow \quad \sum _{n=0}^{\infty }a_{n}=a.$

Satz 1.18

Es gilt:

a) $i$ rekurrent $\quad \Leftrightarrow \quad \sum _{n=0}^{\infty }p_{i,i}^{n}=\infty$ .

b) $i\leftrightsquigarrow j$ , $i$ rekurrent $\quad \Rightarrow \quad j$ rekurrent.

Sei $Q_{i,j}:=P({\text{Kette kommt unendlich oft nach }}j{\text{, startend in }}i)$ .

Satz 1.19

$(X_{n})_{n\in \mathbb {N} }$ homogene Markov-Kette. Dann gilt:

Q_{i,i}={\begin{cases}1,&falls\ i\ rekurrent\\0,&falls\ i\ transient.\end{cases}}

Falls $i$ rekurrent und $i\leftrightsquigarrow j\quad \Rightarrow \quad \rho _{i,j}=1$ und $Q_{i,j}=1$ .

1.4 Grenzwertsätze für Markov-Ketten

Definition 1.20

Eine homogene Markov-Kette heißt

a) aperiodisch, falls $d(i)=1$ für alle $i\in I$ ,

b) irreduzibel, falls $i\leftrightsquigarrow j$ für alle $i,j\in I$ und

c) rekurrent, falls $i$ rekurrent für alle $i\in I$ .

Satz 1.21

$i$ rekurrent, $i\leftrightsquigarrow j\quad \Rightarrow \quad \rho _{i,j}=\rho _{j,i}=1$ .

Satz 1.22

$(X_{n})_{n\in \mathbb {N} }$ homogene Markov-Kette. Dann gilt:

a) verbundene Zustände sind entweder alle rekurrent oder alle transient.

b) verbundene rekurrente Zustände sind entweder alle positiv-rekurrent oder alle null-rekurrent.

Definition 1.23

Eine Verteilung $(\pi _{i})_{i\in I}$ , also $\pi _{i}\geq 0$ und

\sum _{i\in I}\pi _{i}=1,

heißt stationäre Verteilung einer Markov-Kette mit Matrix $(p_{i,j})_{i,j\in I}$ , falls:

$\pi _{i}=\sum _{k\in I}\pi _{k}p_{k,i}$ für alle $i\in I$ .

Anmerkung 1.24

Falls $(\pi _{i})_{i\in I}$ Anfangsverteilung, dann sind $X_{0},X_{1},X2,\ldots$ alle identisch verteilt gemäß $(\pi _{i})_{i\in I}$ .

Theorem 1.1

Sei $(X_{n})_{n\in \mathbb {N} }$ eine irreduzible, homogene Markov-Kette mit Übergangsmatrix $(p_{i,j})_{i,j\in I}$ . Dann besitzt die Kette genau dann eine stationäre Verteilung, wenn alle Zustände positiv-rekurrent sind. In dem Fall ist die Verteilung eindeutig bestimmt durch:

\pi _{i}={\frac {1}{\mathbb {E} \tau _{i,i}}}.

Lemma 1.25

Eine Äquivalenzklasse $J\subseteq I$ ist genau dann aperiodisch, d. h. $d(j)=1$ für alle $j\in J$ , wenn für alle $i,j\in J$ ein $n_{0}\in \mathbb {N}$ existiert, so dass $p_{i,j}^{n}>0$ für alle $n\geq n_{0}$ .

Theorem 1.2

$(X_{n})_{n\in \mathbb {N} }$ sei eine homogene, irreduzible, aperiodische und positiv-rekurrente Markov-Kette. $(\pi _{i})_{i\in I}$ sei die dazugehörige stationäre Verteilung. $X_{0}$ habe eine beliebige Verteilung. Dann gilt:

$\lim _{n\to \infty }|P(X_{n}=i)-\pi _{i}|=0$ für alle $i\in I$ .

Folgerung 1.26

Es gilt

$\lim _{n\to \infty }p_{i,j}^{n}=\pi _{j}$ für alle $i,j\in I$ .

1.5 Konkrete Modelle

1.5.1 Ehrenfest-Modell

Ziel: Modellierung (physikalischer) Angleichungsprozesse

Betrachtet werden zwei Kammern A und B mit durchlässiger Trennwand. In jedem Schritt wandert genau ein Molekül entweder von A nach B oder von B nach A - mit Tendenz zum Ausgleich.

Sei also $m$ die Gesamtzahl der Moleküle und $X_{n}$ die Anzahl der Moleküle in Kammer A zur Zeit $n$ (also $m-X_{n}$ in Kammer B).

Die "Tendenz zum Ausgleich" wird wie folgt modelliert:

p_{i,j}:={\begin{cases}1-{\frac {i}{m}},&{\text{wenn }}j=i+1,i\in \{0,\ldots ,m-1\}\\{\frac {i}{m}},&{\text{wenn }}j=i-1,i\in \{1,\ldots ,m\}\\0&{\text{sonst.}}\end{cases}}

Also:

P={\begin{pmatrix}0&1&&&&&0\\{\frac {1}{m}}&0&1-{\frac {1}{m}}&&&&\\&{\frac {2}{m}}&0&1-{\frac {2}{m}}&&&\\&&&\ddots &&&\\&&&1-{\frac {2}{m}}&0&{\frac {2}{m}}&\\&&&&1-{\frac {1}{m}}&0&{\frac {1}{m}}\\0&&&&&1&0\end{pmatrix}}.

Die stationäre Verteilung $(\pi _{k})_{k=0}^{\infty }$ ist gegeben durch:

\pi _{k}:={\binom {m}{k}}\left({\frac {1}{2}}\right)^{k}\left({\frac {1}{2}}\right)^{m-k}=2^{-m}{\binom {m}{k}}

, also

(\pi _{k})_{k=0}^{\infty }=B(m,1/2)

.

Es gilt:

{\begin{matrix}\lim _{n\to \infty }p_{i,j}^{2n}=2\pi _{j},&p_{i,j}^{2n+1}=0,&{\text{falls }}(i-j){\text{ gerade}}\end{matrix}}

und

{\begin{matrix}\lim _{n\to \infty }p_{i,j}^{2n+1}=2\pi _{j},&p_{i,j}^{2n}=0,&{\text{falls }}(i-j){\text{ ungerade}}\end{matrix}}

Speziell sei jetzt $m=10^{6}$ und die Anfangsverteilung $X_{0}\sim B(m,1/2)$ , also auch $X_{n}\sim B(m,1/2)$ für alle $n\in \mathbb {N}$ . Dann gilt $\mathbb {E} X_{n}={\frac {1}{2}}10^{6}$ und

P(|X_{n}-\mathbb {E} X_{n}|\leq 1\%\mathbb {E} X_{n})=P(495\,000\leq X_{n}\leq 505\,000)\approx 1-10^{23}.

Die Wahrscheinlichkeit, eine Abweichung größer als 1% vom Erwartungswert (ausgeglichener Zustand) zu beobachten, ist praktisch nicht von 0 zu unterscheiden. Außerdem gilt:

\mathbb {E} \tau _{k,k}={\frac {1}{\pi _{k}}}={\frac {2^{m}}{\binom {m}{k}}}

, speziell

\mathbb {E} \tau _{0,0}=2^{m}

,

also die mittlere Wartezeit, erneut 0 Moleküle in Kammer A zu beobachten, wenn gerade 0 Moleküle darin sind.

1.5.2 Warteschlangen-Modell

Zu $t\in \mathbb {N} _{0}$ gehen $\xi _{n}$ Bestellungen ein $(\xi _{n}(\Omega )=\mathbb {N} _{0})$ . Je Zeiteinheit wird eine Bestellung bearbeitet. Wir bezeichnen mit $X_{n}$ die Anzahl der Kunden zum Zeitpunkt $n$ .

X_{0}:=\xi _{0},\quad X_{n+1}:=(X_{n}-1)^{+}+\xi _{n+1}

für

n>0

, wobei

a^{+}:=\max(a,0)

.