Mathematik für Faule: Dynamik/Markovketten

Satz (Eindeutigkeit stationärer Lösungen bei Durchmischung):

Beweis: Die Tabelle der Markovkette sei gegeben durch $Q$; es summieren sich also bei $Q$ die Spalten zu $1$. Wir betrachten nun die Tabelle $Q^{T}$. Hier summieren sich also die Zeilen zu $1$.

Es sei nun $v\in \mathbb {R} ^{n}$ mit $Q^{T}v=v$, das heißt $(Q^{T}-I)v=0$, also $v\in \operatorname {nil} (Q^{T}-I)$. Wir behaupten, dass alle Einträge von $v$ gleich sind.

Nach Annahme und Iteration gilt natürlich auch $(Q^{k})^{T}v=(Q^{T})^{k}v=v$ für alle $k\in \mathbb {N}$. Da $Q$ durchmischend ist, können wir $k$ hinreichend groß wählen, sodass alle Einträge von $Q^{k}$ positiv sind.

Angenommen, nicht alle Einträge von $v$ wären gleich. Dann gibt es einen größten Eintrag $v_{j}$. Es ist aber der j-te Eintrag von $(Q^{k})^{T}v$ einerseits gleich $v_{j}$, andererseits aber gleich einem gewichteten Durchschnitt von manchen Werten, die strikt kleiner sind als $v_{j}$, ein Widerspruch.

Wegen $\operatorname {nil} (Q^{T}-I)=\operatorname {nil} (Q-I)$ folgt die Behauptung. $\Box$

Satz (Konvergenz des Markovprozesses bei Durchmischung):

Beweis: Falls eine konvergente Teilfolge von $(Q^{n}v)_{n}$ gegeben ist, so konvergiert sie (wg. Limesübergang) zu einem stationären Wert, der wegen des vorhergehenden Satzes sowie $\sum _{k}v_{k}=1$ eindeutig ist. Da dies für alle konvergenten Teilfolgen gilt, und da $(Q^{n}v)_{n}$ beschränkt ist (wegen der Nichtnegativität der Komponenten und $\sum _{k}v_{k}=1$), erhalten wir sogar die Konvergenz.

Für die Konvergenzrate sei $w$ die eindeutige stationäre Verteilung. Des weiteren sei $w_{2},\ldots ,w_{n}$ eine Ergänzung von $w$ zu einer Redugenmenge des $\mathbb {R} ^{n}$. Durch Subtraktion eines Vielfachen von $w$ können wir jeweils erreichen, dass $w_{j}$ für $j=2,\ldots ,n$ die Eigenschaft hat, dass die Summe der Komponenten null ist. Außerdem ist die Summe der Komponenten nillinear, sodass wir durch das Gram–Schmidt-Verfahren die $w_{2},\ldots ,w_{n}$ zueinander rechtwinklig machen können.

Wir setzen nun $v_{k}:=w+\epsilon w_{k}$ für $2\leq k\leq n$ und $\epsilon >0$ hinreichend klein. Wegen der Konvergenz gibt es dann für hinreichend großes $m$ hinreichend kleine $\delta _{k,2},\ldots ,\delta _{k,n}$ mit

$Q^{m}v_{k}=w+\sum _{j=2}^{n}\delta _{k,j}w_{j}$,

sodass jedes gestörte $v'=w+\sum _{k=2}^{n}d_{k}w_{k}$ im Fehlerbetrag nach $m$ Iterationen einen gewissen Faktor einbüßt. $\Box$