Pinsker's widely used inequality upper-bounds the total variation distance
${||P-Q||}_1$ 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^*(P,\epsilon)$ --- defined, for an arbitrary
fixed $P$, as the infimum of $D(P||Q)$ over all distributions $Q$ that are
$\epsilon$-far away from $P$ in total variation. We show that $D^*(P\epsilon)\le C_\epsilon^2 + O(\epsilon^3)$, where $C=C(P)=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.
arXiv:1206.6544