33 - Markov-Ketten

Eine endliche Folge von Zufallsvariablen $X_0,\ldots,X_T$ heißt Markov-Kette mit Zustandsraum $S$ und Übergangsmatrix $\boldsymbol{P}=(p(x_i,x_j))_{i,j\in S}$, falls $$P(X_n=x_n|X_0=x_0,\ldots,X_{n-1}=x_{n-1})=P(X_n=x_n|X_{n-1}=x_{n-1})=p(x_{n-1},x_n)$$ für alle $x_0,\ldots,x_n\in S$ und $n=1,\ldots,T$ mit $$P(X_0=x_0,\ldots,X_{n-1}=x_{n-1})>0.$$ Der Zeilenvektor $\boldsymbol{p}_0=(p_0,\ldots,p_m)$, $p_i=P(X_0=x_i)$, heißt Startverteilung.

Eine $m\times m$-Matrix mit Einträgen zwischen 0 und 1, die sich zeilenweise zu 1 addieren, nennt man stochastische Matrix.

Für den Zeilenvektor $\boldsymbol{p}^{(n)}=(p_1^{(n)},\ldots,p_m^{(n)})$ der Wahrscheinlichkeiten $p_i^{(n)}=P(X_n=i)$, dass sich das System nach $n$ Schritten in Zustand $i$ befindet, gilt: $$\boldsymbol{p}^{(n)}=\boldsymbol{p}_0\boldsymbol{P}^n.$$ $\boldsymbol{P}^n$ heißt $n$-Schritt-Übergangsmatrix.

$H_i=\min\{j|X_{i+j}\neq X_i\}$ heißt Verweilzeit im $i$-ten Zustand. Es gilt $H_i|H_0\sim\text{Geo}(p_{ii})$.

Chapman-Kolmogorov-Gleichung

Für alle $x,y\in S$ und $n,m\in\mathbb{N}$ gilt: $$p^{(m+n)}(x,y)=\sum_{z\in S}\, p^{(m)}(x,z)p^{(n)}(z,y).$$

Stationäre Verteilung

Eine Verteilung $\pi$ auf $S$ mit $\pi=\lim_{n\rightarrow\infty}\boldsymbol{p}^{(n)}$ und $\pi=\pi\boldsymbol{P}$ heißt stationäre Verteilung.

Ist $\pi$ stationäre Verteilung, dann ist $\pi'$ normierter Eigenvektor zum Eigenwert 1 von $\boldsymbol{P}'$.

Irreduzibilität

Eine stochastische Matrix $\boldsymbol{P}$ heißt irreduzibel, wenn es für beliebige Zustände $x,y\in S$ ein $n\in\mathbb{N}_0$ gibt, sodass man ausgehend vom Zustand $x$ den Zustand $y$ nach $n$ Schritten erreichen kann, d.h. $p^{(n)}(x,y)>0$.

Periodizität

Eine stochastische Matrix $\boldsymbol{P}$ heißt periodisch, wenn das System alle $k\geq2$ Zustände wieder in einen Zustand $x$ zurückkehren kann, d.h. wenn $p^{(n)}(x,x)>0$ für $n=kr$ mit $r\in\mathbb{N}$ gilt. Dann ist der ggT der Menge $$\mathcal{N}(x)=\{n\in\mathbb{N}:p^{(n)}(x,x)>0\}$$
größer als 1.

$\boldsymbol{P}$ heißt aperiodisch, wenn für jeden Zustand $x\in S$ der ggT der Menge $\mathcal{N}(x)$ genau 1 ist.

$\boldsymbol{P}$ heißt ergodisch, wenn es ein $k\in\mathbb{N}$ gibt, sodass alle Einträge $\boldsymbol{P}^k$ positiv sind.

Eine stochastische Matrix $\boldsymbol{P}$ ist genau dann ergodisch, wenn sie irreduzibel und aperiodisch ist.

Ergodensatz

Eine ergodische stochastische Matrix $\boldsymbol{P}$ besitzt genau eine stationäre Verteilung $\pi=(\pi_1,\ldots,\pi_m)$. Alle $\pi_j$ sind positiv und die $n$-Schritt-Übergangswahrscheinlichkeiten konvergieren unabhängig vom Startzustand gegen die stationäre Verteilung, d.h. für alle $j=1,\ldots,m$ gilt: $$\lim_{n\rightarrow\infty}p_{ij}^{(n)}=\pi_j, \qquad \text{für ale }i=1,\ldots,n.$$