## Thursday, June 1, 2006

### Stop Being So Cheap. Topic: Calculus/Inequalities. Level: Olympiad.

Problem: Minimize the average cost function $\displaystyle C(l_1, l_2, \ldots, l_m) = \sum_{i=1}^m p_ic_il_i$ where $p_i$ and $c_i$ for $i = 1, 2, \ldots, m$ are constants (representing probability and cost per letter of a codeword) and $l_i$ for $i = 1, 2, \ldots, m$ are variables (representing codeword length) subject to the constraint $\displaystyle \sum_{i=1}^m 2^{-l_i} \le 1$.

Solution: Assume all summations run from $1$ to $m$. Now, let's put our favorite technique Langrange multipliers to the use! We see that we must have equality to minimize $C$ (or we could just decrease and arbitrary $l_i$) so let

$\displaystyle g(l_1, l_2, \ldots, l_m) = \left(\sum 2^{-l_i}\right) - 1 = 0$

Then we have

$C_{l_i} = p_ic_i = \lambda g_{l_i} = \lambda(\ln{(2)} \cdot 2^{-l_i})$,

where $C_{l_i}$ and $g_{l_i}$ are the partial derivatives of $C$ and $g$ with respect to $l_i$. So

$2^{-l_i} = \frac{p_ic_i}{\ln{(2)} \cdot \lambda}$.

Then we substitute back into our constraint $g$ to get

$\displaystyle g(l_1, l_2, \ldots, l_m) = \left(\sum 2^{-l_i}\right) - 1 = \left(\sum \frac{p_ic_i}{\ln{(2)} \cdot \lambda} \right) - 1 = 0$,

which gives us

$\displaystyle \lambda = \frac{\sum p_ic_i}{\ln{(2)}}$,

so, solving from our equation above,

$\displaystyle l_i = -\log_2{\left(\frac{p_ic_i}{\sum p_ic_i}\right)}$.

Hence we have our minimum $C$ as

$\displaystyle C_{min} = \sum p_ic_il_i = -\sum p_ic_i \log_2{\left(\frac{p_ic_i}{\sum p_ic_i}\right)} = \sum p_ic_i \log_2{\left(\frac{\sum p_ic_i}{p_ic_i}\right)}$.

QED.

--------------------

Comment: Here we have a real-world application of the technique of Lagrange multipliers, a common optimization technique in multivariate calculus. In actuality, the $l_i$ need to be restricted to integers, but this gives us a lower bound that can be achieved in special cases. It can be further shown that an optimal code has an average cost of at most

$\displaystyle C_{min} + \sum p_ic_i$.