0
$\begingroup$

KL divergence's non-negativity can be proved in many ways. One could use the inequality $\log x \leq x - 1$ as a main step in the proof, another one could leverage the property of concave of the logarithm function to yield the non-negativity.

Although those proofs are concise and simple, I found they less obvious to come up with, particularly, for one who is not familiar with concavity and inequality.

Therefore, I am trying to find an alternative proof which doesn't require knowledge of logarithm inequality as well as concavity.

The following is what I've come up with:

$KL(p||q)\geq0$

$\Leftrightarrow\sum_i p_i \ln p_i \geq \sum_i p_i\ln q_i$

$\Leftrightarrow\sum_i \ln p_i^{p_i} \geq \sum_i p_i\ln q_i^{p_i}$

$\Leftrightarrow e^{\sum_i \ln p_i^{p_i}} \geq e^{\sum_i p_i\ln q_i^{p_i}}$

$\Leftrightarrow e^{\ln p_1^{p_1}}...e^{\ln p_n^{p_n}} \geq e^{\ln q_1^{p_1}}...e^{\ln q_n^{p_n}}$

$\Leftrightarrow p_1^{p_1}...p_n^{p_n} \geq q_1^{p_1}... q_n^{p_n}$

Constrains: $0\leq p_i,q_i \leq 1$ and $\sum_i p_i=1$ and $\sum_i q_i=1$

To prove that $KL(p||q)\geq0$ , now I need to prove that:

$ p_1^{p_1}...p_n^{p_n} \geq q_1^{p_1}... q_n^{p_n}$ $(*)$

Hopefully, $(*)$ is simpler to prove in terms of not using logarithm function. However, I am stuck here.

I would appreciate any idea helps to prove $(*)$ or corrections for the transformation (if any).

$\endgroup$
1
$\begingroup$

Let $f(\boldsymbol{q})=f(q_1,q_2,...,q_{n-1})=q_1^{p_1}q_2^{p_2}...q_{n-1}^{p_{n-1}}(1-\sum_{i=1}^{n-1}{q_i})^{1-\sum_{i=1}^{n-1}p_i}$. I just removed $p_n$, $q_n$ because they depend on other $p_i,q_i$. Here, we know $p_i$, and we try to maximize $f(\boldsymbol{q})$. In the end, we'll see that it's going to be maximized when $p_i=q_i$.

$$\frac{\partial f(\boldsymbol{q})}{\partial q_i}=p_iq_i^{p_i-1}(1-\sum_{k=1}^{n-1}{q_k})^{1-\sum_{k=1}^{n-1}p_k}-q_i^{p_i}(1-\sum_{k=1}^{n-1}{q_k})^{-\sum_{k=1}^{n-1}p_k}=0$$

Solving this yields $p_iq_n=q_1p_n$. Writing this for all $i$ in $1,2,...n-1$, yields $p_i=q_i$ via some algebra. So, any choice of $q_i$ other than $p_i$ yields a smaller $f(\boldsymbol{q})$. Leaving to prove that this is actually maximum to you.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.