aboutsummaryrefslogtreecommitdiff
path: root/content/markov.tex
blob: 2ed1e30a3227a341ad4f668bd22fd178935ce73d (plain)
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
\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.

\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}.

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.