\begin{center}
{\large\bf Exercise sheet 04 -- 25.04.2024}
\end{center}
\hrule
\bigskip

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

\begin{bsp}
An urn contains $r$ red, $w$ white, and $b$ black balls. We first draw $k \geq 2$ balls (one by one) from the urn with replacement (putting them back after each draw). Denote their colours by $X_1, \dots, X_k$. Then we draw $k$ balls from the urn without replacement. Denote their colours by $Y_1, \dots, Y_k$.
\begin{enumerate}
    \item Find $H(X_1, \dots, X_k)$.
    \item Which is larger, $H(X_1, \dots, X_k)$ or $H(Y_1, \dots, Y_k)$? Prove your statement.
\end{enumerate}
(Hint : Clearly $Y_1 \sim X_1$, show that $Y_k \sim X_1$ for all $k$)
\end{bsp}

\begin{bsp}
 Suppose you have $n>2$ coins and among them there may or may not be a counterfeit coin, which is either heavier or lighter than the other coins. You weigh the coins with a balance to determine if there is a heavier or lighter counterfeit coin. Let $k(n)$ be the smallest number of weighings always sufficient to find the counterfeit coin (if any) among the $n$ coins and correctly declare it to be heavier or lighter. 
 \begin{enumerate}
  \item Show that $k(n) \geq \log_3(2n+1)$.
  \item (Difficult) Give a coin weighing strategy for $k=3$ weighings and $n=12$ coins.
 \end{enumerate}
 \end{bsp} 

\begin{bsp}
Show that the entropy of the probability distribution $(p_1, \dots, p_i, \dots, p_j, \dots, p_n)$ cannot be larger than the entropy of the distribution $(p_1, \dots, \frac{p_i+p_j}{2}, \dots, \frac{p_i+p_j}{2}, \dots, p_n)$. When do we have equality?
\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}




