Aryeh Kontorovich

Pinsker's widely used inequality upper-bounds the total variation distance ||P - Q||₁ in terms of the Kullback-Leibler divergence D(P||Q). Although, in general, a bound in the reverse direction is impossible, in many applications the quantity of interest is actually D*(v, Q) - defined, for an arbitrary fixed Q, as the infimum of D(P||Q) over all distributions P that are at least v-far away from Q in total variation. We show that D*(v, Q) ≤ Cv² + O(v³), where C = C(Q) = 1/2 for balanced distributions, thereby providing a kind of reverse Pinsker inequality. Some of the structural results obtained in the course of the proof may be of independent interest. An application to large deviations is given.