Gibbs' inequality

In the information theory, the Gibbs inequality (after JW Gibbs ) an indication of the entropy of a discrete probability distribution. This gives her a lower bound of the average codeword length of optimal prefix codes and a lower bound of the average term of comparison-based sorting algorithm.

Gibbs inequality

Let and discrete probability distributions, ie for all and. Then:

Equality occurs if and only if for all.

Evidence

For all the inequality holds, where equality occurs only in the fall.

If, for a particular, one obtains.

Multiplying the inequality by and by summing over all, we obtain

After, it follows

Bring to the two terms on the respective opposite side, so is

Instead of the natural logarithm can be just as good any other logarithm base hernehmen as is.

You need the inequality by this divide only by the positive number.

In information theory, it makes sense to choose as a base.

Conclusions

For the entropy

With equality if and only if for all.

If discrete random variables, then

With equality if and only if and are stochastically independent.

Some useful applications arising in connection with the power inequality. Be added a complete binary tree with the leaf depths and the leaves associated probability distribution. Then by:

The mean chord length is therefore limited from below by the entropy of the corresponding probability distribution.

So then it is clear that the average code word length of an optimal prefix code from below by the entropy of the respective probability distribution of the symbols is limited. Equality holds here if and only if for all, with the codeword length of th code word denotes.

For comparison-based sorting algorithm of elements under the uniform distribution assumption, by considering the mean chord length of the binary decision tree, the lower bound. The average -case running time of a comparison-based sorting method behaves asymptotically like.