**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 $.

## No comments:

## Post a Comment