Q. 9.13 - A First Course in Probability

Question

Prove that if X can take on any of n possible values with respective probabilities P1, ... ,Pn, then H(X) is maximized when Pi = 1/n, i = 1, ... , n. What is H(X) equal to in this case? 

Step-by-Step Solution

Answer

The required statement is proved in below step.

Step 1: Given Information

We have to find $H\left(X\right)$ and prove the given statement.

Step 2: Simplify

Considering the problem of maximization

$H(p_1,...,p_n)=-\sum _{i=1}^n{p}_i{\log }_2{p}_i$

with condition $\sum _{i=1}^n{p}_i=1.$

Considering the Langrangian function

$\mathcal{L}(p_1,...p_n,\lambda )=$$-\sum _{i=1}^n{p}_i{\log }_2{p}_i-\lambda \left(\underset{i=1}{\overset{n}{\sum P_i}}-1\right)$

With differentiation, we will get the system of equations

$$\begin{gathered} \frac{\partial ℒ}{\partial p_i}=-\left[{\log }_2{P}_i+\frac{1}{\log 2}\right]-\lambda =0,i=1,...,n \\ \frac{\partial ℒ}{\partial \lambda }=\underset{i=1}{\overset{n}{\sum p_i}}-1=0 \end{gathered}$$

If we look at the first equality a little bit better, we have that

${\log }_2{p}_1+\frac{1}{\log 2}=-\lambda ={\log }_2{p}_j+\frac{1}{\log 2}$

for every $i,j.$ it implies that $p_i=p_j$ for every $i$and $j$. Hence, putting these information in the last equality, we have

$n{p}_1-1=0\Rightarrow p_1=\frac{1}{n}$

which implies $p_i=\frac{1}{n}.$

Hence, we have proved the statement.