% \def\solutionMode{TRUE}
\documentclass[12pt]{article}%
\usepackage{573}%
%
% ======================================================================
\begin{document}
% \thispagestyle{empty}
% \headers{\Course{}}{Homework 0 (due 8/30/07)}{\Semester{}}
\noindent {\LARGE\bf \Course{}: \CourseName{}, \Semester{}}
\\[1ex]
{\Large\bf Homework 6 -- not for submission.}
\\[0.25in]
{\bf Version 1.0}
\smallskip
\noindent
\hrule \hrule \hrule \hrule%
\bigskip%
Solutions to this homework would not be provided. Questions from this
homework might appear in the final exam.
\bigskip
\hrule
\hrule
\hrule
\hrule
\section*{Practice problems}
\begin{compactenum}[\color{red} \huge \bf 1.]%
% \begin{compactenum}[(A)]
\item \HWProblem{20}{Naive.}{
We wish to compress a sequence of independent, identically
distributed random variables $X_1, X_2, \ldots$. Each $X_j$
takes on one of $n$ values. The $i$\th value occurs with
probability $p_i$, where $p_1 \geq p_2 \geq \ldots \geq
p_n$. The result is compressed as follows. Set
\begin{align*}
T_i = \sum_{j=1}^{i-1} p_j,
\end{align*}
and let the $i$\th codeword be the first $\ceil{ \lg (1/p_i) }$
bits (in the binary representation) of $T_i$. Start with an
empty string, and consider $X_j$ in order. If $X_j$ takes on
the $i$\th value, append the $i$\th codeword to the end of the
string.
\begin{enumerate}[(A)]
\item Show that no codeword is the prefix of any other
codeword.
\item Let $Z$ be the average number of bits appended for
each random variable $X_j$. Show that
\begin{align*}
\EntropyX{X_j} \leq z \leq \EntropyX{X_j} + 1.
\end{align*}
\end{enumerate}
}{}{}
\item \HWProblem{20}{Codification.}{%
\emphi{Arithmetic coding} is a standard compression method. In
the case when the string to be compressed is a sequence of
biased coin flips, it can be described as follows. Suppose that
we have a sequence of bits $X = ( X_1, X_2, \ldots, X_n)$,
where each $X_i$ is independently $0$ with probability $p$ and
$1$ with probability $1-p$. The sequences can be ordered
lexicographically, so for $x= (x_1, x_2 , \ldots, x_n)$ and $y
= (y_1, y_2, \ldots, y_n)$, we say that $x< y$ if $x_i=0$ and
$y_i=1$ in the first coordinate $i$ such that $x_i \ne y_i$. If
$z(x)$ is the number of zeroes in the string $x$, then define
$p(x) = p^{z(x)}(1-p)^{n-z(x)}$ and
\begin{align*}
q(x) = \sum_{y < x} p(y).
\end{align*}
\begin{enumerate}[(A)]
\item Suppose we are given $X = (X_1, X_2, \ldots,
X_n)$. Explain how to compute $q(X)$ in time $O(n)$ (assume
that any reasonable operation on real numbers takes
constant time).
\item Argue that the intervals $\;\left[q(x), q(x) + p(x)
\MakeBig \right)$ are disjoint subintervals of $[0,1)$.
\item Given (A) and (B), the sequence $X$ can be
represented by any point in the interval $I(X) =
\left[q(X),\MakeBig q(X) + p(X)\right)$. Show that we can
choose a codeword in $I(X)$ with $\ceil{ \lg (1/p(X))} + 1$
binary digits to represent $X$ in such a way that no
codeword is the prefix of any other codeword.
\item Given a codeword chosen as in (C), explain how to
decompress it to determine the corresponding sequence
$(X_1, X_2, \ldots, X_n)$.
\item (Extra credit.) Using the Chernoff inequality, argue
that $\lg(1/p(X))$ is close to $n\EntropyX{p}$ with high
probability. Thus, this approach yields an effective
compression scheme.
\end{enumerate}}{}{}{}
\item \HWProblem{20}{Maximizing Entropy}{%
Consider an $n$-sided die, where the $i$\th face comes up with
probability $p_i$. Show that the entropy of a die roll is
maximized when each face comes up with equal probability $1/n$.
}{}
\item \HWProblem{20}%
{Extraction to the limit,}%
{%
We have shown that we can extract, on average, at least
$\floor{\lg m} -1$ independent, unbiased bits from a number
chosen uniformly at random from $\brc{0, \ldots, m-1}$. It
follows that if we have $k$ numbers chosen independently and
uniformly at random from $\brc{0, \ldots, m-1}$ then we can
extract, on average, at least $k \floor{\lg m } - k$
independent, unbiased bits from them. Give a better procedure
that extracts, on average, at least $k \floor{\lg m } -1$
independent, unbiased bits from these numbers.}{}{}{}
% \newpage
\item \HWProblem{20}{Easy inequality.}{%
Assume you have a (valid) prefix code with $n$ codewords, where
the $i$\th codeword is made out of $\ell_i$ bits. Prove that
\begin{align*}
\sum_{i=1}^n \frac{1}{2^{l_i}} \leq 1.
\end{align*}
}{}
%\end{compactenum}
%\begin{compactenum}
\item \HWProblem{20}{Computing entropy.}{%
\begin{enumerate}
\item Let $S = \sum_{i=1}^{10} 1/i^2$. Consider a random
variable $X$ such that $\Prob{X = i} = 1/(S i^2)$, for
$i=1,\ldots, 10$. Compute $\EntropyX{X}$.
\item Let $S = \sum_{i=1}^{10} 1/i^3$. Consider a random
variable $X$ such that $\Prob{X = i} = 1/(S i^3)$, for
$i=1,\ldots, 10$. Compute $\EntropyX{X}$.
\item Let $S(\alpha) = \sum_{i=1}^{10} 1/i^\alpha$, for
$\alpha > 1$. Consider a random variable $X$ such that
$\Prob{X = i} = 1/(S(\alpha) i^\alpha)$, for $i=1,\ldots,
10$. Prove that $\EntropyX{X}$ is either increasing or
decreasing as a function of $\alpha$ (you can assume that
$\alpha$ is an integer).
\end{enumerate}
}{}
\item \HWProblem{20}{Conditional Entropy}{%
The \emphi{conditional entropy} $\EntropyX{Y |X}$ is defined by
\begin{align*}
\Entropy{Y |X} = \sum_{x,y} \Prob{(X =x ) \cap (Y = y)} \lg
\frac{1}{\Prob{Y = y | X= x}}.
\end{align*}
If $Z=(X,Y)$, prove that
\begin{align*}
\EntropyX{Z} = \EntropyX{X} + \EntropyX{Y | X}.
\end{align*}
}{}
\end{compactenum}
\end{document}