\documentclass{beamer}

\usepackage{beamerthemesplit}
\usepackage[ngerman]{babel}
\usepackage[utf8]{inputenc}

\newtheorem*{thm*}{Theorem} 
\newtheorem*{lem*}{Lemma}
\newtheorem*{cor*}{Corollary}
\newtheorem*{def*}{Definition}
\newtheorem*{proof*}{Beweis}


\newcommand{\essinf}{\hop{\rm ess\,inf}}
\newcommand{\esssup}{\mathop{\rm ess\,sup}}
\renewcommand{\P}{\mathop{\mathbb{P}}}
\newcommand{\R}{\mathop{\mathbb{R}}}
\newcommand{\IE}{\mathop{\mathbb{E}}}
\renewcommand{\IE}{\mathbb{E}}
\newcommand{\F}{\mathop{\mathcal{F}}}
\newcommand{\IN}{\mathop{\mathbb{N}}}
\newcommand{\IR}{\mathop{\mathbb{R}}}
\newcommand{\IP}{\mathop{\mathbb{P}}}
\newcommand{\too}{\mathop{\longrightarrow}}
% black slide, to show somethin on the blackboard
\newcommand{\blackboard}{
\setbeamercolor{normal text}{bg=black}
\frame[plain]
{
BLACKBOARD
}
\setbeamercolor{normal text}{bg=white}
}


\setbeamertemplate{navigation symbols}{} % no navigation symbols

\title[Konvergenz ins Gleichgewicht]{Station??re Verteilungen \& \\ Konvergenz ins Gleichgewicht bei \\ Markov-Ketten in diskreten Zustandsr??umen}
\date{\today}
\author{Gabriel Preu??}

\begin{document}

\frame{\titlepage}

\section[Inhalt]{}


\frame{\tableofcontents}

\section{station??re Verteilungen}
\frame{\tableofcontents[currentsection]}

%\frame{
% \begin{thm*}[Verschiebungsinvarianz] \pause
%    Sei $(X_n)_{n \in \IN }$ Markov($\lambda,P$), $\lambda$ station??re Verteilung, dann gilt: \pause
%   \begin{align*} 
%   &\quad\, \P[X_n = x_n, \ldots, X_{n+m}= x_{n+m}] & \\ 
%   & =  \P[X_n = x_n]p_{x_m,x_{m+1}} \ldots p_{x_{n+m-1}x_{n+m}} &\\ 
%   & = \lambda (x_n) p_{x_m,x_{m+1}}\ldots p_{x_{n+m-1}x_{n+m}} &\\ 
%   &= \P[X_0=x_m,\ldots, X_m=x_{n+m}] 
% \end{align*}
%\pause
%D.h. die Verteilung von $(X_{n+m})$ ist gleich der Verteilung von $(X_n)$
%
%D.h. $(X_{n+m})$ ist ebenfalls Markov($\lambda,P$)
%  \end{thm*}
%}

\frame{
Ziel des Abschnitts: Jede irreduzible, rekurrente stochastische Matrix hat eine positive, station??re Verteilung.\\ \pause
Offene Frage: Eindeutigkeit? \\ \pause

\vspace*{2mm}Existenz einer station??ren Verteilung klar, da: 
\[P \begin{pmatrix}1 \\ \vdots \\ 1 \end{pmatrix} = \begin{pmatrix}1 \\ \vdots \\ 1 \end{pmatrix} \]
d.h. es gibt Spaltenvektor zum EW 1 \\ \pause
	und damit auch Zeilenvektor $\pi$ zum EW 1, d.h. \pause
\[ \exists\pi:\quad \pi P = \pi \]
}

