\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}{4}

\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\ (15.05.2025)} \\[1ex]
\end{center}  
\hrule

\bigskip

\begin{bsp}
Find an example of two different probability distributions $p \neq q$ on the set $\{0, 1\}$ that satisfy $\D{p}{q} = \D{q}{p}$.
\end{bsp}

\begin{bsp}
Let $X_1,\ldots, X_n, Y$ be random variables. Prove the chain rule for mutual information, that is, show explicitly that
\[I((X_1,\ldots, X_n);Y)= I(X_1 ; Y) + I(X_2; Y|X_1) + \ldots + I(X_n;Y| X_1,\ldots, X_{n-1})
\]
Give a more general chain rule for expressions of the form $I((X_1,\ldots,X_n) ; (Y_1,\ldots, Y_m))$.
\end{bsp}


 \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}
\end{bsp}

 \begin{bsp}
 Let $X, Y, Z_1, Z_2$ be random variables on a common state space $\mathcal{X}$ forming the Markov triple $(X,Y,(Z_1,Z_2))$, that is, \[p(x,y,z_1,z_2)=p(x)\,p(y \mid x)\, p(z_1,z_2 \mid y)\] holds
 for all $x,y,z_1,z_2 \in \mathcal{X}$. Show that
 \[
 I(X\semicolon Z_1)+I(X\semicolon Z_2) \leq I(X\semicolon Y)+I(Z_1\semicolon Z_2).
 \]
 \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 state 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}


\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}

\end{document} 