Question

Entropy: Consider a distribution over$\mathit{n}$possible outcomes, with probabilities ${\mathbf{p}}_{\mathbf{1}}\mathbf{,}{\mathbf{p}}_{\mathbf{2}}\mathbf{,}\mathbf{K}\mathbf{,}{\mathbf{p}}_{\mathbf{n}}$.

a. Just for this part of the problem, assume that each ${\mathit{p}}_{\mathbf{i}}$is a power of 2 (that is, of the form $\mathbf{1}\mathbf{/}{\mathbf{2}}^{\mathbf{k}}$). Suppose a long sequence of $\mathit{m}$samples is drawn from the distribution and that for all $\mathbf{1}\mathbf{\le }\mathbf{i}\mathbf{\le }\mathbf{n}$, the ${\mathit{i}}^{\mathbf{t}\mathbf{h}}$outcome occurs exactly times in the sequence. Show that if Huffman encoding is applied to this sequence, the resulting encoding will have length

$\mathbf{\sum }_{\mathbf{i}\mathbf{-}\mathbf{1}}^{\mathbf{n}}\mathit{m}{\mathit{p}}_{\mathbf{i}}\mathit{l}\mathit{o}\mathit{g}\frac{\mathbf{1}}{{\mathbf{p}}_{\mathbf{i}}}$

b. Now consider arbitrary distributions-that is, the probabilities ${\mathit{p}}_{\mathbf{i}}$ are noy restricted to powers of 2. The most commonly used measure of the amount of randomness in the distribution is the entropy.

$\mathbf{\sum }_{\mathbf{i}\mathbf{-}\mathbf{1}}^{\mathbf{n}}\mathit{m}{\mathit{p}}_{\mathbf{i}}\mathit{l}\mathit{o}\mathit{g}\frac{\mathbf{1}}{{\mathbf{p}}_{\mathbf{i}}}$

For what distribution (over outcomes) is the entropy the largest possible? The smallest possible?

Short answer

1. It can be proved that the length of the sequence is $\sum _{i-1}^{n}m{p}_i\log \frac{1}{p_i}$.
2. $p_i=\frac{1}{n}$ is the largest entropy. $p_k=1,p_{i,\left(i\ne k\right)}=0$is the smallest entropy.

Step-by-step solution

Explain the information given

Consider a distribution over possible outcomes with probabilities $p_1,p_2,K{p}_n$. Assume that each $p_i$is a power of 2. Consider the long sequence of $m$samples is drawn from the distribution and for all $1\le i\le n$, $i^{th}$the outcome occurs exactly $m{p}_i$times in the sequence.

Step 2:Show the length of the sequence

(a)

Consider the encoded length of the element $p_i$is with the probability $\log \frac{1}{p_i}$. The probability of $\frac{1}{2^k}$is 1. The $c\left(k\right)$is at the level $k$in Huffman tree (assuming that the root is at level 0) and $\frac{1}{2}>\frac{2}{5}$, and for all role="math" localid="1659009731170" $\frac{1}{2^n}<\frac{1}{3},\left(n>1\right)$. Since the outcome is $c\left(\frac{1}{2}\right)$ and the probability of all the elements in the first layer is 1.

Consider the root to be 1, the subtree must be at the first level and this level elements have the probability $\left(\frac{1}{4}\right)$.Then the probability $c\left(k\right)$, results in the Huffman code is reduced to the length role="math" localid="1659010017242" $\sum _{i=1}^{n}m{p}_i\log \frac{1}{p_i}$.

Therefore, the length of the sequence is role="math" localid="1659010031265" $\sum _{i=1}^{n}m{p}_i\log \frac{1}{p_i}$.

Step 3:Calculate the entropy of largest possible and the smallest possible.

(b)

$p_i=\frac{1}{n}$ is the largest entropy. $p_k=1,p_{i,\left(i\ne k\right)}=0$is the smallest entropy.

Therefore, the largest and the smallest possible entropies are obtained.