Optimal Code Length Using Lagrange Multipliers

Let a source emit $n$ symbols $\{x1,x2,$dots,$xn\}$ with known probabilities

$\{p1,p2,$dots,$pn\},$ where ${\displaystyle \underset{i=1}{\overset{n}{}}}=1p_i>0$ for all $i.$

Let the code length assigned $to$ symbol $xibeli,$ and suppose $we$ are

designing a binary prefix$-$free code. According $to$ Kraft's

inequality, $we$ must have:

${\displaystyle \underset{i=1}{\overset{n}{}}}{2}^{-l}1$

$To$ minimize expected code length, $we$ aim $to$ minimize the average

length:

$\frac{?}{\text{b}\text{a}\text{r}}(L)={\displaystyle \underset{i=1}{\overset{n}{}}}li=1$

Use Lagrange multipliers $to$ find the soptimal code lengths $\{li\}$

that minimize the average code length $\frac{?}{\text{b}\text{a}\text{r}}(L)$ under the constraint:

${\displaystyle \underset{i=1}{\overset{n}{}}}{2}^{-l}=1$

That $is,$ convert the inequality constraint into $an$ equality constraint

for the purpose $of$ optimization.

$(a)$ What $is$ the form $of$ the optimal code length $liin$ terms $of{p}_i?$

$(b)$ Compare the result $to$ Shannon's optimal code length

formula and explain.