\frame{
  \begin{thm*}[Kriterium f??r station??re Verteilung]
Sei I ein endlicher Zustandsraum und f??r ein $i\in I$ gilt:
    \begin{align*}
      &\lim_{n\to\infty}p_{ij}^{(n)} = \pi_j \quad\forall\,j\in I    \end{align*} 
Dann ist $\pi = (\pi_j:\; j\in I)$ station??re Verteilung \pause
  \[
\sum_{j\in I}\pi_j \pause=  \sum_{j\in I}\lim_{n\to\infty}p_{ij}^{(n)} \pause= \lim_{n\to\infty}\sum_{j\in I}p_{ij}^{(n)} \pause= 1
  \]
d.h. $\pi$ ist Verteilung mit \pause
\[ 
	\sum_{k\in I}\pi_kp_{kj} \pause= \sum_{k\in I}\lim_{n\to\infty}p_{ik}^{(n)}p_{kj} \pause= \lim_{n\to\infty}\sum_{k\in I}p_{ik}^{(n)}p_{kj} \pause= 	\lim_{n\to\infty}p_{ij}^{(n+1)}  \pause= \pi_j 
\]
d.h. $\pi$ ist station??r bzgl P
  \end{thm*}
}

\frame{
\frametitle{Anmerkung}
Bei "Random Walks" (Symmetrischer Irrfahrt) gilt zwar $p_{ij}^{(n)} \to 0$, d.h. es wird irgendwann station??r, aber $\sum \pi_j \not= 1$, d.h. $\pi$ ist keine Verteilung.
}

\frame{
 \frametitle{Definition}
\begin{def*}[Aufenthaltszeit]
Die Aufenthaltszeit im Zustand i, bevor man den Zustand k erneut erreicht, ist definiert als 
\[ \gamma_i^k := {\IE}_k\sum_{n=0}^{T_k - 1} 1_{\{X_n=i\}} \]
\end{def*}
}

\frame{
\begin{thm*}[Eigenschaften der Aufenthaltszeit]
Sei P irreduzible und rekurrente stochastische Matrix, dann gilt: 
 \begin{align*}
   \onslide<1->{(i)&\quad \gamma_k^k = 1} \\
   \onslide<2->{(ii)&\quad \gamma^k  = (\gamma_i^k: \; i\in I) \text{ erf??llt } \gamma^kP = \gamma^k } \\
   \onslide<3->{(iii)&\quad 0 < \gamma_i^k < +\infty \quad \forall\,i\in I }
 \end{align*}
\pause\pause\pause
\end{thm*}
Anmerkung: (i) $\checkmark $
}

\frame{
 \frametitle{Beweis von (ii)}
Da P rekurrent, gilt $T_k < +\infty$ und weiterhin ${\IP}_k(X_0 = X_{T_k} = k) = 1$ gilt 
\begin{align*}
\onslide<1->{\gamma_j^k &= {\IE}_k\sum_{n=0}^{T_k - 1} 1_{\{X_n=j\}}} \onslide<2->{&&= {\IE}_k\sum_{n=1}^{T_k} 1_{\{X_n=j\}} }\\
\onslide<3->{&= {\IE}_k\sum_{n=1}^{\infty} 1_{\{X_n=j, n\le T_k \}} } \onslide<4->{&&= \sum_{n=1}^{\infty} \sum_{i\in I}{\P}_k(X_{n-1}=i,X_n=j, n\le T_k )}\\
\onslide<5->{&= \sum_{i\in I}p_{ij}{\IE}_k\sum_{m=0}^{\infty} 1_{\{X_m=i, m\le T_k -1\}}} \onslide<6->{&&=  \sum_{i\in I}p_{ij}{\IE}_k\sum_{m=0}^{T_k - 1} 1_{\{X_m=i\}} }\\
\onslide<7->{&= \sum_{i\in I}\gamma_i^kp_{ij}\quad\text{d.h. $\gamma$ ist station??r} &&\checkmark}
\end{align*}
}

\frame{
 \frametitle{ Beweis von (iii)}
Da P irreduzibel gilt:
\[  \forall\,i,j\;\exists\,n,m\in\IN:\quad p_{ik}^{(n)} > 0, p_{kj}^{(m)} > 0 \]
\begin{align*}
\onslide<1->{\gamma_j^k &&\overbrace{=}^{(ii)}\quad \sum_{i\in I}\gamma_i^kp_{ij}^{(m)} &&\ge \gamma_k^kp_{kj}^{(m)} &&> 0} \\
\onslide<2->{+\infty > \gamma_k^k &&\overbrace{=}^{(ii)}\quad\, \sum_{i\in I}\gamma_i^kp_{ik}^{(n)} &&\ge \gamma_j^kp_{jk}^{(n)}} 
\end{align*}
\pause \pause
\[ \Rightarrow 0 < \gamma_j^k < +\infty \checkmark \]
}

