Start Markov chains digest

2 files changed, 113 insertions, 0 deletions

diff --git a/content/eaz.tex b/content/eaz.tex
index 3ec4720..2680644 100644
--- a/content/eaz.tex
+++ b/content/eaz.tex
@@ -1,3 +1,5 @@
+\newcommand{\Primes}{\mathbb{P}}
+
 \section*{Teilbarkeit}
 
 Sei $n \in \N$. $d \in \N$ ist Teiler von $n$, falls $\exists t \in \N : d \cdot t = n$. Man schreibt $d \mid n$. $n$ ist Vielfaches von $d$.
@@ -442,3 +444,7 @@ Für bel. kommutative Ringe $R$ ist $R[X]$ eine $R$-Algebra vermöge $\sigma : R
 Seien $(A, \sigma), (B, \tau)$ $R$-Algebren.
 
 Ein Ringhomomorphismus $\Phi : A \to B$ ist zugleich Algebrenhomomorphismus, wenn $\Phi \circ \sigma = \tau$ gilt.
+
+\section*{Quotientenkörper}
+
+
diff --git a/content/markov.tex b/content/markov.tex
new file mode 100644
index 0000000..2ed1e30
--- /dev/null
+++ b/content/markov.tex
@@ -0,0 +1,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.