diff options
Diffstat (limited to 'buch/chapters/80-wahrscheinlichkeit/markov.tex')
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/markov.tex | 198 |
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 |