\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

\thispagestyle{empty}

\title{}
\author{}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{../#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\noindent §75: MARKOWKETTEN \\[0.8cm]
75.1 Motivation \\
Der Zustand eines Systems zur Zeit $n \in \SetN$ werde durch eine Zufallsvariable $X_n$ bbeschrieben und soll nur von $X_{n-1}$ abhängen (nicht jedoch von früheren Zuständen $X_{n-2}, X_{n-3},...$). Wir möchten das zeitliche Verhalten dieses Systems studieren, insbesondere das Langzeitverhalten für $n \to \infty$. Prozesse dieser Art sind in der Informatik z.B. bei der Untersuchung der Auslastung von Servern wichtig (Warteschlangenmodelle). \\[0.5cm]
75.2 Def.: \\
Ein stochastischer Prozess ist eine Familie ($X_t$) von Zufallsvariablen mit $t \in \SetR$ oder $t \in \SetN$. Wir denken dabei an $t$ als Zeitparameter, der kontinuierlich oder diskret ist. Ein diskreter stochastischer Prozess $(X_n), n \in \SetN$ heißt Markowkette, wenn die Verteilung von $X_n$ bei gegebenen $X_{n-1}$ nicht von den früheren Verteilungen $X_k, k < n-1$ abhängt:
$$P(X_n=i_n | X_{n-1} = i_{n-1}, X_{n-2} = i_{n-2}, ...) = P(X_n = i_n | X_{n-1} = i_{n-1})$$
Bemerkung: \\
Wichtig sind insbesondere Markowketten, die nur endlich viele Zustände annehmen:
$$P(X_n \in \{1,...,k\}) = 1$$
75.3 Beispiel mit Definition: \\
Jedes Jahr ziehen $10\%$ der Bevölkerung außerhalb Kaliforniens nach Kalifornien und $20\%$ der Bevölkerung Kaliforniens zieht aus. \\
Eine Person findet sich im Jahr $n-1$ in einem von zwei Zuständen:
$$X_{n-1} := \left\{\begin{array}{cl}1 & \text{Person wohnt in Kalifornien} \\ 2 & \text{Person wohnt nich in Kalifornien}\end{array}\right.$$
Der Zustand im Jahr $n$ lässt sich ann durch ein graphisches Modell mit Übergangswahrscheinlichkeiten beschreiben: \\
(Grafik siehe gescannte Vorlesung) \\
Sei $p_{ij}^n$ die Wahrscheinlichkeit, dass ein Zustand $j$ zur Zeit $n-1$ in den Zustand $i$ zur Zeit $n$ übergeht (z.B. $p_{12}^n = 0.1$)
$$p_{ij}^n = P(X_n = i | X_{n-1} = j)$$
Wir definieren die Matrix der Übergangswahrscheinlichkeiten (Übergangsmatrix) durch
$$M_n := (p_{ij}^n) \in \SetR^{k \times k} \quad \text{(bei } k \text{ Zuständen)}$$
Im Beispiel:
$$M_n = \left(\begin{array}{cc}0.8 & 0.1 \\ 0.2 & 0.9\end{array}\right)$$
Die Verteilung von $X_n$ auf die Zustände $1,...,k$ werde durch einen Vektor $u_n \in \SetR^k$ beschrieben:
$$u_n = \left(\begin{array}{c}u_{n_1} \\ \vdots \\ u_{n_k}\end{array}\right) \in \SetR^k$$
Dann berechnet sich $u_n$ aus $u_{n-1}$ durch:
$$u_n = M_n u_{n-1}$$
Sind im Beispiel zur Zeit $n-1$ $60\%$ der Bevölkerung außerhalb Kaliforniens, gilt:
\begin{eqnarray*}
	u_{n-1} & = & \left(\begin{array}{c}0.4 \\ 0.6\end{array}\right) \\
	\Rightarrow u_n & = & \left(\begin{array}{cc}0.8 & 0.1 \\ 0.2 & 0.9\end{array}\right) \left(\begin{array}{c}0.4 \\ 0.6\end{array}\right) = \left(\begin{array}{c}0.38 \\ 0.62\end{array}\right)
\end{eqnarray*}
Im Jahr $n$ leben also $62\%$ außerhalb Kaliforniens. \\[0.5cm]
75.4 Def.: \\
Eine Markowkette ($X_n$) heißt homogen oder Kette mit stationären Übergangswahrscheinlichkeiten, wenn die Übergangsmatrix $M_n$ unabhängig von der Zeit $n$ ist:
$$M_n = M \quad \forall n \in \SetN$$
75.5 Bemerkungen:
\begin{enumerate}[(a)]
	\item Beispiel 75.3 beschreibt eine homogene Markowkette.
	\item Wir nennen eine Matrix $A=(a_{ij}) \in \SetR^{k \times k}$ eine stochastische Matrix, wenn alle Einträge nicht negativ sind und alle Spaltensummen 1 sind:
		\begin{eqnarray*}
			a_{ij} & \ge & 0 \quad \forall i,j \\
			\sum_{i=1}^k a_{ij} & = & 1 \quad \forall j
		\end{eqnarray*}
		Übergangsmatrizen sind Beispiele für stochastische Matrizen.
	\item In der Stochastikliteratur werden oft Zeilenvektoren $u_n$ betrachtet, und man definiert $p_{ij}$ als die Übergangswahrscheinlichkeit von Zustand $i$ nach Zustand $j$. Dann ist
	$$u_n = u_{n-1} M_n$$
	und stochastische Matrizen haben Zeilensumme 1.
\end{enumerate}
75.6 Zustandsbeschreibung endlicher homogener Markowketten \\
(Zeichnung siehe gescannte Vorlesung)
Def.: \\
Sei $(X_n)$ eine endliche homogene Markowkette. Ein Zustand $i$ heißt
\begin{enumerate}[(a)]
	\item transient, wenn $P(X_m \ne i \; \forall m>n | X_n = i) > 0$ (kann verlassen werden)
	\item rekurrent, wenn $P(X_m \ne i \; \forall m>n | X_n = i) = 0$ (mit Wahrscheinlichkeit 1 kehren wir zurück)
	\item periodisch mit Periode $l$, wenn $P(X_{n+l} = i | X_n = i) = 1$
\end{enumerate}
Eine Menge $I$ von Zuständen heißt absorbierend, wenn
$$P(X_{n+1} \in I | X_n \in I) = 1$$
Um das Zeitverhalten von Markowketten zu verstehen, müssen wir stochastische Matrizen näher untersuchen. \\[0.5cm]
75.7 Satz: (Eigenwerte stochastischer Matrizen) \\
Sei $M=(p_{ij}) \in \SetR^{k \times k}$ eine stochastische Matrix. Dann gilt:
\begin{enumerate}[(a)]
	\item $\lambda = 1$ ist Eigenwert von $M^T$
	\item $|\lambda| \le 1$ für alle Eigenwerte $\lambda$ von $M$ und $M^T$.
	\item $\lambda = 1$ ist einziger Eigenwert von $M^T$ mit $|\lambda|=1$ falls $\underset{j}{\min} p_{jj} > 0$.
\end{enumerate}
Beweis von (a) und (b):
\begin{enumerate}[(a)]
	\item Ist $M$ stochastisch, so hat $A=M^T$ die Zeilensumme 1.
		$$\Rightarrow A \left(\begin{array}{c}1 \\ 1 \\ \vdots \\ 1\end{array}\right) = \left(\begin{array}{c}\sum_j a_{1j} \\ \vdots \\ \sum_j a_{kj}\end{array}\right) = \left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right)$$
		Somit ist $\lambda=1$ Eigenwert von $A$ zum Eigenvektor $\left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right)$.
	\item Betachte die Spaltensummennorm
		$$\|M\|_S := \max \left(\sum_{i=1}^k |p_{ij}|\right) = 1$$
		Dann gilt nach Satz 50.8 für jeden Eigenwert $\lambda$ von $M$:
		$$|\lambda| \le \|M\|_S = 1$$
		Für $M^T$ betrachtet man die Zeilensummennorm.
	\item Nach dem Satz von Gerschgorin (50.10) gibt es zu jedem Eigenwert $\lambda$ von $M^T = (a_{ij})$.
		$$|\lambda - p_{ii}| \le \sum_{j=1, j \ne i}^k |\underbrace{a_{ij}}_{\ge 0}| = 1 - p_{ii}$$
		Also liegt $\lambda$ in dem Kreis mit Mittelpunkt $p_{ii}$ und Radius $1-p_{ii}$. Er berührt den Einheitskreis von innen in $(1,0)$. \\
		$\Rightarrow \lambda = 1$.
\end{enumerate}
Bemerkung: \\
Aussage 75.7 (c) gilt auch für $M$ statt $M^T$.

\end{document}
