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

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

\bigskip


\begin{bsp}
A channel has the following probability transition matrix:
\[ P=
\left[
\begin{array}{ccc}
 \frac{2}{3} & \frac{1}{3} & 0   \\
 \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\
  0 & \frac{1}{3} & \frac{2}{3}      
\end{array}
\right].
\]
Show that its capacity is achieved by a distribution that places zero probability on one of the input symbols. Calculate the capacity of the channel. Give an intuitive reason why that letter is not used.
\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 $\operatorname{cap}(\Ccal)=\operatorname{cap}(\Ccal_1)+\operatorname{cap}(\Ccal_2)$.
\end{bsp}


\begin{bsp}
Given a channel $\mathcal{C}=(\mathcal{X},P,\mathcal{Y})$ suppose we form a new channel $\mathcal{C}'$ by transmitting the same message $X$ across the channel twice, resulting in an output $(Y_1,Y_2)$ where $Y_1$ and $Y_2$ are conditionally independent and conditionally identically distributed given $X$.
\begin{enumerate}
    \item Show that
    \[
    I(X;Y_1,Y_2) = 2I(X;Y_1) - I(Y_1;Y_2).
    \]
    \item Conclude that $\operatorname{cap}(\mathcal{C}') \leq 2 \operatorname{cap}(\mathcal{C})$.
\end{enumerate}
\end{bsp}


\begin{bsp}
	Let $\mathcal{C}=(\mathcal{X},P,\mathcal{Y})$ be a binary channel which is composed of two binary channels in sequence, such that the output of the first channel $\mathcal{C}_1=(\mathcal{X},P_1,\mathcal{Z})$ is the input of the second channel $\mathcal{C}_2=(\mathcal{Z},P_2,\mathcal{Y})$. Let the transition matrices be
	\[
	P_1=
	\left[ \begin{array}{cc}
	1-p_{1} & p_{1}      \\
	p_{1} & 1-p_{1} 
	\end{array}
	\right],
	\quad \quad
	P_2=
	\left[
	\begin{array}{cc}
	1-p_{2} & p_{2}      \\
	p_{2} & 1-p_{2} 
	\end{array} \right].
	\]
    \begin{enumerate}
        \item Show that $\mbox{cap}(\Ccal) \leq \min\{\mbox{cap}(\Ccal_1),\mbox{cap}(\Ccal_2)\}$. 
        \item Compute the transition matrix $P$ and the channel capacity $\mbox{cap}(\mathcal{C})$.
        \item Assume that $0 \leq p_1 \leq p_2 < 1/2$. When do we have equality in (a)?
    \end{enumerate}
\end{bsp}


\begin{bsp}
    Let $\Ccal=(\Xcal,P,\Ycal)$ be a discrete memory-less channel with capacity $C$. Suppose that this channel is immediately followed by an erasure channel, that erases the output of $\Ccal$ with probability $\alpha$. This yields a new channel $\Ccal'=(\Xcal, P',\Ycal \cup \{e\})$ with transition probability 
    \[p'(y \mid x)=(1-\alpha) p(y \mid x) \text{ and } p'(e \mid x)=\alpha \text{ for } x \in \Xcal, y \in \Ycal.\]
    Compute the capacity of $\Ccal'$.
\end{bsp}


\begin{bsp}
Consider a channel with binary inputs that has both errors (with probability $\epsilon$) and erasures (with probability $\alpha$), and so has transition matrix
\[
P = \begin{pmatrix}
    1-\alpha-\epsilon &\epsilon &\alpha\\
    \epsilon & 1-\alpha-\epsilon& \alpha
\end{pmatrix}.
\]
Find the capacity of this channel.
\end{bsp}

\end{document} 