Benutzer:Stepri2005/Kurs:Stochastische Prozesse/Markov-Ketten

1.1 Definition und Beispiele

Definition 1.1

Eine Folge von Zufallsgrößen $(X_{n})_{n\in \mathbb {N} }$ über Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikiversity.org/v1/“:): {\displaystyle (­\Omega, \mathcal F, P)} mit abzählbarem Zustandsraum

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikiversity.org/v1/“:): {\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)$.