\begin{center}
{\large\bf Exercise sheet 10 -- 20.06.2024}
\end{center}
\hrule
\bigskip

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

%\begin{bsp}[2 Points]
%The source coding theorem shows that the optimal binary code for a random variable $X$ has an expected length less than $H(X)+1$. Show this bound is tight by finding for any given $\varepsilon > 0$ a random variable $X_\varepsilon$ such that its optimal code $C_\varepsilon$ has expected code length larger than $H(X_{\varepsilon})+1-\varepsilon$.
%\end{bsp}

\begin{bsp}
    Imagine you are the commander of an army besieged in a fort and can only communicate with your allies by sending carrier pigeons. Assume that each pigeon can carry one letter (8 bits) and one pigeon can be sent every 5 minutes.
    \begin{enumerate}
        \item Assuming all pigeons reach their destination safely, what is the capacity of this `channel' in bits/hour?
        \item Now assume that the enemies try to shoot down the pigeons and manage to hit a fraction $\alpha$ of them. Since the pigeons are sent at a constant rate, the receiver knows which pigeons are missing. What is the capacity of this `channel'?
        \item Now assume that every time a pigeon is shot down, the enemies send out a dummy pigeon carrying a random letter chosen uniformly from the set of 8-bit letters. What is the capacity of this `channel'?
    \end{enumerate}
\end{bsp}

\begin{bsp}
Show that the capacity of the channel with 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]\,
\]
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}
	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}
Consider two 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$.\\
Compute the channel capacity $\mbox{cap}(\Ccal)$ in terms of $\mbox{cap}(\Ccal_1)$ and $\mbox{cap}(\Ccal_2)$.
\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}

