\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.8 Bedeutung des Eigenwerts $\lambda = 1$ \\
Wir interessieren uns für das Verhalten einer endlichen homogenen Markowkette $(X_n)$ für $n \to \infty$. Für einen Anfangszustand $u_0$ und eine Übergangsmatrix $M = (p_{ij})$ gilt:
\begin{eqnarray*}
	u_1 & = & M u_0 \\
	u_2 & = & M u_1 = M^2 u_0 \\
	& \vdots & \\
	u_n & = & M^n u_0
\end{eqnarray*}
Ist $u_0$ Eigenvektor von $M$ zum Eigenwert $\lambda = 1$, gilt:
$$u_n = M^n u_0 = \lambda^n u_0 = u_0 \quad \forall n \in \SetN$$
d.h. der Zustand $u_0$ ist stabil. \\
Darüber hinaus kann man Folgendes zeigen: \\[0.5cm]
75.9 Satz: (Potenzen stochastischer Matrizen) \\
Sei $M$ eine stochastische Matrix. Genau dann existiert $\lim_{n \to \infty} M^n$, wenn 1 der einzige Eigenwert von $M$ mit Betrag 1 ist. \\
Beweis einer Richtung: \\
Wir zeigen: Sei $\lambda$ ein Eigenwert von $M$ mit $|\lambda| = 1$. Falls $\lim_{n \to \infty} M^n$ existiert, ist 1 einziger Eigenwert von $M$ mit Betrag 1. Sei $v \ne 0$ ein Eigenvektor von $M$ zum Eigenwert $\lambda$ mit $|\lambda| = 1$:
$$Mv = \lambda v \Rightarrow M^nv = \lambda^n v \quad \forall n \in \SetN$$
Würde $\lim_{n \to \infty} M^n$ existieren, hätten wir
$$(\lim_{n \to \infty}M^n)v = \lim_{n \to \infty} (M^n v) = \lim_{n \to \infty} (\lambda^n v) = \underbrace{(\lim_{n \to \infty} \lambda^n)}_{=: \mu} v$$
Also würde auch $\mu := \lim_{n \to \infty} \lambda^n$ existieren. Dann wäre auch
$$\mu = \lim_{n \to \infty} \lambda^{n+1} = \lambda \cdot \lim_{n \to \infty} \lambda^n = \lambda \cdot \mu$$
Wegen $|\lambda| = 1$ ist auch $|\lambda^n| = 1$ und somit auch $|\mu| = 1 \ne 0$. Aus $\mu = \lambda \mu$ folgt damit $\lambda = 1$. \QED \\[0.5cm]
75.10 Beispiel: \\
Wir betrachten eine stochastische Matrix, die Eigenwert $\lambda$ mit $|\lambda|=1$ besitzt, aber $\lambda \ne 1$ sein kann:
$$M = \left(\begin{array}{cccc}0 & 1 & & \\ & \ddots & \ddots & \\ & & \ddots & 1 \\ 1 & & & 0\end{array}\right) \in \SetR^{k \times k}$$
beschreibt eine zyklische Vertauschung. \\
Sei $$\alpha := e^{\frac{2\pi i}{k}} = \cos \left(\frac{2\pi}{k}\right) + i \sin \left(\frac{2\pi}{k}\right) \quad (\Rightarrow \alpha^k = e^{2\pi i} = 1)$$
Setzen wir
$$v_j := \left(\begin{array}{c}\alpha^{1_j} \\ \alpha^{2_j} \\ \vdots \\ \alpha^{(k-1)_j}\end{array}\right) \quad 0 \le j \le k-1$$
so folgt wegen $\alpha^k=1$
$$M v_j = \left(\begin{array}{c}\alpha^j \\ \alpha^{2j} \\ \vdots \\ \alpha^{kj}\end{array}\right) = \alpha^j v_j$$
Also sind $1, \alpha^1, \alpha^2,..., \alpha^{k-1}$ sämtliche Eigenwerte von $M$. Alle haben Betrag 1. \\
Klar: $M^n$ konvergiert nicht für $n \to \infty$. \\[0.5cm]
75.11 Def.: \\
Eine endliche homogene Markowkette $(X_n)$ ist im Gleichgewicht, falls zu ihrer Übergangsmatrix $M=(p_{ij})$ ein Zustand $u$ existiert mit
$$Mu = u$$
d.h. $u$ ist Eigenvektor von $M$ zum Eigenwert 1. Zusätzlich muss gelten:
$$\sum_{i=1}^k u_i = 1, \quad u_i \ge 0 \quad \forall i \in \{1,...,k\}$$
75.12 Beispiel \\
Im Beispiel 75.3 war die Übergangsmatrix gegeben durch
$$M = \left(\begin{array}{cc}0.8 & 0.1 \\ 0.2 & 0.9\end{array}\right)$$
Berechnung der Eigenwerte:
\begin{eqnarray*}
	0 & = & \left|\begin{array}{cc}0.8 - \lambda & 0.1 \\ 0.2 & 0.9 - \lambda\end{array}\right| = (0.8-\lambda)(0.9 - \lambda) - 0.02 \\
	& = & 0.72 - 0.8\lambda - 0.9\lambda + \lambda^2 - 0.02 \\
	& = & \lambda^2 - 1.7 \lambda + 0.7 \\
	\lambda_{1,2} & = & \frac{1.7 \pm \sqrt{1.7^2 - 4 \cdot 0.7}}{2} = \frac{1.7 \pm \sqrt{2.89-2.8}}{2} \\
	& = & \frac{1.7 \pm 0.3}{2} \\
	\lambda_1 & = & 1 \\
	\lambda_2 & = & 0.7
