diff options
Start Markov chains digest
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | common/commands.tex | 1 | ||||
| -rw-r--r-- | content/eaz.tex | 6 | ||||
| -rw-r--r-- | content/markov.tex | 107 |
4 files changed, 115 insertions, 1 deletions
@@ -8,6 +8,8 @@ Zum Ende meines nunmehr schon dritten Semesters stehen zusätzlich Zusammenfassu Die resultierenden PDF der in _LaTeX_ gesetzten Quellen der [Analysis](https://static.kummerlaender.eu/media/ana12_zusammenfassung.pdf), [Lineare Algebra](https://static.kummerlaender.eu/media/la12_zusammenfassung.pdf), [Numerik 1](https://static.kummerlaender.eu/media/numa1_zusammenfassung.pdf) sowie [Analysis 3](https://static.kummerlaender.eu/media/ana3_zusammenfassung.pdf) Kurzzusammenfassungen stehen auf meiner Webseite zum Download bereit. +Zusammenfassungen der Vorlesungen _Einführung in die Algebra und Zahlentheorie_ sowie _Markov-Ketten_ sind in Arbeit. + ## Generierung # topics: analysis, analysis_3, lineare_algebra, numerik_1 diff --git a/common/commands.tex b/common/commands.tex index 0853848..0162f8e 100644 --- a/common/commands.tex +++ b/common/commands.tex @@ -3,7 +3,6 @@ \newcommand{\K}{\mathbb{K}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} -\newcommand{\Primes}{\mathbb{P}} \newcommand{\powerset}[1]{\mathcal{P}(#1)} \newcommand{\skp}[1]{\langle #1 \rangle} 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. |