\frame{
\begin{lem*}[ohne Beweis]
Sei P irreduzibel, $\lambda$ station??res Ma?? mit $\lambda_k = 1$, dann gilt
\[ \lambda \ge \gamma^k \]
Ist P rekurrent, so gilt sogar echte Gleichheit.
%\begin{align*}
%	\lambda_j &= \sum_{i_1\in I}\lambda_{i_1}p_{i_1j} = \sum_{i_1 \not= k}\lambda_{i_1}p_{i_1j} + p_{kj},\; \lambda_{i_1} = \sum_{i_2 \not= k}\lambda_{i_2}p_{i_1i_2} + p_{ki_2} \\
%	\lambda_j &= \sum_{i_1,i_2 \not= k}\lambda_{i_2}p_{i_2i_1}p{i_1j} + \big(p_{kj} + \sum_{i_1 \not=k}p_{ki_1}p_{i_1j}\big) \\
%	\vdots \\
%	\lambda_j &= \sum_{i_1,\ldots,i_n \not=k} \lambda_{i_n}p_{i_ni_{n-1}}\ldots p_{i_1j} \\
%		    &\quad + \big(p_{kj} + \sum_{i_1\not=k}p_{ki_1}p_{i_1j} + \ldots + \sum_{i_1,\ldots,i_{n-1}\not=k}p_{ki_{n-1}}\ldots p_{i_2i_1}p_{i_1j}\big)
%\end{align*}
\end{lem*}
}

\frame{
\begin{def*}[positiv rekurrent]
Wir erinnern uns: ${\IP}_i(X_n = i \text{ f??r unendlich viele n}) = 1 \Leftrightarrow {\IP}_i(T_i < +\infty) = 1$ \\ \pause
Ist zus??tzlich die mittlere R??ckkehrzeit 
\[ m_i := {\IE}_i(T_i) \]
endlich, so heisst der Zustand i positiv rekurrent. \\ \pause
Andernfalls nennen wir i nullrekurrent
\end{def*}
}

\frame{
\begin{thm*}
Sei P irreduzibel, dann sind ??quivalent:
\begin{align*}
\onslide<1->{(i)&\; \text{jeder Zustand ist positiv rekurrent}} \\
\onslide<2->{(ii)&\; \text{ein Zustand i ist positiv rekurrent}} \\
\onslide<3->{(iii)&\; P\text{ hat eine station??re Verteilung $\pi$ mit }\pi_i = m_i^{-1}}
\end{align*}
\pause\pause\pause
Anmerkung: $(i) \Rightarrow (ii) \checkmark$
\end{thm*}
}

\frame{
\frametitle{Beweis (ii) $\Rightarrow$ (iii)}
Ist i positiv rekurrent, so insbesondere rekurrent. \\
Dann ist $\gamma^i $ invariantes Ma?? mit 
\[ \sum_{j\in I}\gamma_j^i \pause= {\IE}_i(T_i)  \pause= m_i < +\infty \] \pause
Dann liefert
\[ \pi_j = \frac{\gamma_j^i}{m_i} \] \\
das Gew??nschte und $\pi$ ist station??re Verteilung.
}

\frame{
\frametitle{Beweis (iii) $\Rightarrow$ (i)}
\begin{center}
siehe Tafel 
\end{center}
%Sei k ein beliebiger Zustand. Da P irreduzibel und ${\sum}_{i\in I} \pi_i = 1$ gilt
%\[ \pi_k = \sum_{i\in I}\pi_ip_{ik}^{(n)} > 0 \text{ f??r einige n}\]
%Setze $\lambda_i = \frac{\pi_i}{\pi_k}$, dann ist $\lambda$ ein station??res Ma?? mit $\lambda_k = 1$.
%$\Rightarrow \lambda \ge \gamma^k$ mit
%\[ m_k = \sum_{i\in I}\gamma_i^k \le \sum_{i\in I}\frac{\pi_i}{\pi_k} = \frac{1}{\pi_k} < +\infty \] und k ist positiv rekurrent.
%
%Nun ist P rekurrent, d.h. es gilt sogar $\lambda = \gamma^k$ und die Ungleichung wird zur Gleichung
}

