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