\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{Informationssysteme - Übungsblatt 3}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Mi, 14-16 Uhr, Andreas Kaster
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\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}
	}

\maketitle

\newpage

\section*{Aufgabe 3.2}

\subsubsection*{(a)}
\begin{itemize}
	\item Die Kette ist reduzibel, da die Zustände 1 und 2 nicht von den Zuständen 3, 4 und 5 erreichbar sind.
	\item Die Kette ist periodisch, da für den Zustand 1 die einzige Rekurrenz über den Zustand 2 in $2n$ Schritten ist. Der größte gemeinsame Teiler aller Rekurrenzwerte von Zustand 1 ist $GGT(2n) = 2$ für $n=1,2,...$.
\end{itemize}

\subsubsection*{(b)}
\begin{itemize}
	\item Die Kette ist irreduzibel, da alle Zustände von jedem anderen Zustand mit positiver Wahrscheinlichkeit erreichbar sind.
	\item Jeder Zustand kann in nur 3 Schritten erreicht werden ($GGT(3n) = 3$ für $n=1,2,...$). Daher ist die Kette periodisch.
	\item Die Kette ist nicht ergodisch, da sie nicht aperiodisch ist.
\end{itemize}

\subsubsection*{(c)}
\begin{itemize}
	\item Die Kette ist irreduzibel, da alle Zustände von jedem anderen Zustand mit positiver Wahrscheinlichkeit erreichbar sind.
	\item Die Kette ist aperiodisch. Alle Zustände haben die Periode 1. Die Rekurrenzwerte der Zustände 1 und 3 sind $2n$ und $3n$. Es gilt: $GGT(2,3) = 1$. Die Rekurrenzwerte von Zustand 2 sind $3n$ und $5n$. Es gilt: $GGT(3,5) = 1$.
	\item Die Kette ist ebenfalls homogen, da alle Übergangswahrscheinlichkeiten von $n$ unabhängig sind. Somit ist die Kette positiv rekurrent und ergodisch.
\end{itemize}

\subsubsection*{(d)}
\begin{itemize}
	\item Die Kette ist reduzibel, da der Zustand 1 nicht von den anderen Zuständen erreicht werden kann.
	\item Sie ist aperiodisch, da man von den Zuständen 2, 3 und 4 Rekurrenzwerte $\ge 2$ für alle Pfadlängen finden kann. Zustand 1 besitzt keinen Rekurrenzwert.
	\item Sie ist nicht ergodisch, da sie nicht irreduzibel ist.
\end{itemize}

\section*{Aufgabe 3.3}

\subsubsection*{(a)}
Um zu beweisen, dass die angegebene Kette ergodisch ist, wird wieder die folgende Tatsache zur Hilfe genommen: \\
Eine Markov-Kette ist genau dann ergodisch, wenn sie irreduzibel, aperiodisch, homogen und positiv rekurrent ist. \\
Zeige nun also die Teilaussagen:
\begin{itemize}
	\item Die Kette ist irreduzibel, da alle Zustände von jedem anderen Zustand mit positiver Wahrscheinlichkeit erreichbar sind.
	\item Die Kette ist aperiodisch, da es eine Schleife in jedem Zustand gibt, die zu diesem selbst führt. Somit braucht man von jedem Zustand zu einem anderen beliebig viele Schritte, bevor man wieder zum Ausgangszustand zurückkehrt. Daher kann man alle Rekurrenzwerte größer 1 finden und es gilt: $GGT(2,3,4,...) = 1$.
	\item Die Kette ist homogen, da alle Übergangswahrscheinlichkeiten von $n$ unabhängig sind.
	\item Die Kette ist positiv rekurrent und letztendlich ergodisch, da sie einen endlichen Zustandsraum sowie die oben aufgeführten Eigenschaften besitzt.
\end{itemize}

\subsubsection*{(b)}
Unter einer Zustandswahrscheinlichkeit versteht man die Summe aller eingehenden Übergangswahrscheinlichkeiten multipliziert mit den Zustandswahrscheinlichkeiten des Vorgängerzustandes. Klar ist, dass die Summe aller Zustandswahrscheinlichkeiten 1 ergeben muss. \\
Da die Kette ergodisch ist, existieren stationäre Zustandswahrscheinlichkeiten $\pi_j$. Diese konvergieren zu $\displaystyle \pi_j = \lim_{n \to \infty} \pi_j^{(n)}$. \\
Für die gegebene Markov-Kette erhalten wir:
\begin{eqnarray*}
	\pi_1 & = & 0.5 \pi_1 + 0.1 \pi_2 \\
	\pi_2 & = & 0.5 \pi_1 + 0.2 \pi_2 + 0.1 \pi_3 \\
	\pi_3 & = & 0.7 \pi_2 + 0.6 \pi_3 + 0.1 \pi_4 \\
	\pi_4 & = & 0.3 \pi_3 + 0.9 \pi_4 \\
	1 & = & \pi_1 + \pi_2 + \pi_3 + \pi_4
\end{eqnarray*}
Man erhält daraus:
\begin{eqnarray*}
	\pi_1 & = & \frac{1}{5} \pi_2 \\
	\pi_2 & = & \frac{1}{5} \pi_2 + \frac{1}{2} \frac{1}{5}\pi_2 + \frac{1}{10} \pi_3 = \frac{1}{7} \pi_3 \\
	\pi_3 & = & \frac{3}{5} \pi_3 + \frac{7}{10} \frac{1}{7} \pi_3 + \frac{1}{10} \pi_4 = \frac{1}{3} \pi_4 \\
	1 & = & \pi_1 + \pi_2 + \pi_3 + \pi_4 = \frac{1}{5} \frac{1}{7} \frac{1}{3} \pi_4 + \frac{1}{7} \frac{1}{3} \pi_4 + \frac{1}{3} \pi_4 + \pi_4 \\[0.3cm]
	\pi_4 & = & \frac{105}{146} \\
	\pi_3 & = & \frac{1}{3} \cdot \frac{105}{146} = \frac{35}{146} \\
	\pi_2 & = & \frac{1}{7} \cdot \frac{35}{146} = \frac{5}{146} \\
	\pi_1 & = & \frac{1}{5} \cdot \frac{5}{146} = \frac{1}{146} \\
	1 & = & \frac{1}{146} + \frac{5}{146} + \frac{35}{146} + \frac{105}{146}
\end{eqnarray*}

\end{document}
