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:

    “If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
    —Thomas Jefferson (1743–1826)

    “To cease to admire is a proof of deterioration.”
    —Charles Horton Cooley (1864–1929)

    “It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
    —William Shakespeare (1564–1616)