%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TPs Ann� 2000-2001
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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$ 2}:} 
\bigskip
\bigskip

\noindent {\bf 2-1.} The random variables $X$ and $Y$ have the joint probability distribution $p(x,y)$: 
\par
\medskip
\noindent (a) Calculate $H(X)$ and $H(Y)$.
\par
\medskip
\noindent (b) Calculate $H(X|Y)$ and $H(Y|X)$.
\par
\medskip
\noindent (c) Calculate $H(X,Y)$.
\par
\medskip
\noindent (d) Calculate $H(X{\rm:}Y)$.
\par
\medskip
\noindent (e) Draw a Venn diagram for the quantities obtained in (a), (b), (c) and (d).

\vspace*{-33mm}
\hspace*{100mm}
\begin{tabular}{|cc|ccc|}
\hline
&&\multicolumn{3}{|c|}{$Y=$}
\\ 
\multicolumn{2}{|c|}{P($X,Y$)}
&\multicolumn{1}{c}{$0$}
&\multicolumn{1}{c}{$1$}
&\multicolumn{1}{c|}{$2$}
\\
\hline
      & $0$ & $1/9$ & $1/9$ & $1/9$ \\
 $X=$ & $1$ & $1/9$ & $0$ & $2/9$  \\
      & $2$ & $1/9$ & $2/9$ & $0$ \\

\hline
\end{tabular}


\vspace*{10mm}
\bigskip
\noindent {\bf 2-2.} An urn contains red, white and black balls with probabilities $p_{R}, p_{W}$ and $p_{B}$. We consider as a random variable $X$ the color of a ball that is randomly drawn from the urn.
  
\par
\medskip
\noindent (a) Show that the entropy of drawing $k$ balls with replacement is given by
$H(X_{1},X_{2},...,X_{k})=kH(X)$ where $H(X)$ is the entropy of a single draw.
\par
\medskip
\noindent (b) If the balls are not replaced, and if one does not look at the color of the balls that were taken out, give an intuitive argument why $H(X_i)=H(X)$ where $H(X)$ is the entropy of an arbitrary draw. Without intuition, it might be useful to start solving (c) to (f).
\par
\medskip
\noindent 
(c) The balls are not replaced. Compare the probability to obtain colors $c_1$ at the first draw and $c_2$ at the second draw with the probability to obtain colors $c_2$ at the first draw and $c_1$ at the second draw. 
\par
\medskip
\noindent 
(d) The balls are not replaced. Calculate the probability to obtain a red ball at the second draw.
\par
\medskip
\noindent 
(e) The balls are not replaced. What can one say about the marginal probabilities?
\par
\medskip
\noindent 
(f) The balls are not replaced. Compare the entropy of the second draw with the entropy of the first draw.
\par
\medskip
\noindent 
(g) Show that the entropy of drawing $k$ balls without replacements is less than or equal to the entropy of drawing $k$ balls with replacement.


\bigskip
\noindent {\bf 2-3.} The random variables $X$, $Y$ and $Z$ generate a Markov chain $X\rightarrow Y\rightarrow Z$ if the conditional probability of $Z$ depends only on $Y$. Thus,  $p(x,y,z)=p(x)p(y|x)p(z|y)$.
 \par
\medskip
\noindent (a) Show that $X$ and $Z$ are conditionally independent given $Y$,  $p(x,z|y)=p(x|y)p(z|y)$. 
\par
\medskip
\noindent (b) Show that $H(X{\rm:}Y)\geq H(X{\rm:}Z)$ by using the result of (a) and the chain rule for the mutual entropy $H(X{\rm:}Y,Z)$. 
\par
\medskip
\noindent (c) The random variables $X$, $Y$ and $Z$ have probability distributions on sets 
${\mathcal{X}}$ of cardinality $n$, ${\mathcal{Y}}$ of cardinality $k$ and ${\mathcal{Z}}$ of cardinality $m$. Show that if $n>k$ and $m>k$ then $H(X{\rm:}Z)\leq \log_{2} k$. 
\par
\medskip
\noindent (d) Explain what happens if $k=1$.

\bigskip
\noindent {\bf 2-4.} We consider binary sequences of length $n$ emitted by a source of independent and identically distributed random variables. Every bit is emitted indepedently of the previous bit according to the binomial distribution where the probability to emit a ``1'' is given by $p$. We call {\em typical sequence} all sequences that contain $k$ ones and $(n-k)$ zeros, with $k\simeq np$ (we round the mean number of ones to the closest whole number.)
\par
\medskip
\noindent (a) What is the probability that the source emits a particular typical sequence? Give an approximation to that probability as a function of the entropy of the source.
\par
\medskip
\noindent (b) What is the number of typical sequences, expressed as a function of the entropy of the source? Compare that number with the absolute number of sequences that can be emitted by the source. What is the approximate probability to emit a sequence that is typical? (Use the Stirling approximation $n! \approx n^n$)
\par
\medskip
\noindent (c) What is the most probable sequence that can be emitted by the source? Is it typical?

\bigskip
\noindent {\bf 2-5.} {\em Definition}: $\rho(x,y)$ is a
{\em distance} if it satisfies the following properties $\forall x,y,z$:
\begin{enumerate}
\item $\rho(x,y)\ge 0$
\item $\rho(x,y)=\rho(y,x)$
\item $\rho(x,y)=0$ if and only if $x=y$
\item $\rho(x,y)+\rho(y,z)\ge \rho(x,z)$
\end{enumerate}
\medskip
\noindent (a) Let $\rho(X,Y)=H(X|Y)+H(Y|X)$.
Verify that $\rho(X,Y)=H(X,Y)-H(X{\rm:}Y)=2H(X,Y)-H(X)-H(Y)$,
and interpret this relation with the help of a Venn diagram. 
\par
\medskip
\noindent (b) Prove that $\rho(X,Y)$ satisfies all properties of a distance if the notation $X=Y$ means that there exists a bijection between $X$ and $Y$.
\newline
{\em Tip}: To show the last property use the strong subadditivity.

\bigskip
\noindent {\bf 2-6.} Assume three binary random variables $X,Y$ and $Z$. Suppose that these variables are uniformly distributed, that is $H(X)=H(Y)=H(Z)=1$~bit. If one ignores $Z$, one can define the mutual information of $X$ and $Y$, that is $H(X{\rm:}Y)$. Equally, one can define the mutual information of $X$ and $Y$, \emph{conditional} on $Z$, i.e. $H(X{\rm:}Y|Z)$. Finally, one defines $H(X{\rm:}Y{\rm:}Z)=H(X{\rm:}Y)-H(X{\rm:}Y|Z)$, that is the mutual information of three random variables. This entropy can be positive, negative or zero.
\par
\medskip
\noindent (a) Give an example for a distribution of $X$, $Y$ and $Z$
such that $H(X{\rm:}Y{\rm:}Z)>0$. 
\par
\medskip
\noindent (b) Give an exmaple for a distribution of $X$, $Y$ and $Z$
such that $H(X{\rm:}Y{\rm:}Z)<0$.

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


\end{document}