\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\bf Tutorial 9 solutions }

\date{}

\begin{enumerate}
\item Consider messages (strings) of length $n$
on an alphabet of size $k$, $\{a_1,a_2,\ldots,a_k\}$,
where the frequency counts of $a_1,\ldots,a_k$ are $n_1,\ldots,n_k$
respectively.  That is, the letter $a_i$ occurs $n_i$ times in the message.
What is the total number of possible messages?


This is the permutation problem we studied in class. 
We have to find the number of permutations of a word with $n$ letters from
an alphabet of $k$ different letters,
with $n_1$ occurrences of the first letter, $n_2$ of the second, $\ldots$, 
$n_k$ are of $k^{th}$. This number is
$${ n! \over n_1!n_2! \ldots n_k!}$$ 

\item 
\begin{enumerate}
\item With no restrictions on encoding (i.e., each letter need not be
coded separately), show that the minimum number of bits needed to encode
a string of length $n$ (of the type described above) is
$$\sum_{i=1}^k n_i \log \frac{n}{n_i} + \frac{1}{2} \log 2\pi n 
- \frac{1}{2}\sum_{i=1}^k \log 2\pi n_i + \Theta (\frac{1}{n}) - 
\sum_{i=1}^k \Theta (\frac{1}{n_i})$$

We have to have an encoding scheme that distinguishes among ${n! \over n_1!n_2!\ldots n_k!}$ strings and so a lower bound on the number of bits we need is 
$$\log  {n! \over n_1!n_2!\ldots n_k!}$$
Using Stirling's formula,
$$\log  {n! \over n_1!n_2!\ldots n_k!} =
\log {\sqrt{2\pi n} \over \sqrt{2\pi n_1 \ldots 2\pi n_k}} {n^n e^{n_1}\ldots e^{n_k} \over e^n n_1^{n_1} \ldots n_k^{n_k} } 
{e^{\Theta(1/n)} \over e^{\Theta (1/n_1)}\ldots e^{\Theta(1/n_k)}}$$
$$ = n \log n - \sum_{i=1}^k n_i \log n_i +  \log {\sqrt{2\pi n} \over \sqrt{2\pi n_1 \ldots 2\pi n_k}} + \Theta(1/n) - \sum_{i=1}^k \Theta(1/n_i)$$
$$ = \log n \sum_{i=1}^k n_i - \sum_{i=1}^k n_i \log n_i + 1/2\log 2\pi n - 1/2\sum_{i=1}^k \log 2 \pi n_i + \Theta(1/n) - \sum_{i=1}^k \Theta(1/n_i)$$
$$ = \sum_{i=1}^k n_i \log \frac{n}{n_i}  + 1/2\log 2\pi n - 1/2\sum_{i=1}^k \log 2 \pi n_i + \Theta(1/n) - \sum_{i=1}^k \Theta(1/n_i)$$

\item Without loss of generality, assume $n_1$ is the largest 
frequency, i.e., $n_1 \geq n_i$ for all $i>1$. Show that
for $i >1$,
$$n_i \log \frac{n}{n_i} - \frac{1}{2} \log 2\pi n_i - \Theta (\frac{1}{n_i})
\sim n_i \log \frac{n}{n_i}$$

Note that for $i >1$, $n_i \leq n/2$.
Now consider two cases:
\begin{enumerate}
\item $n_i = O(1):$  (That is, as $n$ grows, $n_i$ is bounded.) 
Then $n_i \log \frac{n}{n_i} \sim n_i \log n$ and
$$1/2 \log 2\pi n_i- \Theta (\frac{1}{n_i}) = o(n_i \log n)$$ 
So here 
$n_i \log \frac{n}{n_i} - \frac{1}{2} \log 2\pi n_i - \Theta (\frac{1}{n_i}) \sim n_i \log \frac{n}{n_i}$.

\item $n_i = \omega(1):$ (i.e. as $n$ grows, $n_i$ also grows to infinity.)
Then $n_i \log \frac{n}{n_i} \geq n_i$ and
$$1/2 \log 2\pi n_i- \Theta (\frac{1}{n_i}) = o(n_i)$$ 
So here too, $n_i \log \frac{n}{n_i} - \frac{1}{2} \log 2\pi n_i - \Theta (\frac{1}{n_i}) \sim n_i \log \frac{n}{n_i}$.
\end{enumerate}

\item Using the above show that the lower bound we get is 
$$\sim \frac{1}{2} \log \frac{n}{n_1} + \sum_{i=1}^k n_i \log \frac{n}{n_i}$$

Let us separate the lower bound we got into the terms with $n_1$ and the
rest.
$$n_1 \log \frac{n}{n_1} - 1/2 \log 2\pi n_1 + 1/2\log 2\pi n+ \Theta(1/n) \sum_{i=2}^k n_i \log \frac{n}{n_i} - 1/2\sum_{i=2}^k \log 2 \pi n_i - \sum_{i=1}^n \Theta(1/n_i)$$
$$ \sim n_1 \log \frac{n}{n_1} + 1/2 \log \frac{n}{n_1} + 
\sum_{i=2}^k n_i \log \frac{n}{n_i}$$
$$ = 1/2 \log \frac{n}{n_1}+ \sum_{i=1}^k n_i \log \frac{n}{n_i}$$

