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

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

\bigskip
 
 \begin{bsp} 
		Consider again the Markov Chain $(X_n)_{n\geq 1}$ from Exercise~5.6 (last session	).
     \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}
   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 $\mathcal{X} = \{a, b, c, d, e, f, g, h\}$. 
  \begin{enumerate}
    \item Give an example of a prefix code $C : \mathcal{X} \to \{0,1\}^*$ with code word lengths
     \[\begin{split} 
     &\ell(C(a)) = \ell(C(b)) = \ell(C(c)) = 2, \; \ell(C(d))=3, \\  
     &\ell(C(e)) = \ell(C(f)) = \ell(C(g)) = 5, \; \ell(C(h))=6.
     \end{split}\]
    \item Show that the Kraft inequality is a strict inequality for this code, that is, 
      \[\sum_{x \in \mathcal{X}} 2^{-\ell(C(x))} < 1.\]
    \item Find a binary sequence of length 6 which cannot be decoded.
    \item Find a prefix code $C : \mathcal{X} \to \{0,1\}^*$ such
      that we have equality in the Kraft inequality.
    \item Find a probability distribution for a random variable $X: \Omega \rightarrow \mathcal{X}$ such that your code is optimal and compare the expected code length with $H(X)$.
  \end{enumerate}
\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}

\end{document} 