\end{eqnarray*}
Eigenvektor zu $\lambda_1=1$
$$\left(\begin{array}{cc}-0.2 & 0.1 \\ 0.2 & -0.1\end{array}\right) \left(\begin{array}{c}x \\ y\end{array}\right) = \left(\begin{array}{c}0 \\ 0\end{array}\right)$$
\begin{eqnarray*}
	0.2x & = & 0.1 y \\
	\Rightarrow x & = & \frac{y}{2} \\[0.5cm]
	v & = & \left(\begin{array}{c}\alpha \\ 2 \alpha\end{array}\right), \quad \alpha \ne 0
\end{eqnarray*}
Zusätzlich muss gelten:
$$\alpha \ge 0, \quad \alpha + 2\alpha = 1 \Rightarrow \alpha = \frac{1}{3}$$
$$\Rightarrow v = \left(\begin{array}{c}\frac{1}{3} \\[0.3cm] \frac{2}{3}\end{array}\right) \quad \text{Gleichgewichtszustand}$$
$\frac{1}{3}$ der Personen wohnt in Kalifornien, $\frac{2}{3}$ außerhalb. \\[0.3cm]
Wann ist es möglich, bei einer Markowkette von einem Zustand in einem beliebigen anderen zu gelangen? \\[0.5cm]
75.13 Def.: \\
Eine stochastische Matrix $M=(p_{ij}) \in \SetR^{k \times k}$ heißt transitiv (irreduzibel), wenn man von jedem Zustand $n$ mit positiver Wahrscheinlichkeit in jeden Zustand $m$ in endlich vielen Schritten gelangen kann: \\
Es gibt ein $r$, so dass für $M^r =: B = (b_{ij})$ gilt:
$$b_{mn} > 0$$
75.13 Praktisches Kriterium für Irreduzibilität \\
Man zeichnet zur Übergangsmatrix $M=(p_{ij})$ einen gerichteten Graphen: Ist $p_{ij} > 0$, zeichnet man einen Pfeil von $j$ nach $i$. Fall man von jedem Zustand längs solcher Pfeile zu jedem anderen Zustand gelangt, ist $M$ irreduzibel, andernfalls nicht. \\[0.5cm]
75.14 Beispiele
\begin{enumerate}[(a)]
	\item $$M = \left(\begin{array}{ccc}\frac{1}{2} & \frac{1}{2} & \frac{1}{4} \\ \frac{1}{4} & 0 & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{2}\end{array}\right)$$
		(Graph siehe gescannte Vorlesung) \\
		irreduzibel: Es gibt von jedem Punkt einen Weg zu jedem anderen Punkt. \\
		beachte: Ein Weg darf auch mehrere Pfeile umfassen. Daher führt ein Weg von 2 nach 2.
	\item $$M = \left(\begin{array}{cccc}\frac{3}{4} & \frac{1}{4} & 0 & 0 \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 \\0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\ 0 & 0 & \frac{1}{4} & \frac{3}{4}\end{array}\right)$$
		(Graph siehe gescannte Vorlesung) \\
		irreduzibel.
	\item $$M = \left(\begin{array}{ccc}1 & \frac{2}{5} & \frac{1}{4} \\ 0 & \frac{1}{5} & \frac{1}{4} \\ 0 & \frac{2}{5} & \frac{1}{2}\end{array}\right)$$
		(Graph siehe gescannte Vorlesung) \\
		reduzibel: Es führt z.B. kein Weg von 1 nach 2.
\end{enumerate}

\end{document}