\item Finally show that this is $\sim \sum_{i=1}^k n_i \log \frac{n}{n_i}$.

Since $n_1 \geq n_i$ for all $i > 1$, and $n_1 < n$,
$$\sum_{i=1}^k n_i \log \frac{n}{n_i} \geq \sum_{i=1}^k n_i \log \frac{n}{n_1}$$
$$ \geq n \log \frac{n}{n_1} = \omega (1/2 \log \frac{n}{n_1})$$

Therefore, 
$$1/2 \log \frac{n}{n_1}+ \sum_{i=1}^k n_i \log \frac{n}{n_i} \sim \sum_{i=1}^k n_i \log \frac{n}{n_i}$$
\end{enumerate}

\item Suppose $n$ is a power of $2$ and each $n_i$ is also a power of $2$.
What is the length of the codeword for $a_i$ ? Using this show 
that in this case the Huffman encoding is truly optimal, i.e., it
exactly matches the lower bound above. 

We will prove that the codeword for $a_i$ has $\log \frac{n}{n_i}$ 
bits exactly by induction on the size of the alphabet. 
For this we need a small lemma:

\begin{lemma}
In any set of powers of two (with two or more elements) 
that add up to a power of two, the smallest
two numbers must be equal.
\end{lemma}

{\em Proof. }
By contradiction. 
Let the numbers be $2^{b_1},2^{b_2},\ldots,2^{b_k}$ which
add up to $2^b$ where
$b_1 < b_2 \leq \ldots \leq b_k$. Then we can divide
throughout by $2^{b_1}$ to get the numbers $1,2^{b_2-b_1},\ldots,2^{b_k-b_1}$
which add up to $2^{b-b_1}$. But the sum of this set of numbers
is odd whereas $2^{b-b_1}$ is even. A contradiction. So $b_1 = b_2$.\qed


Now we can prove the statement of the problem by induction on $k$.

$P(k):$  For all $i=1,\ldots,k$, $a_i$ is a leaf at depth $\log \frac{n}{n_i}$
in a Huffman tree.

Base: $k=2$  $n_1 = n_2 = n/2$. Each is at depth $\log 2 = 1$.

Ind. Step: Assume $P(k-1)$. To prove $P(k)$, let $a_1$ and $a_2$
be the letters chosen in the first step of the algorithm for $k$ letters.
From the lemma above $n_1 = n_2$. Consider
the set of messages with $k-1$ letters and frequencies 
$n_1+n_2,n_3,\ldots,n_k$. Since $n_1=n_2$, $n_1+n_2$ is a power of two.
By the inductive hypothesis the letters $a_i, i > 2$ are at depth
$\log \frac{n}{n_i}$. The letter with frequency $n_1+n_2$
is at depth $\log \frac {n}{n_1+n_2} = \log \frac{n}{n_1} -1 = \log \frac{n}{n_2} -1$. Then the algorithm for $k$ letters will attach $a_1$ and $a_2$ at
the node representing the letter with frequency $n_1+n_2$. So $a_1$
and $a_2$ are at depth $\log \frac{n}{n_1}$ and $\log \frac{n}{n_2}$ (which
are equal.


Since the letter $a_i$ is encoded using $\log \frac{n}{n_i}$ bits,
the total length of a message is $\sum_{i=1}^k n_i \log \frac{n}{n_i}$
which matches our lower bound. 

\item Find a set of frequency counts where the Huffman encoding of strings
with those frequency counts is much longer than the bound above (Hint: 
consider an alphabet of size 2.) 

Consider an alphabet with two letters $a_1,a_2$. The Huffman
encoding is 1 bit for each one, so a message of length $n$ uses
$n$ bits.

Let $n_1 = \alpha n $ and $n_2 = (1-\alpha) n$.
The lower bound we get is $n (\alpha \log \frac{1}{\alpha} + (1-\alpha) \log \frac{1}{1-\alpha})$. As $\alpha$ tends to 1 this tends to zero.

E.g. for $\alpha = 1/2^{100}$, the lower bound is 
$$ < n ( \frac{100}{2^{100}} + (1-1/2^{100}) \log \frac{1}{1-1/2^{100}})$$ 
$$ \leq n (\frac{100}{2^{100}} + (1-1/2^{100}) \log (1+1/2^{99}))$$
$$ \leq n (\frac{100}{2^{100}} + (1-1/2^{100}) 1/2^{99})$$
(using the fact that $1+x \leq e^x$ for $x >0$.)
$$ \leq n/2^{93}$$
Which is much less than $n$.

Note: Huffman codes are close to the optimal except in extreme
cases like the above where one letter dominates.

\end{enumerate}

\end{document}
