{"id":18270,"date":"2023-08-24T16:00:15","date_gmt":"2023-08-24T14:00:15","guid":{"rendered":"https:\/\/djalil.chafai.net\/blog\/?p=18270"},"modified":"2024-02-14T10:01:42","modified_gmt":"2024-02-14T09:01:42","slug":"a-reverse-pinsker-inequality","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2023\/08\/24\/a-reverse-pinsker-inequality\/","title":{"rendered":"A reverse Pinsker inequality"},"content":{"rendered":"
\"Photo<\/a>
Solomon Kullback (1907 \u2013 1994)<\/figcaption><\/figure>\n

This tiny post is devoted to a cute reverse Pinsker inequality, extracted from a recent work of my colleague Justin Salez. This reverse Pinsker inequality is at the heart of his investigation of the cutoff phenomenon, in total variation distance, for Markov chains, that we do not discuss here.<\/p>\n

Pinsker inequality.<\/strong> If $\\mu$ and $\\nu$ are probability measures on the same probability space, it reads
\n\\[
\n2\\|\\mu-\\nu\\|_{\\mathrm{TV}}^2\\leq\\mathrm{Entropy}(\\nu\\mid\\mu)
\n\\] where
\n\\[
\n\\mathrm{Entropy}(\\nu\\mid\\mu):=\\int\\frac{\\mathrm{d}\\nu}{\\mathrm{d}\\mu}\\log\\frac{\\mathrm{d}\\nu}{\\mathrm{d}\\mu}\\mathrm{d}\\mu.
\n\\] is the Kullback-Leibler divergence or relative entropy of $\\nu$ with respect to $\\mu$, and where
\n\\[
\n\\|\\mu-\\nu\\|_{\\mathrm{TV}}:=\\sup_A|\\mu(A)-\\nu(A)|
\n\\] is the total variation distance between $\\mu$ and $\\nu$. By convention $\\mathrm{Entropy}(\\nu\\mid\\mu)=+\\infty$ if $\\frac{\\mathrm{d}\\nu}{\\mathrm{d}\\nu}$ does not exist, and in this case the inequality is useless. The constant $2$ is optimal as one can check on Bernoulli distributions. The inequality was first proved by Mark S. Pinsker (1925 \u2013 2003) with another constant, and later on and independently by Solomon Kullback (1907 \u2013 1994) and Imre Csisz\u00e1r (1938 \u2013 ). Let us give now a quick proof, due to Johannes H. B. Kemperman (1924 \u2013 2011). Using $\\|\\mathrm{1}_A-\\mathrm{1}_{A^c}\\|_\\infty\\leq1$, the $L^1-L^\\infty$ duality, the convexity inequality \\[ 3(u-1)^2\\leq(2u+4)(u\\log u-u+1),\\quad u\\geq0,\\]and the Cauchy-Schwarz inequality, we get, with $\\alpha:=\\alpha_{\\nu\\mid\\mu}:=\\frac{\\mathrm{d}\\nu}{\\mathrm{d}\\mu}$, \\begin{align*}
\n2\\|\\mu-\\nu\\|_{\\mathrm{TV}}
\n&\\leq\\sup_{\\|f\\|_\\infty\\leq1}\\int f\\mathrm{d}(\\mu-\\nu)\\\\
\n&=\\int|\\alpha-1|\\mathrm{d}\\mu\\\\
\n&\\leq\\int\\sqrt{\\frac{2\\alpha+4}{3}}\\sqrt{\\alpha\\log\\alpha-\\alpha+1}\\mathrm{d}\\mu\\\\
\n&\\leq\\sqrt{\\int\\frac{2\\alpha+4}{3}\\mathrm{d}\\mu}\\sqrt{\\int\\alpha\\log\\alpha\\mathrm{d}\\mu}\\\\
\n&=\\sqrt{2\\int\\alpha\\log\\alpha\\mathrm{d}\\mu}\\\\
\n&=\\sqrt{2\\mathrm{Entropy}(\\nu\\mid\\mu)}.
\n\\end{align*} Note that $\\left\\|\\cdot\\right\\|_{\\mathrm{TV}}$ takes its values in $[0,1]$ while $\\mathrm{Entropy}$ takes its values in $[0,+\\infty]$. Indeed if $\\mathrm{d}\\nu=\\frac{\\mathrm{1}_A}{\\mu(A)}\\mathrm{d}\\mu$, then $\\|\\mu-\\nu\\|_{\\mathrm{TV}}=1-\\mu(A)$ while $\\mathrm{Entropy}(\\nu\\mid\\mu)=-\\log\\mu(A)\\to+\\infty$ as $\\mu(A)\\to0$. Also we cannot expect a direct reverse Pinsker inequality.<\/p>\n

Varentropy.<\/strong> The relative entropy can be seen as the mean of a log :
\n\\[
\n\\mathrm{Entropy}(\\nu\\mid\\mu)=\\int\\beta_{\\nu\\mid\\mu}\\mathrm{d}\\nu
\n\\quad\\text{where}\\quad
\n\\beta_{\\nu\\mid\\mu}:=\\log\\frac{\\mathrm{d}\\nu}{\\mathrm{d}\\mu}.
\n\\] The variance of $\\beta_{\\nu\\mid\\mu}$ or varentropy is
\n\\begin{align*}
\n\\mathrm{Varentropy}(\\nu\\mid\\mu)
\n&:=
\n\\mathrm{Var}_\\nu(\\beta_{\\nu\\mid\\mu})\\\\
\n&=\\int(\\beta_{\\nu\\mid\\mu}-\\mathrm{Entropy}(\\nu\\mid\\mu))^2\\mathrm{d}\\nu\\\\
\n&=\\int\\beta_{\\nu\\mid\\mu}^2\\mathrm{d}\\nu-\\mathrm{Entropy}(\\nu\\mid\\mu)^2.
\n\\end{align*} If $\\mathrm{d}\\nu=\\frac{\\mathrm{1}_A}{\\mu(A)}\\mathrm{d}\\mu$ then $\\beta_{\\nu\\mid\\mu}$ is constant on $A=\\mathrm{supp}(\\nu)$ and $\\mathrm{Varentropy}(\\nu\\mid\\mu)=0$.<\/p>\n

A reverse Pinsker inequality.<\/strong> It reads
\n\\[
\n\\mathrm{Entropy}(\\nu\\mid\\mu)
\n\\leq\\frac{1+\\sqrt{\\mathrm{Varentropy}(\\nu\\mid\\mu)}}{1-\\|\\mu-\\nu\\|_{\\mathrm{TV}}}.
\n\\] In particular for all $\\varepsilon\\in(0,1)$,
\n\\[
\n\\|\\mu-\\nu\\|_{\\mathrm{TV}}\\leq\\varepsilon
\n\\quad\\Longrightarrow\\quad
\n\\mathrm{Entropy}(\\nu\\mid\\mu)
\n\\leq\\frac{1+\\sqrt{\\mathrm{Varentropy}(\\nu\\mid\\mu)}}{1-\\varepsilon}.
\n\\] Let us give a proof. Let us set $\\varepsilon:=\\|\\mu-\\nu\\|_{\\mathrm{TV}}$. Consider the event
\n\\[
\nA:=\\Bigr\\{\\frac{\\mathrm{d}\\nu}{\\mathrm{d}\\mu}\\geq\\mathrm{e}^\\theta\\Bigr\\}
\n\\quad\\text{where}\\quad
\n\\theta:=\\mathrm{Entropy}(\\nu\\mid\\mu)-\\frac{\\sqrt{\\mathrm{Varentropy}(\\nu\\mid\\mu)}}{1-\\varepsilon}.
\n\\] The Chebyshev inequality gives\\begin{align*}
\n\\nu(A^c)
\n&=\\nu(\\beta_{\\nu\\mid\\mu}<\\theta)\\\\
\n&=\\nu\\Bigr(\\beta_{\\nu\\mid\\mu}-\\mathrm{Entropy}(\\nu\\mid\\mu)<-\\frac{\\sqrt{\\mathrm{Varentropy}(\\nu\\mid\\mu)}}{1-\\varepsilon}\\Bigr)\\\\
\n&\\leq(1-\\varepsilon)^2,
\n\\end{align*} hence $\\nu(A)\\geq1-(1-\\varepsilon)^2$. On the other hand, the definition of $A$ gives
\n\\[
\n\\mu(A)\\leq\\mathrm{e}^{-\\theta}\\nu(A).
\n\\] These two inequalities together give
\n\\[
\n\\nu(A)-\\mu(A)\\geq(1-(1-\\varepsilon)^2)(1-\\mathrm{e}^{-\\theta}).
\n\\] Now since $\\|\\mu-\\nu\\|_{\\mathrm{TV}}=\\varepsilon$, we get $\\varepsilon\\geq(1-(1-\\varepsilon)^2)(1-\\mathrm{e}^{-\\theta})$, in other words
\n\\[
\n\\theta\\leq\\log\\Bigr(1+\\frac{1}{1-\\varepsilon}\\Bigr).
\n\\] Finally, the convexity inequality $\\log(1+u)\\leq u$ gives $\\theta\\leq1\/(1-\\varepsilon)$, as expected.<\/p>\n

If $\\mathrm{d}\\nu=\\frac{\\mathrm{1}_A}{\\mu(A)}\\mathrm{d}\\mu$ then the reverse Pinsker inequality above reads $-\\mu(A)\\log\\mu(A)\\leq1$.<\/p>\n

Fisher information and Poincar\u00e9 inequality.<\/strong> The logarithmic Fisher information is defined by
\n\\[
\n\\mathrm{Fisher}(\\nu\\mid\\mu)
\n:=\\int|\\nabla\\beta_{\\nu\\mid\\mu}|^2\\mathrm{d}\\nu
\n=\\int\\frac{|\\nabla\\frac{\\mathrm{d}\\nu}{\\mathrm{d}\\mu}|^2}{\\frac{\\mathrm{d}\\nu}{\\mathrm{d}\\mu}}\\mathrm{d}\\mu.
\n\\] Also we have, denoting $c_{\\mathrm{PI}}(\\nu)$ the Poincar\u00e9 inequality constant of $\\nu$ :
\n\\[
\n\\mathrm{Varentropy}(\\nu\\mid\\mu)
\n=
\n\\mathrm{Var}_\\nu(\\beta_{\\nu\\mid\\mu})
\n\\leq c_{\\mathrm{PI}}(\\nu)\\int|\\nabla\\beta_{\\nu\\mid\\mu}|^2\\mathrm{d}\\nu
\n=c_{\\mathrm{PI}}(\\nu)\\mathrm{Fisher}(\\nu\\mid\\mu).
\n\\] Combined with the reverse Pinsker inequality above, this gives
\n\\[
\n\\mathrm{Entropy}(\\nu\\mid\\mu)
\n\\leq\\frac{1+\\sqrt{c_{\\mathrm{PI}}(\\nu)\\mathrm{Fisher}(\\nu\\mid\\mu)}}{1-\\|\\mu-\\nu\\|_{\\mathrm{TV}}}.
\n\\]<\/p>\n

Note.<\/strong> There are plenty of alternate or reverse Pinsker inequalities. For instance the Bretagnolle-Huber inequality, used for hypothesis testing in Statistics, reads \\[\\|\\mu-\\nu\\|_{\\mathrm{TV}}^2\\leq1-\\mathrm{e}^{-\\mathrm{Entropy}(\\nu\\mid\\mu)},\\]and has the advantage over Pinsker of being informative even when $\\mathrm{Entropy}(\\nu\\mid\\mu)\\geq2$.<\/p>\n

Further reading.<\/strong><\/p>\n