14
$\begingroup$

How to prove the following known (Pinsker's) inequality?

For two strictly positive sequences $(p_i)^n_{i=l}$ and $(q_i)^n_{i=l}$ with $\sum_{i=1}^np_i=\sum_{i=1}^nq_i=1$ one has $$\sum_{i=1}^np_i\log\frac{p_i}{q_i}\ge \frac{1}{2}\left(\sum_{i=1}^n|p_i-q_i|\right)^2.$$

$\endgroup$
5
  • 1
    $\begingroup$ Retagged due to the relation to Kullback-Leibler_divergencecomments may only be edited for 5 minutes(click on this box to dismiss) $\endgroup$
    – Ilya
    Apr 4, 2012 at 13:14
  • $\begingroup$ If it is known, does it have a name? Where did you find it and was a reference to a proof missing? $\endgroup$
    – Aryabhata
    Apr 4, 2012 at 17:15
  • $\begingroup$ @Aryabhata yes it is known. Pinsker's inequality: mathoverflow.net/questions/42667/… $\endgroup$
    – Kolmo
    Apr 4, 2012 at 18:35
  • $\begingroup$ @Kolmo: Please add an answer. Also, my point was OP knows it is known, and if OP knew the name, they could have done some research before posting it here. $\endgroup$
    – Aryabhata
    Apr 4, 2012 at 18:51
  • 1
    $\begingroup$ Check also Beck & Teboulle 2003, "Mirror descent and nonlinear projected subgradient methods for convex optimization", Proposition 5.1 for elementary proof of a weaker inequality with symmetrized KL-divergence. $\endgroup$
    – ostrodmit
    Sep 15, 2015 at 9:51

2 Answers 2

7
$\begingroup$

See here. Pinsker's inequality

https://mathoverflow.net/questions/42667/two-reference-requests-pinskers-inequality-and-pontryagin-duality

$\endgroup$
3
  • $\begingroup$ Is there a simpler proof? $\endgroup$
    – Sunni
    Apr 4, 2012 at 20:17
  • $\begingroup$ I find a simpler one from Borwein\& Levis, 2005, page 63. $\endgroup$
    – Sunni
    Apr 10, 2012 at 19:25
  • $\begingroup$ @Kolmo can you please point out the condition for equality in Pinsker's inequality? $\endgroup$ Nov 12, 2016 at 9:14
5
$\begingroup$

Take a look at Tsybakov 2009 Introduction to Nonparametric Estimation, p.88, also available in the net. Good and simple proof.

$\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.