Gibbs' Inequality - Proof

Proof

Since

it is sufficient to prove the statement using the natural logarithm (ln). Note that the natural logarithm satisfies

for all x with equality if and only if x=1.

Let denote the set of all for which pi is non-zero. Then

\begin{align} - \sum_{i \in I} p_i \ln \frac{q_i}{p_i} & {} \geq - \sum_{i \in I} p_i \left( \frac{q_i}{p_i} - 1 \right) \\ & {} = - \sum_{i \in I} q_i + \sum_{i \in I} p_i \\ & {} = - \sum_{i \in I} q_i + 1 \\ & {} \geq 0. \end{align}

So

and then trivially

since the right hand side does not grow, but the left hand side may grow or may stay the same.

For equality to hold, we require:

  1. for all so that the approximation is exact.
  2. so that equality continues to hold between the third and fourth lines of the proof.

This can happen if and only if

for i = 1, ..., n.

Read more about this topic:  Gibbs' Inequality

Famous quotes containing the word proof:

    “There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
    —Herman Melville (1819–1891)

    “The chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
    —H.L. (Henry Lewis)

    “From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
    —Johan Huizinga (1872–1945)