13
$\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$
  • 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 '12 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 '12 at 17:15
  • $\begingroup$ @Aryabhata yes it is known. Pinsker's inequality: mathoverflow.net/questions/42667/… $\endgroup$ – Kolmo Apr 4 '12 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 '12 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 '15 at 9:51
6
$\begingroup$

See here. Pinsker's inequality

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

$\endgroup$
  • $\begingroup$ Is there a simpler proof? $\endgroup$ – Sunni Apr 4 '12 at 20:17
  • $\begingroup$ I find a simpler one from Borwein\& Levis, 2005, page 63. $\endgroup$ – Sunni Apr 10 '12 at 19:25
  • $\begingroup$ @Kolmo can you please point out the condition for equality in Pinsker's inequality? $\endgroup$ – Karthik Nov 12 '16 at 9:14
4
$\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.