# A different proof for KL divergence non-negativity

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).

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.