\frame{
 \frametitle{Abschnittsfazit}
 Erinnerung: Ziel war es zu zeigen, dass jede irreduzible, positive rekurrente stochastische Matrix eine positive, station??re Verteilung hat. \\ \pause
Das haben wir mit dem letzten Theorem gezeigt. \checkmark
}

\section{Konvergenz ins Gleichgewicht}
\frame{\tableofcontents[currentsection]}

\frame{
\frametitle{Worum geht es?}
Ziel: Allgemeine Untersuchung vom Grenzverhalten f??r $p_{ij}^{(n)}$. \\ \pause
\vspace{4mm}
Kann man Vorraussagen machen ??ber $\lambda P^n$ f??r $n\to\infty$? \\
\vspace{4mm}
Wissen bisher: Existiert $\lim_{n\to\infty} p_{ij}^{(n)}$ f??r  einen Zustand i, so definiert uns das station??re Verteilung. \\ \pause
\vspace{4mm}
Aber was, wenn nicht? \\ \pause
\vspace{4mm}
Gegenbeispiel:  $P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$
}

\frame{
\begin{def*}[aperiodisch]
Ein Zustand i heisst aperiodisch, wenn gilt:
\[ \exists\,n_0\in\IN:\quad p_{ii}^{(n)} > 0\quad \forall\,n\ge n_0 \]
\pause
$\Rightarrow$ Keine aperiodischen Zust??nde im Gegenbeispiel. \\
\pause
\vspace{4mm}
Existiert ein aperiodischer Zustand und P ist irreduzibel, \\ so sind alle Zust??nde aperiodisch. \\ \pause
\vspace{4mm}
Es gilt sogar: $p_{kl}^{(n)} > 0$ f??r fast alle n und beliebige k,l. 
\end{def*}
}

% // ------------------- Aus Zeitmangel entfernt --------------------- //%

%\frame{
%\begin{thm*}
%Ist P irreduzibel und habe einen nicht periodischen Zustand i, so gilt f??r beliebige andere Zust??nde j,k $p_{jk}^{(n)}$ f??r fast alle n.
%Insbesondere ist somit jeder Zustand nicht periodisch.
%Beweis: \\
%Da P irreduzibel gibt es $r,s \in \IN, P_{ji}^{(r)}>0,p_{ik}^{(s)} > 0$ und es gilt:
%\[ p_{jk}^{(r+n+s)} \ge p_{ji}^{(r)}p_{ii}^{(n)}p_{k}^{(s)} > 0 \]
%f??r fast alle $n \in \IN$
%\end{thm*}
%}

\frame{
\begin{thm*}[Konvergenz ins Gleichgewicht]
Sei P irreduzibel, aperiodisch und habe die station??re Verteilung $\pi$
Dann gilt f??r jede Verteilung $\lambda$ mit $(X_n)_{n\ge 0}$ ist Markov($\lambda,P$)
\[ \P(X_n = j) \to \pi_j \quad n\to\infty\quad \forall\,j\in I \]

insbesondere gilt:

\[ p_{ij}^{(n)} \to \pi_j \quad n\to\infty\quad \forall\,i,j\in I \]
\end{thm*}
}

\section{Beispiele}
\frame{\tableofcontents[currentsection]}

\frame{
Wissen bereits: Symmetrische Irrfahrt besitzt keine station??re Verteilung \\ \pause
Betrachten daher Irrfahrt auf einem Kreis \\ (sozusagen: Symmetrische Irrfahrt "mod n") \\ \pause
\vspace{4mm}
Beispiel: $n = 2$ \\ \pause
\vspace{4mm}
\[
P =
    \begin{pmatrix}
	 0 & \frac{1}{2} & \frac{1}{2} \\
	\frac{1}{2} & 0 & \frac{1}{2} \\ 
	\frac{1}{2} & \frac{1}{2} & 0 
      \end{pmatrix} \]
} 

\end{document}
