%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TPs Ann� 2002-2003
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{article}

\voffset -2.8 cm 
\textwidth 17 cm
\textheight 24.7 cm
\oddsidemargin -.54 cm
\evensidemargin -1.54 cm

\pagestyle{plain}


\begin{document}

\centerline {\Large \sc Information and coding theory}
\bigskip
\bigskip
\hrule
\bigskip
\bigskip
\centerline {\underline{\Large Exercise sheet n$^\circ$ 1}:} 
\bigskip
\bigskip

\noindent {\bf 1-1.} A discrete random variable $X$ has a uniform probability distribution $p(x)$ over the set 
${\mathcal{X}}$ of cardinality $|{\mathcal{X}}|=m$.
\par
\medskip
\noindent (a) Give an example for ${\mathcal{X}}$ and calculate $p(x)$ 
for $x \in {\mathcal{X}}$.
\par
\medskip
\noindent (b) Determine the entropy $H(X)$. If $m=64$, what is $H(X)$?
\par
\medskip
\noindent (c) How many bits are needed to enumerate the alphabet ${\mathcal{X}}$ without encoding, where $m=64$?
\par
\medskip
\noindent (d) How many symbols taken from a quaternary alphabet are necessary to enumerate the alphabet   ${\mathcal{X}}$ without encoding, where $m=64$?
\par
\medskip
\noindent (e) Show that $H(X)$ is greater than the entropy of any other random variable $Y$, where $Y$ has values on the same set $\mathcal{X}$. {\it (Read the recall on Lagrange multipliers.)}

\bigskip
\noindent {\bf 1-2.} A random variable $X$ has an alphabet ${\mathcal{X}}=\{A,B,C,D\}$.
\par
\medskip
\noindent (a) Calculate $H(X_P)$ associated to probabilities \newline
$P(X)=\{1/2,1/4,1/8,1/8\}$.
\par
\medskip
\noindent (b) Calculate $H(X_Q)$ associated to probabilities
$Q(X)=\{1/4,1/4,1/4,1/4\}$.
\par
\medskip
\noindent (c) We define a binary code:
\newline  
\{C($X=A$)=0, C($X=B$)=10, C($X=C$)=110, C($X=D$)=111\}.
\newline  
Calculate the expected length (in bits) of the codewords of $X$ are distributed according to $P(X)$ and $Q(X)$
\par
\medskip
\noindent (d) Compare the four obtained results.


\bigskip
\noindent {\bf 1-3.} A coin (with same probability for ``head'' or ``tail'') is flipped repeatedly until one obtains ``head''. Let the random variable $X$ be given by the number of flips until one obtains ``head'' for the first time.
\par
\medskip
\noindent (a) Calculate $H(X)$.
\par
\medskip
\noindent (b) One repeatedly flips the coin until ``head'' is obtained for the first time. Find a sequence of questions of type ``yes/no'' to determine the value of $X$. Compare the entropy of $X$ with the expected length of the sequence of questions necessary to fully determine $X$.
\par
\medskip
\noindent {\it Note:}
\begin{eqnarray*}
\sum_{n=1}^\infty r^n={r\over 1-r}, \qquad
\sum_{n=1}^\infty n r^n={r\over (1-r)^2}, \qquad r < 1.
\end{eqnarray*}


\newpage

\noindent {\bf 1-4.} Assume $X$ and $Y$ to be random variables. What is the inequality relating $H(X)$ and $H(Y)$ if,
\par
\medskip
\noindent (a) $Y=2^X$, with ${\mathcal{X}}=\{0,1,2,3,4\}$ associated to probabilities $\{1/2,1/4,1/8,1/16,1/16\}$. 
\par
\medskip
\noindent (b) $Y=\cos(X)$, with ${\mathcal{X}}=\{0,\pi/2,\pi,3 \pi/2,2 \pi \}$ associated to probabilities $\{1/3,1/3,1/12,1/12,1/6\}$.
\par
\medskip
\noindent (c) Show that the entropy of any function $f(X)$ of the random variable $X$ is less or equal than the entropy of $X$. In order to prove this, it is useful to calculate the join entropy $H(X,f(X))$. In which case the inequality $H(f(X)) \le H(X)$ is saturated?
\par

