\begin{center}
{\large\bf Exercise sheet 07 -- 23.05.2024}
\end{center}
\hrule
\bigskip

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

\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} \label{ex:MC}
	Let $(X_n)_{n\geq 0}$ 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$.
%	$$\mathbf{P} = \begin{pmatrix}
%	0.88 & 0.12 \\
%	0.5 & 0.5
%	\end{pmatrix} .$$
	\begin{enumerate}
		\item Draw the transition graph.
		\item Compute the stationary distribution $\nu$ of the Markov chain.
		\item Let $t^0$ be the first return time to $0$ after starting with $X_0=0$. Based on the transition graph, compute $\Expect(t^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 got in part (b).		
	\end{enumerate}
\end{bsp}

\begin{bsp} 
    Consider again the Markov Chain $(X_n)_{n\geq 0}$ from Exercise \ref{ex:MC}.
    \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&= 01001010010110110010 ,\\
        w_2&= 01110011110111011111 .
        \end{align*}
    \end{enumerate}
\end{bsp}

