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