\bigskip
\noindent {\bf 1-5.} Let $X$ and $Y$ be two random variables, taking values $x_1,x_2,\cdots, x_r$ and $y_1,y_2,\cdots, y_s$. Furthermore, we define a random variable $Z=X+Y$.
\par
\medskip
\noindent (a) Show that $H(Z|Y)=H(X|Y)$ and $H(Z|X)=H(Y|X)$. Deduce that if $X$ and $Y$ are independently distributed, then $H(X)\le H(Z)$ and $H(Y)\le H(Z)$. Thus, summing two random variables can only increase the uncertainty.
\par
\medskip
\noindent (b) Give an example for $X$ and $Y$ (necessarily correlated) such that $H(X)>H(Z)$ and $H(Y)>H(Z)$.
\par
\medskip
\noindent (c) In which case the equality $H(Z)=H(X)+H(Y)$ is satisfied?
\par
\bigskip


\noindent {\bf Optional:} Give an example of a distribution of two random variables $X$ and $Y$ whose correlation coefficient is zero, although they are not independent. Show that in this case $H(X{\rm:}Y) \ne 0$, showing that the mutual entropy is a better measure of the dependence of $X$ and $Y$.
\medskip
Correlation coefficient: $r=\frac{<xy>-<x><y>}{\sqrt{<x^{2}>-<x>^{2}}\sqrt{<y^{2}>-<y>^{2}}}$
\medskip
\par
\bigskip

\bigskip
\bigskip
\centerline {\underline{\Large Recall}:} 
\bigskip

\begin{enumerate}
\item Change of the base of logarithms
\medskip
\newline
$\log_{a}N=\log_{b}N/\log_{b}a$

\item Lagrange theorem:
\begin{itemize}
\item 
We want to maximize
\newline
$u(x_{1},x_{2},...,x_{n})$ with $k$ constraints $g_{j}(x_{1},x_{2},...,x_{n})=a_{j}$, $j=1,\cdots,k$.
\item 
We introduce the Lagrangian:
\newline
$
L(x_{1},...,x_{n},\lambda_{1},...,\lambda_{k})=u(x_{1},x_{2},...,x_{n})+\sum_{j=1}^{k}\lambda_{j}[a_{j}-g_{j}(x_{1},x_{2},...,x_{n})].
$
\item 
Condition on an extremum:
\newline
$\forall i, \frac{\partial L}{\partial x_{i}}=0.$ 
\item 
If $u$ is concave, the solution is a maximum.
\end{itemize}
\end{enumerate}

\bigskip
\centerline {\underline{\Large Web site}:} 
\bigskip
http://quic.ulb.ac.be/teaching/
\end{document}


% \noindent {\bf 1-7.} On dispose de $n$ pi\`eces de monnaie dont l'une d'entre
% elles peut \'eventuellement \^etre contrefaite. 
% Une pi\`ece contrefaite se reconna\^\i t par le fait qu'elle est soit
% l\'eg\`erement plus lourde, soit l\'eg\`erement plus l\'eg\`ere qu'une
% pi\`ece authentique. Afin de d\'eterminer s'il y a contrefa\c con,
% les pi\`eces sont pes\'ees.
% \par
% \medskip
% \noindent (a) Quelle est la distribution de probabilit\'e de la pi\`ece contrefaite qui maximise l'entropie se Shannon.
% Traiter l'existance ou non de pi\`ece contrefaite comme un \'el\'ement de plus de la distribution de probabilit\'e.
% \par
% \medskip
% \noindent (b) \'Etablir l'\'equation qui borne inf\'erieure et sup\'erieurement le nombre de pes\'ees en moyenne.
% \par
% \medskip
% \noindent (c) Sachant que la distribution de probabilit\'e est 2-adique. 
% Obtenir une borne sup\'erieure du nombre de pi\`eces $n$
% tel que $k$ pes\'ees en moyenne suffisent pour trouver la pi\`ece contrefaite, s'il y en a.
% \par
% 
