1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
\newcommand{\F}{\mathcal{F}}
\renewcommand{\P}{\mathbb{P}}
\section*{Grundlagen}
Betrachtet wird Folge von Zufallsvariablen $(X_n)$ auf Wahrscheinlichkeitsraum $(\Omega,\F,\P)$ mit $X_n : \Omega \to S$. $S$ sei endlich oder abzählbar unendlich.
$X_n$ beschreibt Zustand des Systems zur Zeit $n$.
$(X_n)$ ist \emph{stochastischer Prozess} in diskreter Zeit.
\subsection*{Stochastische Matrizen}
Eine Matrix $P = (p_{ij})_{i,j \in S}$ heißt \emph{stochastisch}, falls $p_{ij} \geq 0$ und $\forall i \in S : \sum_{j \in S} p_{ij} = 1$ gilt.
Produkt stochastischer Matrizen ist stochastisch.
\section*{Homogene Markov-Ketten}
Eine Folge $X_0, X_1, X_2, \dots$ von $S$-wertigen ZV heißt \emph{homogene Markov-Kette} mit Übergangsmatrix $P$, falls für $\forall n \in \N$ und alle Zustände $i_k \in S$ mit $\P(X_0 = i_0,\dots,X_n = i_n) > 0$ gilt:
\vspace*{-4mm}
\begin{align*}
&\P(X_{n+1} = i_{n+1} | X_0 = i_0, \dots, X_n = i_n) \\
&= \P(X_{n+1} = i_{n+1} | X_n = i_n) \\
&= p_{i_n i_{n+1}}
\end{align*}
$p_{ij}$ heißen \emph{Übergangswahrscheinlichkeiten}.
$\nu(i) = \P(X_0=i)$ def. für $i \in S$ die \emph{Startverteilung}.
\vspace*{2mm}
Jede Folge unabhängiger ZV ist Markov-Kette.
Übergangswk. einer homogenen Markov-Kette hängen nicht vom Zeitpunkt des Übergangs ab.
\subsection*{Charakterisierung}
Es sind äquivalent:
\begin{enumerate}[label=(\alph*)]
\item $(X_n)$ ist MK mit Übergangsmatrix $P$
\item $\forall n \in \N_0, i_k \in S :$ \vspace*{-2mm} \\ $\P(X_k = i_k, 0 \leq k \leq n) = \P(X_0 = i_0) \displaystyle\prod_{k=0}^{n-1} p_{i_k i_{k+1}}$
\item $\forall n \in \N_0, i_k \in S$ mit $\P(X_0 = i_0) > 0$: \\ $\P(X_k = i_k, 1 \leq k \leq n | X_0 = i_0) = \prod_{k=0}^{n-1} p_{i_k i_{k+1}}$
\end{enumerate}
\subsection*{$n$-Schritt Übergang}
Sei $P$ stochastische Matrix. Dann sind $p_{ij}^{(n)}$ von $P^n$ die \emph{$n$-Schritt-Übergangswahrscheinlichkeiten} zu $P$.
$\forall i, j \in S, m, n \in \N_0$ mit $\P(X_m = i) > 0 : \\ \P(X_{n+m} = j | X_m = i) = p_{ij}^{(n)}.$
$\forall j \in S, n \in \N : \P(X_n = j) = \sum_{j \in S} \P(X_0 = i) p_{ij}^{(n)}$
\subsection*{Chapman-Kolmogorov-Gleichung}
$p_{ij}^{(n+m)} = \displaystyle\sum_{k \in S} p_{ik}^{(n)} p_{kj}^{(m)}$ für $i, j \in S$.
\section*{Zustandsklassifikation}
Ein Zustand $i \in S$ \emph{führt nach} $j \in S$ (kurz $i \rightsquigarrow j$), falls $\exists n \in \N : p_{ij}^{(n)} > 0$.
Ein Zustand $i \in S$ \emph{kommuniziert mit} $j \in S$ ($i \leftrightarrow j$), falls $i \rightsquigarrow j$ und $j \rightsquigarrow i$ gelten.
\subsection*{Äquivalenzklassen}
Die Relation $i \sim j := (i \leftrightarrow j) \lor (i = j)$ definiert eine Äquivalenzrelation auf $S$.
Zustandsmenge $S$ lässt sich in Äquivalenzklassen $K(i) := \{j \in S | i \sim j\}$ partitionieren.
\vspace*{2mm}
$J \subset S$ ist \emph{abgeschlossen}, wenn $\not\exists j \in J, i \in S \setminus J : j \rightsquigarrow i$.
Die Markov-Kette $(X_n)$ ist \emph{irreduzibel}, falls $S$ nur aus einer Klasse besteht. d.h. $\forall i, j \in S, i \neq j : i \leftrightarrow j$.
\vspace*{2mm}
$J \subset S$ ist abg. gdw. $(p_{ij}, i,j \in J)$ stochastisch ist.
\subsection*{Eintrittszeit eines Zustands}
$T_i := \inf\{ n \in \N : X_n = i \}$ ist die zufällige Eintrittszeit der Markov-Kette in Zustand $i \in S$.
Für $i, j \in S, n \in \N$ sei definiert:
\vspace*{-4mm}
\begin{align*}
f_{ij}^{(n)} :&= \P(T_j = n | X_0 = i) = \P_i(T_j = n) \\
&= \P(X_n = j, X_\nu \neq j (1 \leq \nu < n) | X_0 = i)
\end{align*}
$f_{ij}^{(n)}$ beschreibt die Wahrscheinlichkeit von $i$ startend nach genau $n$ Schritten in $j$ anzugelangen.
$f_{ij}^* := \sum_{n=0}^\infty f_{ij}^{(n)} = \P_i(\exists n \in \N : X_n = j)$
\vspace*{2mm}
Ein Zustand $i \in S$ mit $f_{ii}^* = 1$ ist \emph{rekurrent}.
Gilt $f_{ii}^* \neq 1$ so ist $i \in S$ \emph{transient}.
$\forall n \in \N, i, j \in S : p_{ij}^{(n)} = \displaystyle\sum_{k=1}^n f_{ij}^{(k)} p_{jj}^{(n-k)}$
Zustand $i \in S$ ist rekurrent gdw. $\displaystyle\sum_{n = 0}^\infty p_{ii}^{(n)} = \infty$.
\subsubsection*{Solidaritätsprinzip}
Ist Zustand $i \in S$ rekurrent bzw. transient, so ist $\forall j \in K(i)$ seiner Klasse rekurrent bzw. transient.
\vspace*{2mm}
Liegen $i, j \in S$ in der selben rekurrenten Klasse, so gilt: $f_{ij}^* = f_{ji}^* = 1$.
\subsubsection*{Abgeschlossenheit}
Ist eine Klasse $K \subseteq S$ rekurrent so ist $S$ abgeschlossen, d.h. $(p_{ij}, i,j \in K)$ ist stochastisch.
\vspace*{2mm}
Ist eine Klasse $K \subseteq S$ abgeschlossen und endlich, so ist $K$ rekurrent.
\section*{Absorptionswahrscheinlichkeiten}
Zustandsmenge $S$ ist zerlegbar in rekurrente Klassen $K_1, \dots, K_m$ und eine Menge transienter Zustände $T$ s.d. $S = T \cup K_1 \cup \cdots \cup K_m$.
\vspace*{1mm}
Sei $\tau = \inf\{ n \geq 0 | X_n \notin T\}$ die Austrittszeit aus der transienten Menge, d.h. der Zeitpunkt der Absorption in eine der rekurrenten Klassen.
\vspace*{1mm}
Sei $i \in T, k \in T^c$ und $u_{ik} = \P_i(X_\tau = k)$.
\vspace*{2mm}
Für $i \in T, j \in T^c$ gilt: $u_{ij} = \displaystyle\sum_{k \in T} p_{ik} u_{kj} + p_{ij}$
\section*{Stationäre Verteilungen}
Sei $(X_n)$ MK mit Übergangsmatrix $P$. Ein Maß $\nu : S \to \R_{\geq 0}$ ist \emph{invariant} für $P$, falls $\nu \cdot P = \nu$ d.h:
$\displaystyle\sum_{i \in S} \nu(i) \cdot p_{ij} = \nu(j)$ für $j \in S$
Ist $\nu$ eine Verteilung (d.h. $\sum_{i \in S} \nu(i) = 1$) und invariant für $P$, so ist $\nu$ eine \emph{stationäre Verteilung}.
\vspace*{1mm}
Eine mit stationärer Verteilung $\nu$ gestartete MK hat zu jedem Zeitpunkt Verteilung $\nu$:
$\P_\nu(X_n = j) = \sum_{i \in S} \nu(i) \cdot p_{ij}^{(n)} = \nu(j)$
|
