aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/80-wahrscheinlichkeit/markov.tex
diff options
context:
space:
mode:
authorRoy Seitz <roy.seitz@ost.ch>2021-09-11 14:04:07 +0200
committerRoy Seitz <roy.seitz@ost.ch>2021-09-11 14:04:07 +0200
commitf6f7b194411c8fdda2ba6777a3d5fac69d043ad2 (patch)
treef151914b6af8736451e8d5f87ff09aaef773bc65 /buch/chapters/80-wahrscheinlichkeit/markov.tex
parentReferenz auf WrStatt-Skript. (diff)
parenttypos, index (diff)
downloadSeminarMatrizen-f6f7b194411c8fdda2ba6777a3d5fac69d043ad2.tar.gz
SeminarMatrizen-f6f7b194411c8fdda2ba6777a3d5fac69d043ad2.zip
Merge branch 'master' of github.com:AndreasFMueller/SeminarMatrizen
Diffstat (limited to 'buch/chapters/80-wahrscheinlichkeit/markov.tex')
-rw-r--r--buch/chapters/80-wahrscheinlichkeit/markov.tex198
1 files changed, 126 insertions, 72 deletions
diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex
index 0485714..1e30010 100644
--- a/buch/chapters/80-wahrscheinlichkeit/markov.tex
+++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex
@@ -18,7 +18,10 @@ werden.
%
\subsection{Markov-Eigenschaft}
% XXX Notation, Zustände, Übergangswahrscheinlichkeit
-Ein stochastischer Prozess ist eine Familie von Zustandsvariablen
+Ein stochastischer Prozess ist eine Familie von Zufallsvariablen
+\index{stochastischer Prozess}%
+\index{Prozess, stochastisch}%
+\index{Zufallsvariable}%
$X_t$ mit Werten in einer Menge $\mathcal{S}$ von Zuständen.
Der Parameter $t$ wird üblicherweise als die Zeit interpretiert,
er kann beliebige reelle Werte oder diskrete Werte annahmen, im letzten
@@ -36,6 +39,7 @@ Zustands $s\in\mathcal{S}$ zu einem späteren Zeitpunkt $t_1>t_0$
zu studieren.
Das Ereignis $\{X_t = x\}$ kann man sich als abhängig von der Vorgeschichte
vorstellen.
+\index{Vorgeschichte}%
Die Vorgeschichte besteht dabei aus dem Eintreten gewisser Ereignisse
\[
\{X_0=x_0\},
@@ -47,7 +51,7 @@ Die Vorgeschichte besteht dabei aus dem Eintreten gewisser Ereignisse
zu früheren Zeiten $t_0<t_1<\dots<t_n<t$.
Die bedingte Wahrscheinlichkeit
\begin{equation}
-P(X_t = x|
+P(X_t = x \mid
X_{t_n}=x_n\wedge X_{t_{n-1}}=x_{n-1}\wedge\dots\wedge X_{t_1}=x_1\wedge
X_{t_0}=x_0)
\label{buch:wahrscheinlichkeit:eqn:historybedingt}
@@ -58,6 +62,7 @@ die Zustände $x_0,x_1,\dots,x_n$ durchlaufen hat.
\subsubsection{Gedächtnislosigkeit}
% XXX Gedächtnislösigkeit, Markov-Eigenschaft
+\index{Markov-Eigenschaft}%
In vielen Fällen ist nur der letzte durchlaufene Zustand wichtig.
Die Zustände in den Zeitpunkten $t_0<\dots<t_{n-1}$ haben dann keinen
Einfluss auf die Wahrscheinlichkeit.
@@ -73,25 +78,26 @@ $x_0,\dots,x_n,x\in \mathcal{S}$ die
Wahrscheinlichkeit~\eqref{buch:wahrscheinlichkeit:eqn:historybedingt}
nicht von der Vorgeschichte abhängt, also
\[
-P(X_t = x|
+P(X_t = x\mid
X_{t_n}=x_n\wedge X_{t_{n-1}}=x_{n-1}\wedge\dots\wedge X_{t_1}=x_1\wedge
X_{t_0}=x_0)
=
-P(X_t = x|
+P(X_t = x \mid
X_{t_n}=x_n).
\]
\index{Markov-Eigenschaft}
\end{definition}
-Die Wahrscheinlichkeiten $P(X_t=x|X_s=y)$ mit $t>s$ bestimmen das
+Die Wahrscheinlichkeiten $P(X_t=x\mid X_s=y)$ mit $t>s$ bestimmen das
zeitliche Verhalten der Wahrscheinlichkeiten vollständig.
Wir schreiben daher auch
\[
p_{xy}(t, s)
=
-P(X_t = x|X_s=y)
+P(X_t = x\mid X_s=y)
\]
für die sogenannte {\em transiente Übergangswahrscheinlichkeit}.
+\index{transiente Übergangswahrscheinlichkeit}%
Für eine endliche Menge von Zuständen, können die transienten
Übergangswahrscheinlichkeiten auch als zeitabhängige
quadratische Matrix $P(s,t)$ geschrieben werden, deren
@@ -105,13 +111,14 @@ mit den Zuständen $x,y\in\mathcal{S}$ indiziert sind.
\subsubsection{Die Chapman-Kolmogorov-Gleichung}
% XXX Chapman-Kolmogorov-Gleichung
+\index{Chapman-Kolmogorov-Gleichung}%
Man beachte, dass in der Definition der Markov-Eigenschaft
keine Voraussetzungen darüber gemacht werden, wie nahe
am Zeitpunkt $t$ der letzte Zeitpunkt $t_n$ der Vorgeschichte liegt.
Die transienten Übergangswahrscheinlichkeiten $p_{xy}(s,t)$ werden
aber im allgemeinen davon abhängen, wie weit in der Vergangenheit
der Zeitpunkt $s<t$ liegt.
-Für eine näheren Zeitpunkt $\tau$ mit $s<\tau <t$ muss es daher
+Für einen näheren Zeitpunkt $\tau$ mit $s<\tau <t$ muss es daher
einen Zusammenhang zwischen den transienten Übergangswahrscheinlichkeiten
$p_{xy}(s,\tau)$, $p_{xy}(\tau,t)$ und $p_{xy}(s,t)$ geben.
@@ -187,16 +194,18 @@ Es ist üblich, für die Zeitpunkte ganze oder natürliche Zahlen zu
verwenden.
\begin{definition}
-Eine diskrete Markov-Kette ist ein stochastischer Prozess
+Eine {\em diskrete Markov-Kette} ist ein stochastischer Prozess
$(X_t)_{t\in\mathbb{N}}$ mit Werten in $\mathcal{S}$, der die
Markov-Eigenschaft
\[
-P(X_{n+1}=x_{n+1}|X_n=x_n\wedge\dots X_0=x_0)
+P(X_{n+1}=x_{n+1}\mid X_n=x_n\wedge\dots X_0=x_0)
=
-P(X_{n+1}=x_{n+1}|X_n=x_n)
+P(X_{n+1}=x_{n+1}\mid X_n=x_n)
\]
hat.
\end{definition}
+\index{diskrete Markov-Kette}%
+\index{Markov-Kette, diskret}%
\begin{figure}
\centering
@@ -220,8 +229,9 @@ p_{11}(n+1,n) & \dots & p_{1s}(n+1,n)\\
p_{11}(n+1,n) & \dots & p_{1s}(n+1,n)
\end{pmatrix},
\]
-auch die $1$-Schritt Übergangswahrscheinlichkeit genannt, kann man jetzt
+auch die $1$-Schritt-Übergangswahrscheinlichkeit genannt, kann man jetzt
auch die Matrix der Überganswahrscheinlichkeiten für mehrere Schritte
+\index{Ubergangswahrscheinlichkeit@Übergangswahrscheinlichkeit}%
\[
T(n+m,n)
=
@@ -239,12 +249,12 @@ verwendet werden, wenn sie zwei Bedingungen erfüllt:
\begin{enumerate}
\item Die Einträge von $T$ müssen als Wahrscheinlichkeiten interpretiert
werden können, sie müssen also alle zwischen $0$ und $1$ sein:
-$0\le t_{ij}\le 1$ für $i,j\in\mathcal{S}$
+$0\le t_{i\!j}\le 1$ für $i,j\in\mathcal{S}$
\item Die Matrix muss alle möglichen Fälle erfassen.
Dazu ist notwendig, dass sich die Wahrscheinlichkeiten aller Übergänge
aus einem Zustand $j$ zu $1$ summieren, also
\[
-\sum_{i\in\mathcal{S}} p_{ij} = 1.
+\sum_{i\in\mathcal{S}} p_{i\!j} = 1.
\]
Die Summe der Elemente einer Spalte
\end{enumerate}
@@ -252,6 +262,7 @@ Die Summe der Elemente einer Spalte
\begin{beispiel}
Die Permutationsmatrix einer Permutation $\sigma\in S_n$
(Abschnitt~\label{buch:section:permutationsmatrizen})
+\index{Permutationsmatrix}%
ist eine Matrix mit Einträgen $0$ und $1$, so dass die erste Bedingung
erfüllt ist.
In jeder Zeile oder Spalte kommt genau eine $1$ vor, so dass auch die
@@ -269,8 +280,8 @@ p_i(n)
=
P(X_i=n)
\]
-geschrieben, die auch in einem Vektor $p(n)$ zusammengefasst
-werden können.
+geschrieben, die auch in einem Vektor $p(n)$ mit den Komponten
+$p_i(n)$ zusammengefasst werden können.
Die Matrix der Übergangswahrscheinlichkeiten erlaubt, die Verteilung
$p(n+1)$ aus der Verteilung $p(n)$ zu berechnen.
Nach dem Satz von der totalen Wahrscheinlichkeit ist nämlich
@@ -278,9 +289,9 @@ Nach dem Satz von der totalen Wahrscheinlichkeit ist nämlich
P(X_{n+1}=x)
=
\sum_{y\in\mathcal{S}}
-P(X_{n+1}=x|X_n=y) P(X_n=y)
+P(X_{n+1}=x\mid X_n=y) P(X_n=y)
\qquad\text{oder}\qquad
-p^{(n+1)} = T(n+1,n) p^{(n)}
+p(n+1) = T(n+1,n) p(n)
\]
in Matrixform.
Die Zeitentwicklung kann also durch Multiplikation mit der Übergangsmatrix
@@ -288,6 +299,7 @@ berechnet werden.
\subsubsection{Zeitunabhängige Übergangswahrscheinlichkeiten}
% XXX Übergangswahrscheinlichkeit
+\index{zeitunabhängige Übergangswahrscheinlichkeiten}
Besonderes einfach wird die Situation, wenn die Übergangsmatrix $T(n+1,n)$
nicht von der Zeit abhängt.
In diesem Fall ist $T(n+1,n) = T$ für alle $n$.
@@ -311,32 +323,41 @@ homogene Markov-Kette mit Übergangsmatrix $T$, wenn $Tp=p$.
\end{definition}
Eine stationäre Verteilung ist offenbar ein Eigenvektor der Matrix
-$T$ zum Eigenwert $1$.
+$T$ zum Eigenwert $1$.
Gefunden werden kann er als Lösung des Gleichungssystems $Tp=p$.
-Dazu muss die Matrix $T-E$ singulär sein.
-Die Summe einer Spalte von $T$ ist aber immer ein, da $E$ in jeder Spalte
+Dazu muss aber die Matrix $T-I$ singulär sein, wie man wie folgt
+einsehen kann.
+Die Summe einer Spalte von $T$ ist aber immer $1$, da sich die
+Wahrscheinlichkeiten zu $1$ summieren müssen.
+Da die Einheitsmatrix $I$ in jeder Spalte
genau eine $1$ enthält, ist die Summe der Einträge einer Spalte von
-$T-E$ folglich $0$.
-Die Summe aller Zeilen von $T-E$ ist also $0$, die Matrix $T-E$
+$I$ ebenfalls $1$.
+Die Summe einer Spalte von $T-I$ ist folglich $0$.
+Die Summe aller Zeilen von $T-I$ ist also $0$, die Matrix $T-I$
ist singulär.
-Dies garantiert aber noch nicht, dass alle Einträge in diesem
-Eigenvektor auch tatsächlich nichtnegativ sind.
+
+Dass $T-I$ singulär ist, garantiert aber noch nicht,
+dass alle Einträge in einem zum Eigenwert $1$
+Eigenvektor auch tatsächlich nichtnegativ gewählt werden können.
Die Perron-Frobienus-Theorie von
+\index{Perron-Frobenius-Theorie}%
Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen}
-beweist, dass sich immer ein Eigenvektor mit nichtnegativen
-Einträgen finden lässt.
+beweist, dass genau dies immer möglich ist.
-Es ist aber nicht garantiert, dass eine stationäre Verteilung
+Es ist nicht garantiert, dass eine stationäre Verteilung
auch eindeutig bestimmt ist.
Dieser Fall tritt immer ein, wenn die geometrische Vielfachheit
des Eigenwerts $1$ grösser ist als $1$.
In Abschnitt~\ref{buch:subsection:elementare-eigenschaften}
werden Bedingungen an eine Matrix $T$ untersucht, die garantieren,
-dass der Eigenraum zum Eigenvektor $1$ einedeutig bestimmt ist.
+dass der Eigenraum zum Eigenvektor $1$ eindimensional ist.
\begin{beispiel}
-Als Beispiel dafür betrachten wir eine Permutation $\sigma\in S_n$
-und die zugehörige Permutationsmatrix $P$,
+Als Beispiel dafür, dass der Eigenraum $\mathcal{E}_1(T)$
+mehrdimensional sein kann, betrachten wir eine Permutation $\sigma\in S_n$
+\index{Permutation}%
+und die zugehörige Permutationsmatrix $P_\sigma$,
+\index{Permutationsmatrix}%
wie sie in Abschnitt~\label{buch:section:permutationsmatrizen}
beschrieben worden ist.
Wir verwenden die
@@ -365,7 +386,8 @@ setzt.
Die Konstruktion stellt sicher, dass sich die Komponenten zu $1$
summieren.
Wir können aus dem Beispiel auch ableiten, dass die geometrische
-Vielfachheit des Eigenvektors $1$ mindestens so gross ist wie die
+Vielfachheit des Eigenwerts $1$ einer Permutationsmatrix $P_\sigma$
+mindestens so gross ist wie die
Anzahl der Zyklen der Permutation $\sigma$.
\end{beispiel}
@@ -377,8 +399,9 @@ Die Zyklen können daher unabhängig voneinander studiert werden.
Diese Idee kann auf allgemeine Markov-Ketten verallgemeinert werden.
\begin{definition}
-Zwei Zustände $i,j\in\mathcal{S}$ kommunizieren, wenn die
-Übergangswahrscheinlichkeiten $T_{ij}(n) \ne 0$ und $T_{ij}(n)\ne 0$ sind
+Zwei Zustände $i,j\in\mathcal{S}$ {\em kommunizieren}, wenn die
+\index{kommunizieren}%
+Übergangswahrscheinlichkeiten $T_{i\!j}(n) \ne 0$ und $T_{i\!j}(n)\ne 0$ sind
für $n$ gross genug.
\end{definition}
@@ -407,12 +430,14 @@ Solche Markov-Ketten können unabhängig voneinander studiert werden.
Die Bedingung der Irreduzibilität ist gleichbedeutend damit,
dass für genügend grosses $n$ alle Matrixelemente von $T^n$ positiv sind.
-Solche Matrizen nennt man positiv,
+Solche Matrizen nennt man {\em positiv},
+\index{positive Matrix}%
in Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen}
wird gezeigt, dass positive Matrizen immer eine eindeutige
stationäre Verteilung haben.
In Abbildung~\ref{buch:wahrscheinlichkeit:fig:markovzerfall}
ist eine reduzible Markov-Kette dargestellt, die Zustandsmenge
+\index{reduzible Markov-Kette}%
zerfällt in zwei Teilmengen von Zuständen, die nicht miteinander
kommunizieren.
Ein irreduzible Markov-Kette liegt vor, wenn sich ähnlich wie
@@ -420,7 +445,7 @@ in Abbildung~\ref{buch:wahrscheinlichkeit:fig:diskretemarkovkette}
jeder Zustand von jedem anderen aus erreichen lässt.
Wenn sich der Vektorraum $\mathbb{R}^n$ in zwei unter $T$ invariante
-Unterräme zerlegen lässt, dann hat nach Wahl von Basen in den Unterräumen
+Unterräume zerlegen lässt, dann hat nach Wahl von Basen in den Unterräumen
die Matrix $T$ die Form
\[
\left(
@@ -483,7 +508,7 @@ Die stationären Verteilungen
\operatorname{Stat}(T)
=
\{
-p\in\mathbb R_+^n\;|\; \text{$Tp=p $ und $\|p\|_1=1$}
+p\in\mathbb R_+^n \mid \text{$Tp=p $ und $\|p\|_1=1$}
\}
\]
bilden was man eine konvexe Menge nennt.
@@ -495,7 +520,7 @@ Jede Verteilung auf der ``Verbindungsstrecke'' zwischen den beiden
Verteilungen ist auch wieder stationär.
\begin{definition}
-Eine {\em konvexe Kombination} von Vektoren $v_1,\dots,v_k\in\mathbb{R^n}$
+Eine {\em konvexe Kombination} von Vektoren $v_1,\dots,v_k\in\mathbb{R}^n$
ist ein Vektor der Form
\[
v=t_1v_1+\dots + t_kv_k
@@ -512,7 +537,8 @@ wieder in $M$ ist.
Die konvexen Kombinationen der Vektoren sind Linearkombination
mit nichtnegativen Koeffizienten. Sie bilden im Allgemeinen
-einen $(k-1)$-Simplex in $\mathbb{R}^n$.
+einen $(k-1)$-Simplex in $\mathbb{R}^n$ (siehe auch
+Abbildung~\ref{buch:wahrscheinlichkeit:fig:konvex}).
Für zwei Punkte $x$ und $y$ bilden die konvexen Kombination
$tx+(1-t)y$ für $t\in[0,1]$ die Verbindungsstrecke der beiden
Vektoren.
@@ -527,7 +553,7 @@ ihre Verbindungsstrecke enthält
Im Beispiel der Google-Matrix wurde ein iterativer Algorithmus
zur Berechnung des Pagerank verwendet.
Es stellt sich daher die Frage, ob diese Methode für andere homogene
-Markov-Ketten auch funkioniert.
+Markov-Ketten auch funktioniert.
Man beginnt also mit einer beliebigen Verteilung $p(0)$ und wendet
die Übergangsmatrix $T$ wiederholt an.
Es entsteht somit eine Folge $p(n) = T^np(0)$.
@@ -546,8 +572,8 @@ Verteilung.
Für eine stationäre Verteilung $p(0)$ ist die Folge $p(n)$ eine
konstante Folge, sie konvergiert also gegen $p(0)$.
Stationäre Verteilungen sind also automatisch Grenzverteilungen.
-Falls der Raum der stationären Verteilungen mehrdimensional sind,
-dann ist auch die Grenzverteilung nicht eindeutig bestimmt, selbst
+Falls der Raum der stationären Verteilungen mehrdimensional ist,
+braucht die Grenzverteilung nicht eindeutig bestimmt zu sein, selbst
wenn sie existiert.
Aber nicht einmal die Existenz einer Grenzverteilung ist garantiert,
wie das folgende Beispiel zeigt.
@@ -578,6 +604,8 @@ p(2)&=p(5)=p(8)=\dots =\begin{pmatrix}p_3(0)\\p_1(0)\\p_2(0)\end{pmatrix}.
\end{align*}
Die Folge $p(n)$ kann also nur dann konvergieren, wenn die drei
Komponenten gleich sind.
+Insbesondere gibt es keine Grenzverteilung, wenn sie nicht alle
+gleich sind.
\end{beispiel}
\subsubsection{Erwartungswert und Varianz}
@@ -588,11 +616,11 @@ zu berechnen.
Dazu muss jedem Zustand ein Zahlenwert zugeordnet werden.
Sei also
\(
-g: \mathcal{S}\to R
+g: \mathcal{S}\to \mathbb{R}
\)
eine Funktion, die einem Zustand eine reelle Zahl zuordnet.
Aus der Zufallsvariable $X_n$ des Zustands zur Zeit $n$ wird daraus
-die Zufallsvariable $Y_n=g(X_n)$ des Wertes zur Zeit $n$.
+die reellwertige Zufallsvariable $Y_n=g(X_n)$ des Wertes zur Zeit $n$.
Die Abbildung $g$ kann auch als Vektor mit der Komponenten $g_i$
für $i\in\mathcal{S}$ betrachtet werden, wir verwenden für diesen
Vektor wieder die Schreibweise $g$.
@@ -634,7 +662,7 @@ definieren.
In Abschnitt~\ref{buch:section:paradoxon-von-parrondo} wird ein Spiel
vorgestellt, in dem der Gewinn davon abhängt, welcher Übergang stattfindet,
nicht welcher Zustand erreicht wird.
-Es git daher eine Matrix $G$ von Gewinnen, der Eintrag $g_{ij}$ ist
+Es git daher eine Matrix $G$ von Gewinnen, der Eintrag $g_{i\!j}$ ist
der Gewinn, der bei einem Übergang von Zustand $j$ in den Zustand $i$
ausgezahlt wird.
Mit dieser Matrix lassen sich jetzt viele verschiedene Fragen beantworten:
@@ -642,7 +670,7 @@ Mit dieser Matrix lassen sich jetzt viele verschiedene Fragen beantworten:
\begin{frage}
\label{buch:wahrscheinlichkeit:frage1}
Mit welchem Gewinn kann man in Runde $n$ des Spiels rechnen,
-wenn $p(n-1)$ die Verteilung zur Zeit $n-1$ ist?
+wenn die Verteilung zur Zeit $n-1$ durch $p(n-1)$ gegeben ist?
\end{frage}
Der Erwartungswert ist
@@ -664,15 +692,15 @@ einer Spielrunde im Zustand $i$ befindet?
\end{frage}
Dies ist der Spezialfall der Frage~\ref{buch:wahrscheinlichkeit:frage1}
-für die Verteilung $p_j(n-1) = \delta_{ij}$.
+für die Verteilung $p_j(n-1) = \delta_{i\!j}$.
Der Erwartungswert ist die Summe der Spalte $j$ der Matrix $G\odot T$.
Man kann das Produkt $U^t(G\odot T)$ also auch als eine Zeilenvektor
von Gewinnerwartungen unter der Vorbedingung $X_{n-1}=j$ betrachten.
\[
\begin{pmatrix}
-E(Y|X_{n-1}=1)
+E(Y\mid X_{n-1}=1)
&\dots&
-E(Y|X_{n-1}=n)
+E(Y\mid X_{n-1}=n)
\end{pmatrix}
=
U^t (G\odot T).
@@ -681,6 +709,9 @@ Indem man $G$ durch $G^{\odot k}$ ersetzt, kann man beliebige höhere
Momente berechnen.
\subsection{Absorbierende Zustände}
+In diesem Abschnitt gehen wir immer von einer irreduziblen Markov-Kette
+aus.
+
% XXX Definition
Eine Grenzverteilung beschreibt die relative Häufigkeit, mit der
der Prozess in den verschiedenen Zuständen vorbeikommt.
@@ -710,13 +741,13 @@ sie für alle zukünftigen Zustände in diesem Zustand.
Eine Markov-Kette kann mehrere absorbierende Zustände haben, wie in
Abbildung~\ref{buch:wahrscheinlichkeit:fig:abs} dargestellt.
-Indem man die absorbierenden Zustände zuerst auflistet, bekommt die
-Übergangsmatrix die Form
+Indem man die absorbierenden Zustände zuerst auflistet, gefolgt von
+den transienten Zustädnen, bekommt die Übergangsmatrix die Form
\[
T=
\left(
\begin{array}{c|c}
-E&R\\
+I&R\\
\hline
0&Q
\end{array}
@@ -732,7 +763,7 @@ T^2
=
\left(
\begin{array}{c|c}
-E&R+RQ \\
+I&R+RQ \\
\hline
0&Q^2
\end{array}
@@ -742,7 +773,7 @@ T^3
=
\left(
\begin{array}{c|c}
-E&R+RQ+RQ^2 \\
+I&R+RQ+RQ^2 \\
\hline
0&Q^3
\end{array}
@@ -754,18 +785,19 @@ T^k
=
\left(
\begin{array}{c|c}
-E&\displaystyle R\sum_{l=0}^{k-1} Q^l \\
+I&\displaystyle R\sum_{l=0}^{k-1} Q^l \\
\hline
0&Q^k
\end{array}
\right).
\]
-Da man früher oder später in einem absorbierenden Zustand landet,
-muss $\lim_{k\to\infty} Q^k=0$ sein.
+Wegen der angenommenen Irreduzibilität wird man
+früher oder später in einem absorbierenden Zustand landet,
+daher muss $\lim_{k\to\infty} Q^k=0$ sein.
Die Summe in der rechten oberen Teilmatrix kann man als geometrische
Reihe summieren, man erhält die Matrix
\[
-\sum_{l=0}^{k-1} Q^l = (E-Q)^{-1}(E-Q^k),
+\sum_{l=0}^{k-1} Q^l = (I-Q)^{-1}(I-Q^k),
\]
die für $k\to\infty$ gegen
\[
@@ -773,7 +805,7 @@ N
=
\lim_{k\to\infty} \sum_{l=0}^{k-1} Q^l
=
-(E-Q)^{-1}
+(I-Q)^{-1}
\]
konvergiert.
Die Matrix $N$ heisst die {\em Fundamentalmatrix} der absorbierenden
@@ -784,12 +816,13 @@ Markov-Kette.
% XXX Absorptionszeit
Wie lange dauert es im Mittel, bis der Prozess in einem
Absorptionszustand $i$ stecken bleibt?
+\index{Absorbtionszeit}%
Die Fundamentalmatrix $N$ der Markov-Kette beantwortet diese
Frage.
-Wenn der Prozess genau im Schritt $k$ zum ersten Mal Zustand $i$
+Wenn der Prozess genau im Schritt $k$ zum ersten Mal im Zustand $i$
ankommt, dann ist $E(k)$ die mittlere Wartezeit.
Der Prozess verbringt also zunächst $k-1$ Schritte in transienten
-Zuständen, bevor er in einen absorbierenden Zustand wechselt.
+Zuständen, bevor er in einen absorbierenden Zustand $i$ wechselt.
Wir brauchen die Wahrscheinlichkeit für einen Entwicklung des Zustandes
ausgehend vom Zustand $j$, die nach $k-1$ Schritten im Zustand $l$
@@ -808,7 +841,7 @@ innerhalb der Menge der Pfade, die auch tatsächlich absorbiert werden,
das ist die bedingte Wahrscheinlichkeit
\begin{equation}
\begin{aligned}
-P(X_k = i\wedge X_{k-1} = l \wedge X_0=j|X_k=i)
+P(X_k = i\wedge X_{k-1} = l \wedge X_0=j\mid X_k=i)
&=
\frac{
P(X_k = i\wedge X_{k-1} = l \wedge X_0=j)
@@ -833,25 +866,25 @@ E(k)
&=
\sum_{k=0}^\infty
k(
-q^{(k)}_{lj}
+q^{(k)}_{l\!j}
-
-q^{(k-1)}_{lj}
+q^{(k-1)}_{l\!j}
)
\notag
\\
&=
\dots
+
-(k+1)(
-q^{(k)}_{lj}
+k(
+q^{(k-1)}_{l\!j}
-
-q^{(k+1)}_{lj}
+q^{(k)}_{l\!j}
)
+
-k(
-q^{(k-1)}_{lj}
+(k+1)(
+q^{(k)}_{l\!j}
-
-q^{(k)}_{lj}
+q^{(k+1)}_{l\!j}
)
+
\dots
@@ -860,23 +893,44 @@ q^{(k)}_{lj}
&=
\dots
+
-q^{(k-1)}_{lj}
+k
+q^{(k-1)}_{l\!j}
+\underbrace{
+\mathstrut
+-
+q^{(k)}_{l\!j}
++
+(k+1)
+q^{(k)}_{l\!j} }_{\displaystyle q^{(k)}_{l\!j}}
+\mathstrut
+-
+(k+1)
+q^{(k+1)}_{l\!j}
++
+\dots
+\\
+&=
+\dots
++
+q^{(k)}_{l\!j}
+
\dots
=
-\sum_{k} q^{(k)}_{lj}.
+\sum_{k} q^{(k)}_{l\!j}.
\notag
\end{align}
In zwei benachbarten Termen in
\eqref{buch:wahrscheinlichkeit:eqn:telescope}
-heben sich die Summanden $kq^{(k)}_{lj}$ weg, man spricht von
+heben sich die Summanden $kq^{(k)}_{l\!j}$ weg, man spricht von
einer teleskopischen Reihe.
+\index{teleskopische Reihe}%
Die verbleibenden Terme sind genau die Matrixelemente der Fundamentalmatrix $N$.
Die Fundamentalmatrix enthält also im Eintrag $(l,j)$ die Wartezeit
bis zur Absorption über den Zustand $l$.
\subsubsection{Wartezeit}
% XXX Mittlere Zeit bis zu einem bestimmten Zustand
+\index{Wartezeit}%
Die mittlere Wartezeit bis zum Erreichen eines Zustands kann mit der
Theorie zur Berechnung der Absorptionszeit berechnet werden.
Dazu modifiziert man den Prozess dahingehend, dass der Zielzustand