 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

Pinsker's inequality

Article Id: WHEBN0020064401
Reproduction Date:

 Title: Pinsker's inequality Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

Pinsker's inequality

In information theory, Pinsker's inequality, named after its inventor Mark Semenovich Pinsker, is an inequality that bounds the total variation distance (or statistical distance) in terms of the Kullback–Leibler divergence. The inequality is tight up to constant factors.

Contents

• Formal statement 1
• History 2
• Inverse problem 3
• References 4

Formal statement

Pinsker's inequality states that, if P and Q are two probability distributions, then

\delta(P,Q) \le \sqrt{\frac{1}{2} D_{\mathrm{KL}}(P\|Q)}

where

\delta(P,Q)=\sup \{ |P(A) - Q(A)| : A\text{ is an event to which probabilities are assigned.} \}

is the total variation distance (or statistical distance) between P and Q and

D_{\mathrm{KL}}(P\|Q) = \sum_i \ln\left(\frac{P(i)}{Q(i)}\right) P(i)\!

is the Kullback–Leibler divergence in nats.

History

Pinsker first proved the inequality with a worse constant. The inequality in the above form was proved independently by Kullback, Csiszár, and Kemperman.

Inverse problem

An inverse of the inequality cannot hold: for every \epsilon > 0, there are distributions with \delta(P,Q)\le\epsilon but D_{\mathrm{KL}}(P\|Q) = \infty.