\begin{center}
{\large\bf Exercise sheet 06 -- 16.05.2024}
\end{center}
\hrule
\bigskip

\setcounter{bsp}{23}	% gleich der Nummer des letzten Beispiels des letzten Übungszettels

\begin{bsp}
    Let $(X_n)_{n \geq 0}$ be an irreducible time homogeneous Markov chain with transition matrix $P$ and stationary initial distribution $\nu$. Let $N \in \mathbb{N}$ and consider the stochastic process $(Y_n)_{n=0}^N$ where $Y_n = X_{N-n}$.
    \begin{enumerate}
    \item Show that $(Y_n)_{n=0}^N$ is a Markov chain.
    \item Determine the transition matrix for the chain.
    \item Show that the reversed chain is stationary and determine its stationary distribution.
  \end{enumerate}
 \end{bsp}

 \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}
% Let $X, Y, Z, W$ be random variables on a common state space $\mathcal{X}$ forming the Markov triple $(X,Y,(Z,W))$, that is, \[p(x,y,z,w)=p(x)\,p(y \mid x)\, p(z,w \mid y)\] holds
% for all $x,y,z,w \in \mathcal{X}$. Show that
% \[
% I(X\semicolon Z)+I(X\semicolon W) \leq I(X\semicolon Y)+I(Z\semicolon W).
% \]
% \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.
		%$(X_n)_{n\geq 0}$.
	\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}

% \begin{bsp} \mbox{} \vspace{-\topskip}
%     \begin{enumerate}
%         \item Prove that for every Markov chain $(X_n)_{n\in\N}$ 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\Z}$, 
%         \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}
% 	Let $(X_n)_{n \geq 1}$ be a stochastic process of i.i.d. Bernoulli RVs with distribution $\Prob [X_n=1]=p$ and $\Prob [X_n=0]=1-p$, for $n \geq 1$.
% 	Let $(Y_n)_{n \geq 1}$ be a stationary stochastic process with values in $\{0,1\}$, such that for $n \geq 3$, 
% 	\[Y_n =  X_n  \oplus Y_{n-1} \oplus Y_{n-2},\]
% 	where $\oplus$ is addition modulo 2.
% 	What is the entropy rate of the stochastic process $(Y_n)_{n \geq 1}$?
% \end{bsp}


% \begin{bsp}
%     Let $(X_i)_{i \geq 1}$ be a stochastic process with finite state space $\mathcal{X}$. Show that if one of the limits 
%     \begin{align*}
%         & \lim_{n \to \infty} \frac{1}{n} H(X_{k+1}, \dots, X_{k+n}) \\
%         & \lim_{n \to \infty} \frac{1}{n} H(X_{k+1}, \dots, X_{k+n} \mid X_1, \dots, X_k)
%     \end{align*}
%     exists for some $k \in \N_0$, then both limits exist for every $k \in \N_0$ and all of them coincide.
% \end{bsp}

% \begin{bsp}
% 	We are given two 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} 



% \newpage2
% \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} \mbox{} \vspace{-\topskip}
%     \begin{enumerate}
%         \item Prove that for every Markov chain $(X_n)_{n\in\N}$ 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\Z}$, 
%         \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}
%     Let $(X_i)_{i \geq 1}$ be a stochastic process with finite state space $\mathcal{X}$. Show that if one of the limits 
%     \begin{align*}
%         & \lim_{n \to \infty} \frac{1}{n} H(X_{k+1}, \dots, X_{k+n}) \\
%         & \lim_{n \to \infty} \frac{1}{n} H(X_{k+1}, \dots, X_{k+n} \mid X_1, \dots, X_k)
%     \end{align*}
%     exists for some $k \in \N_0$, then both limits exist for every $k \in \N_0$ and all of them coincide.
% \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 Calculate the entropy rate $h$.
%         \item Given that the Markov chain starts at $X_1=0$, find whether the sequences $w_1,w_2 \in \mathcal{X}^{20}$ are in the typical set $A_{\varepsilon}^{(20)}$, for $\varepsilon= 0.05$:
%         \begin{align*}
%         w_1&= 01001010101101100100 ,\\
%         w_2&= 01111001110111110111 .
%         \end{align*}
%     \end{enumerate}
% \end{bsp}

