\begin{center}
{\large\bf Exercise sheet 05 -- 02.05.2024}
\end{center}
\hrule
\bigskip

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


 \begin{bsp}
Our goal is to identify a random object $X$ which is distributed in $\mathcal{X}$ with some distribution $p$. A question $Q$ from a set $\mathcal{Q}$ is asked at random according to distribution $r$. This results in a deterministic answer $A=A(X,Q)$,
that is, there is a deterministic function $(x,q) \mapsto A(x,q)$ from $\mathcal{X}$ to $\mathcal{Q}$. Suppose $X$ and $Q$ are independent. Then $I(X;Q,A)$ is the uncertainty in $X$ removed by the question-answer pair $(Q,A)$.
\begin{enumerate}
    \item Show that $I(X;Q,A)=H(A \mid Q)$ and interpret this statement.
    \item Now suppose that two i.i.d. questions $Q_1,Q_2 \sim r$ are asked, yielding answers $A_1$ and $A_2$. Show that $I(X;Q_1,A_1,Q_2,A_2) \leq 2I(X;Q_1,A_1)$.
\end{enumerate}
\end{bsp}


\begin{bsp}
The \emph{interaction information} of three random variables $X_1,X_2,X_3$ is defined as
\[
I(X_1 \semicolon X_2\semicolon X_3): = I(X_1\semicolon X_2) - I(X_1\semicolon X_2 \mid X_3).
\]
\begin{enumerate}
    \item Show that the interaction information is symmetric, in the sense that $I(X_1\semicolon X_2\semicolon X_3) = I(X_{\sigma(1)}\semicolon X_{\sigma(2)}\semicolon X_{\sigma(3)})$ holds for any permutation $\sigma$ of $\{1,2,3\}$.
    \item Give an example of random variables $X_1,X_2,X_3$ such that $I(X_1\semicolon X_2\semicolon X_3) < 0$.
\end{enumerate}
%(Venn Diagram)
\end{bsp}

\begin{bsp} \label{ex:markov}
  Consider the Markov chain $(X_n)_{n \geq 0}$ on $\mathcal{X} = \{1, \ldots,
  7\}$ with transition matrix
  \[\mathbf{P} = \begin{pmatrix}
      \frac{1}{3} & 0  &              0  & \frac{1}{3} &  0  & 0               & \frac{1}{3} \\
      \frac{1}{3} & 0  &              0  & \frac{1}{3} &  0  & 0               & \frac{1}{3} \\
      \frac{1}{2} & 0  &              0  & \frac{1}{2} &  0  & 0               &          0  \\
      \frac{1}{3} & 0  &              0  & \frac{1}{3} &  0  & 0               & \frac{1}{3} \\
                    0 & 0  & \frac{1}{2} &              0  &  0  & \frac{1}{2} &          0  \\
                    0 & 0  &              0  &              0  &  0  & 0               &           1 \\
      \frac{1}{3} & 0  &              0  & \frac{1}{3} &  0  & 0               & \frac{1}{3} \\
  \end{pmatrix}.\]
  \begin{enumerate}
    \item Draw the transition graph. Is $(X_n)$ irreducible?
    \item Calculate $\Prob [X_n = i \mid X_0 = 6]$ for $i \in \mathcal{X}$ and
      $n \in \{1, 2, 3\}$.
    \item Give a stationary distribution for $X_n$. Is it unique?
    \item Calculate $\lim_{n \to \infty} \Prob [X_n = i \mid X_0 = 6]$ for all
      $i \in \mathcal{X}$.
  \end{enumerate}
\end{bsp}

\begin{bsp}
  Give an example to show that in general, a function of a Markov chain is not
  necessarily again a Markov chain (i.e., find a Markov chain $(X_n)_{n \geq 0}$ with finite spate space $\mathcal{X}$ and a function $f: \mathcal{X} \to \mathcal{Y}$ such that $(Y_n)_{n \geq 0}$ with $Y_n = f(X_n)$ is not
  a Markov chain).
\end{bsp}


