\documentclass[a4paper, 12pt]{article}
\usepackage[left = 3cm, right=3cm, top=2cm, bottom=2.5cm, marginparwidth=3cm, marginparsep= 0.75cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[ngerman]{babel}
\usepackage{xspace}
\usepackage{mathtools,amsmath,amsfonts,amsthm}
\usepackage{enumerate}
\usepackage{systeme}
\usepackage{multicol}
\usepackage{xfrac}

\usepackage{marginnote}
\usepackage{hyperref}

\usepackage{mathtools}

\DeclarePairedDelimiterX{\infdivx}[2]{(}{)}{%
  #1\;\delimsize\|\;#2%
}
\newcommand{\D}{D\infdivx}

\newcommand{\punkte}[1]{\marginnote{\textbf{\footnotesize (#1 Pkt.)}}}

\newcommand{\CC}{\mathbb{C}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\VV}{\mathbb{V}}
\newcommand{\ZZ}{\mathbb{Z}}

\newcommand{\Ac}{\mathcal{A}}
\newcommand{\Pc}{\mathcal{P}}

\let\vphi\phi
\renewcommand{\phi}{\varphi}

\let\vtheta\theta
\renewcommand{\theta}{\vartheta}
\newcommand{\eps}{\varepsilon}

\newcommand{\Acal}{\mathcal{A}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Pcal}{\mathcal{P}}
\newcommand{\Xcal}{\mathcal{X}}
\newcommand{\Ccal}{\mathcal{C}}
\newcommand{\Ycal}{\mathcal{Y}}
\newcommand{\stcomp}[1]{{#1}^{\mathsf{c}}}

\newcommand{\Prob}{\PP}
\newcommand{\Cov}{\operatorname{Cov}}
\newcommand{\Var}{\VV}
\newcommand{\Expect}{\EE}
\newcommand{\Indicator}{1\!\!1}
\newcommand{\semicolon}{\,;\,}


\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\rang}{rang}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\spec}{spec}
\DeclareMathOperator{\diag}{diag}


\DeclarePairedDelimiter\br{(}{)}
\DeclarePairedDelimiter\abs{|}{|}
\DeclarePairedDelimiter\norm{\|}{\|}
\DeclarePairedDelimiter\innerproduct{\langle}{\rangle}

%\theoremstyle{definition}
\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\renewcommand{\thesection}{\arabic{section}}


\newtheoremstyle{beispiele}% name
{12pt}% Space above
{18pt}% Space below
{}% Body font
{}% Indent amount
{\bfseries}% Theorem head font
{.}% Punctuation after theorem head
{.5em}% Space after theorem head
{}% Theorem head spec (can be left empty, meaning ‘normal’)
\theoremstyle{beispiele}
\newtheorem{bsp}{Exercise}[section]

\begin{document}

\setcounter{section}{5}

\hrule
\begin{center}
{\Large \textbf{Information Theory SS 2025}} \\[1ex]
\end{center}
\begin{center}
\textbf{\large {Institut für Diskrete Mathematik (5050), TU Graz}}
\end{center}
\begin{center}
\textbf{\large Exercise sheet \thesection\ (22.05.2025)} \\[1ex]
\end{center}  
\hrule

\bigskip

 \begin{bsp} 
	Consider the \textit{Drunkard's walk} Markov chain with state space $\mathcal{X}=\{0,1,\ldots,N\}$ and transition matrix:
	\[\mathbf{P} = \begin{pmatrix}
	1 & 0 & 0 & 0 & \cdots & 0 & 0 \\
	\beta & 0 & \alpha & 0 & \cdots & 0 & 0 \\
	0 & \beta & 0 & \alpha &\cdots & 0 & 0 \\
	\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
	0 & 0 & \cdots & \beta & 0 & \alpha & 0 \\
	0 & 0 & \cdots & 0 & \beta & 0 & \alpha \\
	0 & 0 & \cdots & 0 & 0 & 0 & 1
	\end{pmatrix} \, ,\]
	where $0<\alpha<1$ is the probability of moving one step from position $k$ to position $k+1$, and $\beta=1-\alpha$ is the probability to move from position $k$ to position $k-1$, for $k=1,\ldots,N-1$.
	\begin{enumerate}
		\item Given an initial distribution $(0,\ldots,0,1,0,\ldots,0)$ with $1$ on the $j$-th entry, let $p_j$, for $j=0,\ldots,N$, be the probability that $X_n=N$ for some $n \geq 0$ (the drunkard reaches home). Find a set of linear equations for the $p_j$.
		[{\small{Hint: Express $p_j$ in terms of $p_{j-1}$ and $p_{j+1}$}}]
		\item Compute $p_j$ for the concrete case where $N=3$, $j=1$ and $\alpha=\frac{1}{2}$. 
	\end{enumerate}
\end{bsp} 

\begin{bsp}
	Consider the \textit{Weather in Oz} Markov chain $(X_n)_{n\geq 0}$ with state space $\mathcal{X}=\{c,r,s\}$ (clear, rainy, snowy) and transition matrix:
	$$\mathbf{P} = \begin{pmatrix}
	0 & \sfrac{1}{2} & \sfrac{1}{2} \\
	\sfrac{1}{4} & \sfrac{1}{2} & \sfrac{1}{4} \\
	\sfrac{1}{4} & \sfrac{1}{4} & \sfrac{1}{2} \\
	\end{pmatrix} \, .$$
	\begin{enumerate}
		\item Compute a stationary distribution for the Markov chain.
		\item Compute the entropy rate of the stochastic process.
	\end{enumerate}
\end{bsp}

\begin{bsp}
    Consider the experiment of consecutively rolling a fair die. For $n \geq 1$, let $Z_n$ be the RV representing the number of rolls until `6' appears $n$ times.
	\begin{enumerate}
	\item Is $(Z_n)_{n\geq 1}$ a Markov Chain? 
	\item Is $(Z_n)_{n\geq 1}$ stationary?
	\item Compute the entropy rate of $(Z_n)_{n \geq 1}$.
\end{enumerate}
\end{bsp}

\newpage

 \begin{bsp} ~
     \begin{enumerate}
         \item Prove that for every Markov chain $(X_n)_{n\in\NN}$ the quantity $H(X_0|X_n)$ is non-decreasing in $n \geq 0$.
         \item Show that for any stationary discrete stochastic process $(X_n)_{n\in\ZZ}$, 
         \begin{equation*}
         	H(X_0|X_{-1},\dotsc,X_{-n})=H(X_0|X_1,\dotsc,X_n).
         \end{equation*}
     \end{enumerate}
 \end{bsp}

 \begin{bsp}
 	We are given $2$ coins: when tossed, coin $A$ shows `head' with probability $p$ and `tail' with probability $1-p$, coin $B$ is a fair coin. Consider the following two-stage experiment. At the first stage we choose coin $A$ with probability $q$ and coin $B$ with probability $1-q$. At the second stage we toss repeatedly and independently the chosen coin. Let $X_0$ be the RV taking value $1$ if coin $A$ is chosen and  the value $0$ if coin $B$ is chosen. For $n \geq 1$, let $X_n$ be the RV referring to the outcome of the $n$-th toss: if 'head' shows up then $X_n=1$ and if 'tail' shows up then $X_n=0$.
 	\begin{enumerate}
 		\item For which values of $p$ and $q$ is $(X_n)_{n\geq 1}$ stationary? 
         \item For which values of $p$ and $q$ is $(X_n)_{n\geq 0}$ stationary?
 		\item Compute the entropy rates of $(X_n)_{n\geq 1}$ and $(X_n)_{n\geq 0}$.
 	\end{enumerate}
 \end{bsp} 

 \begin{bsp} \label{ex:MC}
     Let $(X_n)_{n\geq 1}$ be a time-homogeneous Markov chain with state space $\mathcal{X}=\{0,1\}$ and transition probabilities: $p(0|0)=0.3$, $p(1|0)=0.7$, $p(0|1)=0.2$, $p(1|1)=0.8$.
		\begin{enumerate}
			\item Draw the transition graph.
			\item\label{itemb} Compute the stationary distribution $\nu$ of the Markov chain.
			\item Let $\tau^0$ be the return time to $0$ after starting with $X_0=0$. Based on the transition graph, compute $\EE(\tau^0 \mid X_0=0)$ as the sum of an infinite series and then find $\nu(0)$ according to the Ergodic Theorem for Markov Chains. 
			Compare it with what you computed in~\eqref{itemb}.
		\end{enumerate}
		
\end{bsp}
 
\begin{bsp}
	Imagine you are walking on the integers in the direction you are facing (left or right), reversing direction after each step taken with probability $p = 0.2$. You start at $0$ facing to the right. For $n \geq 0$ let $X_n$ be your position at time $n$. 
	\begin{enumerate}
		\item Describe the state space and transition probabilities of this process. Is $(X_n)_{n \geq 0}$ a Markov chain?
		\item What is your expected number of steps taken before reversing direction?
		\item Calculate $H(X_1,\dots,X_n)$.
		\item Find the entropy rate of this process.
	\end{enumerate}
\end{bsp}

\begin{bsp}
	Prove the following generalization of the claim used in the proof of Proposition~3.19:
	
	Let $(X_n)_{n \geq 0}$ be an irreducible time-homogeneous Markov chain with a finite state space $\mathcal{X}$ and transition matrix $P$. 
	If $f : \mathcal{X} \to \RR$ is a harmonic function with respect to $P$ for all $x \in \mathcal{X}$ except for at most one point $x_0 \in \mathcal{X}$, that is, when viewed as a column vector $(P f)_{x} = f(x)$ for all $x \in \mathcal{X} \setminus \{ x_0 \}$,
	then $f = c {\bf 1}$ is constant.
\end{bsp}


\end{document} 