% \begin{bsp}
% 	Consider again the Markov Chain $(X_n)_{n\geq 1}$ from Exercise \ref{ex:MC} and suppose that $X_1=0$. 
% 	\begin{enumerate}
% 	    \item Find an integer $n$ and a word $w \in \mathcal{X}^{n}$ such that $w$ lies in the typical set $A_{0.005}^{(n)}$.
% 	    \item Given $\epsilon >0$, provide an idea on how to construct a word $w$ lying in the typical set $A_{\epsilon}^{(n)}$ for some integer $n$.
% 	\end{enumerate}
% \end{bsp}

% \begin{bsp}
%     Let $\mathcal{X}=\{a,b,c,d\}$ and 
%     \[
%         C(a)=10, \qquad C(b)=11, \qquad C(c)=00, \qquad C(d)=110.
%     \]
%     \begin{enumerate}
%         \item Show that this code is not prefix free but uniquely decodable.
%         \item Show that there are arbitrarily long words $x_1 \cdots x_n$ such that $C(x_1 \cdots x_n)$ can only be
%         decoded at the very end, that is, that the initial element $x_1$ cannot be recovered from any proper prefix of $C(x_1 \dots x_n)$.
%     \end{enumerate}
% \end{bsp}

% \begin{bsp}
%   Let $X: \Omega \to\mathcal{X}=\{a,b,c,d\}$ be a random variable with
%   \[\mathbb{P}[X=a] = \frac{3}{8}, \qquad \mathbb{P}[X=b] = \frac{2}{8}, \qquad \mathbb{P}[X=c] = \frac{2}{8}, \qquad \mathbb{P}[X=d] = \frac{1}{8}.\]
%   The elements of $\mathcal{X}$ are encoded as follows:
% \[C(a)=00, \qquad C(b)=01,\qquad C(c)=11,\qquad C(d)=001.\]
% \begin{enumerate}
%   \item Is the code $C$ (i) non-singular, (ii) prefix-free, (iii) uniquely decodable?
%   \item Calculate the entropy $H(X)$ and the expected code length $\mathbb{E}(\ell(C))$.
%   \item Give a better code for this random variable (prefix-free, shorter expected length).
% \end{enumerate}
% \end{bsp}

% \begin{bsp}
%     Let $C: \mathcal{X} \to \Sigma=\{0,1,\dots, D-1\}$ be a $D$-ary prefix code on a set $\mathcal{X}$ of cardinality $m$ and suppose that the code word lengths $l_1, \dots, l_m$ satisfy the strict inequality
%     \[
%         \sum_{i=1}^m D^{-l_i} < 1.
%     \]
%     Show that there are arbitrary long strings $w \in \Sigma^*$ which are not code words, that is, $w$ is not the code word of any string in $\mathcal{X}^*$.
% \end{bsp}


% \begin{bsp}
%   Let $X: \Omega \to\mathcal{X}=\{a,b,c,d\}$ be a random variable with
%   \[\mathbb{P}[X=a] = \frac{3}{8}, \qquad \mathbb{P}[X=b] = \frac{2}{8}, \qquad \mathbb{P}[X=c] = \frac{2}{8}, \qquad \mathbb{P}[X=d] = \frac{1}{8}.\]
%   The elements of $\mathcal{X}$ are encoded as follows:
% \[C(a)=00, \qquad C(b)=01,\qquad C(c)=11,\qquad C(d)=001.\]
% \begin{enumerate}
%   \item Is the code $C$ (i) non-singular, (ii) prefix-free, (iii) uniquely decodable?
%   \item Calculate the entropy $H(X)$ and the expected code length $\mathbb{E}(\ell(C))$.
%   \item Give a better code for this random variable (prefix-free, shorter expected length).
% \end{enumerate}
% \end{bsp}

% \begin{bsp}
%     Let $C: \mathcal{X} \to \Sigma=\{0,1,\dots, D-1\}$ be a $D$-ary prefix code on a set $\mathcal{X}$ of cardinality $m$ and suppose that the code word lengths $l_1, \dots, l_m$ satisfy the strict inequality
%     \[
%         \sum_{i=1}^m D^{-l_i} < 1.
%     \]
%     Show that there are arbitrary long strings $w \in \Sigma^*$ which are not code words, that is, $w$ is not the code word of any string in $\mathcal{X}^*$.
% \end{bsp}

