\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{marginnote}
\usepackage{hyperref}

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

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

\bigskip



\begin{bsp}
Let $X$ and $Y$ be the values of two independently thrown six-sided dice.
Calculate
\begin{enumerate}
	\renewcommand{\itemsep}{0.25mm}
    \item $H(X)+H(Y)$,
    \item $H(X+Y)$,
    \item $H(X-Y)$,
    \item $H(\max(X,Y))$.
\end{enumerate}
\end{bsp}

\begin{bsp}
	Let $f \, : \, I \to \RR$ be a convex function defined on an interval $I \subseteq \RR$. Let $x_1,\dots,x_n \in I$ be points in the interval and let $p_i \in [0,1]$ for $i=1,\dots,n$ be probabilities, i.e., $p_1 + \dots + p_n = 1$. 
	Show that:
	\begin{align*}
		f \left(\sum_{i=1}^n p_i x_i \right) \leq \sum_{i=1}^n p_i f(x_i).
	\end{align*}
\end{bsp}

\begin{bsp}
A fair coin is flipped until heads occurs the first time. Let $X$ denote the number of flips required.
\begin{enumerate}
    \item Find the entropy $H(X)$ in bits.
    \item Find an efficient sequence of yes-no questions in order to guess the outcome of $X$. Compare $H(X)$ to the expected number of questions.
\end{enumerate}
\end{bsp}

\begin{bsp}
The NBA Playoffs are a best-of-seven series between Team A and Team B, which ends when one team wins four games.
Let the random variable $X$ represent the outcome of the series of games. 
For example, some possible outcomes are AAAA, ABABABA, and AAABBBB. 
Let the random variable $Y$ represent the number of games played. 
In the previous three examples this is $4$, $7$, and $7$, respectively.
%
Assume that the two teams are equally strong. 
Find the values of $H(X)$, $H(Y)$, $H(Y \mid X)$, and $H(X \mid Y)$.
\end{bsp}

\begin{bsp}
Let $X$ and $Y$ be random variables that take values in finite sets $\mathcal{X}$ and $\mathcal{Y}$, respectively. Let $Z = X + Y$.
\begin{enumerate}
    \item Show that $H(Z \mid X) = H(Y \mid X)$. Argue that if $X, Y$ are independent, then $H(Y) \leq H(Z)$ and $H(X) \leq H(Z)$.
    \item Give an example of (necessarily dependent) random variables in which $H(X) > H(Z)$ and $H(Y) > H(Z)$.
    \item Find a necessary and sufficient condition for $H(Z) = H(X) + H(Y)$.
\end{enumerate}
\end{bsp}


\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}
(\emph{Hint: Clearly $Y_1$ and $X_1$ have the same distribution. Show that also $Y_k$ and $X_1$ have the same distribution 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.
To be precise, in a weighing you take two disjoint sets $A$ and $B$ of coins and determine which set is heavier than the other, or whether they weigh the same.
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} 

\end{document} 