% \begin{bsp}\label{ex:huffman}
%   Consider the random variable $X : \Omega \to \{x_1, \dots, x_{10}\}$ with probability distribution 
%   \[
%     p=(\, 0.25,\, 0.12,\, 0.13,\, 0.15,\, 0.03,\, 0.05,\, 0.04,\, 0.13,\, 0.08,\, 0.02\,).
%   \]
%  In a $D$-ary Huffman code at each step we choose $D$ nodes with the lowest probability and construct their parent with probability the sum of the probabilities of the children. Only at the first step we may merge less than $D$ children: 
% 	given that $ |\mathcal{X}| = N$, at the first step we build the parent of $k = 2+(N-2) \!\! \! \mod  \! (D-1)$ children. For example, for $N=19$ and $D=5$ we get $k = 2+ 17 \!\!\mod  4 = 3$.
%   \begin{enumerate}
%     \item Build a binary Huffman code.
%     \item Compute the expected code length of your code and compare it to $H(X)$.
%     \item Build a ternary Huffman code over the alphabet $\Sigma=\{0,1,2\}$.
%     \item Compute the expected code length of your code and compare it to 
%       \[
%       H_3(X)=-\sum_{x \in \mathcal{X}} p(x) \log_3(p(x)).
%       \]
%   \end{enumerate}
% \end{bsp}

% \begin{bsp}
% Let $X,Y$ be random variables with values in $\mathcal{X}=\mathcal{Y}=\{0,1\}$ and let $p_X(0)=q$, $p_X(1)=1-q$. Let $\mathcal{C}=(\mathcal{X},P,\mathcal{Y})$ be the channel with input $X$, output $Y$ and transition matrix
% \[ 
% P=
% \left[
% \begin{array}{cc}
%  1-p & p      \\
%  p & 1-p 
% \end{array}
% \right].
% \]
% \begin{enumerate} 
%     \item Compute $I(X,Y)$ in terms of $p$ and $q$.
%     \item For which values of $p$ is $I(X;Y)$ maximal?
%     \item For which values of $p$ is $I(X;Y)$ minimal?
% \end{enumerate}
% \end{bsp}

% \begin{bsp}
% A channel $\Ccal=(\Xcal,P,\Ycal)$ has a binary input and output alphabet and transition probabilities given by the following matrix:
% \[ 
% P=
% \left[
% \begin{array}{cc}
%  1 & 0      \\
%  1/4 & 3/4 
% \end{array}
% \right].
% \]
% Find the input distribution maximizing $I(X,Y)$ and the channel capacity.
% \end{bsp}

% \begin{bsp}
% Consider two independent discrete channels $\mathcal{C}_1=(\mathcal{X}_1,P_1,\mathcal{Y}_1)$ and $\mathcal{C}_2=(\mathcal{X}_2,P_2,\mathcal{Y}_2)$. We construct a new channel $\Ccal=(\Xcal_1 \times \Xcal_2,\, P,\, \Ycal_1 \times \Ycal_2)$ from $\Ccal_1$ and $\Ccal_2$ such that $(x_1,x_2) \in \Xcal_1 \times \Xcal_2$ will be transmitted in parallel: for $i \in \{1,2\}$ the input $x_i \in \Xcal_i$ is sent to some $y_i \in \Ycal_i$ according to the transition matrix $P_i$.\\
% Show that the channel capacity satisfies $\mbox{cap}(\Ccal)=\mbox{cap}(\Ccal_1)+\mbox{cap}(\Ccal_2)$.
% \end{bsp}

% \begin{bsp}
% Consider a binary channel $\Ccal$ which is composed of $n$ identical independent binary symmetric channels $\Ccal_i$ in sequence, each with error probability $p<\frac{1}{2}$. For channel $\Ccal_i$ denote by $X_{i-1}$ the input and by $X_i$ the output random variable, so that $X_0$ and $X_n$ are input and output of $\Ccal$.
% \begin{enumerate}
%     \item Show that $\Ccal$ is a binary symmetric channel with error probability $\frac{1}{2}(1-(1-2p)^n)$.
%     \item Conclude that $\lim_{n \to \infty} I(X_0;X_n)=0$.
% \end{enumerate}
% \end{bsp}