Kullback's inequality

In information theory and statistics, Kullback's inequality is a lower bound on the Kullback–Leibler divergence expressed in terms of the large deviations rate function. If P and Q are probability distributions on the real line, such that P is absolutely continuous with respect to Q, i.e. P << Q, and whose first moments exist, then $$D_{KL}(P\parallel Q)\ge {\mathrm{\Psi }}_Q^{*}(\mu {\text{'}}_1(P)),$$ where ${\mathrm{\Psi }}_Q^{*}$ is the rate function, i.e. the convex conjugate of the cumulant-generating function, of $Q$, and $\mu {\text{'}}_1(P)$ is the first moment of $P.$

The Cramér–Rao bound is a corollary of this result.

Proof

Let P and Q be probability distributions (measures) on the real line, whose first moments exist, and such that P << Q. Consider the natural exponential family of Q given by $$Q_{\theta }(A)=\frac{\underset{A}{\int }{e}^{\theta x}Q(dx)}{\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}{e}^{\theta x}Q(dx)}=\frac{1}{M_Q(\theta )}\underset{A}{\int }{e}^{\theta x}Q(dx)$$ for every measurable set A, where $M_Q$ is the moment-generating function of Q. (Note that Q₀ = Q.) Then $$D_{KL}(P\parallel Q)=D_{KL}(P\parallel Q_{\theta })+\underset{\mathrm{supp}P}{\int }(\log \frac{\mathrm{d}{Q}_{\theta }}{\mathrm{d}Q})\mathrm{d}P.$$ By Gibbs' inequality we have $D_{KL}(P\parallel Q_{\theta })\ge 0$ so that $$D_{KL}(P\parallel Q)\ge \underset{\mathrm{supp}P}{\int }(\log \frac{\mathrm{d}{Q}_{\theta }}{\mathrm{d}Q})\mathrm{d}P=\underset{\mathrm{supp}P}{\int }(\log \frac{e^{\theta x}}{M_Q(\theta )})P(dx)$$ Simplifying the right side, we have, for every real θ where $M_Q(\theta )<\mathrm{\infty }:$ $$D_{KL}(P\parallel Q)\ge \mu {\text{'}}_1(P)\theta -{\mathrm{\Psi }}_Q(\theta ),$$ where $\mu {\text{'}}_1(P)$ is the first moment, or mean, of P, and ${\mathrm{\Psi }}_Q=\log M_Q$ is called the cumulant-generating function. Taking the supremum completes the process of convex conjugation and yields the rate function: $$D_{KL}(P\parallel Q)\ge \underset{\theta }{\sup }\{\mu {\text{'}}_1(P)\theta -{\mathrm{\Psi }}_Q(\theta )\}={\mathrm{\Psi }}_Q^{*}(\mu {\text{'}}_1(P)).$$

Corollary: the Cramér–Rao bound

Main article: Cramér–Rao bound

Start with Kullback's inequality

Let X_θ be a family of probability distributions on the real line indexed by the real parameter θ, and satisfying certain regularity conditions. Then $$\underset{h\to 0}{\lim }\frac{D_{KL}(X_{\theta +h}\parallel X_{\theta })}{h^2}\ge \underset{h\to 0}{\lim }\frac{{\mathrm{\Psi }}_{\theta }^{*}({\mu }_{\theta +h})}{h^2},$$

where ${\mathrm{\Psi }}_{\theta }^{*}$ is the convex conjugate of the cumulant-generating function of $X_{\theta }$ and ${\mu }_{\theta +h}$ is the first moment of $X_{\theta +h}.$

Left side

The left side of this inequality can be simplified as follows: $$\begin{array}{rl}\underset{h\to 0}{\lim }\frac{D_{KL}(X_{\theta +h}\parallel X_{\theta })}{h^2}& =\underset{h\to 0}{\lim }\frac{1}{h^2}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\log \left(\frac{\mathrm{d}{X}_{\theta +h}}{\mathrm{d}{X}_{\theta }}\right)\mathrm{d}{X}_{\theta +h}\\ & =-\underset{h\to 0}{\lim }\frac{1}{h^2}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\log \left(\frac{\mathrm{d}{X}_{\theta }}{\mathrm{d}{X}_{\theta +h}}\right)\mathrm{d}{X}_{\theta +h}\\ & =-\underset{h\to 0}{\lim }\frac{1}{h^2}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\log (1-(1-\frac{\mathrm{d}{X}_{\theta }}{\mathrm{d}{X}_{\theta +h}}))\mathrm{d}{X}_{\theta +h}\\ & =\underset{h\to 0}{\lim }\frac{1}{h^2}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}[(1-\frac{\mathrm{d}{X}_{\theta }}{\mathrm{d}{X}_{\theta +h}})+\frac{1}{2}{(1-\frac{\mathrm{d}{X}_{\theta }}{\mathrm{d}{X}_{\theta +h}})}^2+o\left({(1-\frac{\mathrm{d}{X}_{\theta }}{\mathrm{d}{X}_{\theta +h}})}^2\right)]\mathrm{d}{X}_{\theta +h}& & \text{Taylor series for }\log (1-t)\\ & =\underset{h\to 0}{\lim }\frac{1}{h^2}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\left[\frac{1}{2}{(1-\frac{\mathrm{d}{X}_{\theta }}{\mathrm{d}{X}_{\theta +h}})}^2\right]\mathrm{d}{X}_{\theta +h}\\ & =\underset{h\to 0}{\lim }\frac{1}{h^2}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\left[\frac{1}{2}{\left(\frac{\mathrm{d}{X}_{\theta +h}-\mathrm{d}{X}_{\theta }}{\mathrm{d}{X}_{\theta +h}}\right)}^2\right]\mathrm{d}{X}_{\theta +h}\\ & =\frac{1}{2}{{ℐ}}_X(\theta )\end{array}$$ which is half the Fisher information of the parameter θ.

Right side

The right side of the inequality can be developed as follows: $$\underset{h\to 0}{\lim }\frac{{\mathrm{\Psi }}_{\theta }^{*}({\mu }_{\theta +h})}{h^2}=\underset{h\to 0}{\lim }\frac{1}{h^2}\underset{t}{\sup }\{{\mu }_{\theta +h}t-{\mathrm{\Psi }}_{\theta }(t)\}.$$ This supremum is attained at a value of t=τ where the first derivative of the cumulant-generating function is $\mathrm{\Psi }{\text{'}}_{\theta }(\tau )={\mu }_{\theta +h},$ but we have $\mathrm{\Psi }{\text{'}}_{\theta }(0)={\mu }_{\theta },$ so that $${\mathrm{\Psi }}^{\prime }{\text{'}}_{\theta }(0)=\frac{d{\mu }_{\theta }}{d\theta }\underset{h\to 0}{\lim }\frac{h}{\tau }.$$ Moreover, $$\underset{h\to 0}{\lim }\frac{{\mathrm{\Psi }}_{\theta }^{*}({\mu }_{\theta +h})}{h^2}=\frac{1}{2{\mathrm{\Psi }}^{\prime }{\text{'}}_{\theta }(0)}{\left(\frac{d{\mu }_{\theta }}{d\theta }\right)}^2=\frac{1}{2\mathrm{Var}(X_{\theta })}{\left(\frac{d{\mu }_{\theta }}{d\theta }\right)}^2.$$

Putting both sides back together

We have: $$\frac{1}{2}{{ℐ}}_X(\theta )\ge \frac{1}{2\mathrm{Var}(X_{\theta })}{\left(\frac{d{\mu }_{\theta }}{d\theta }\right)}^2,$$ which can be rearranged as: $$\mathrm{Var}(X_{\theta })\ge \frac{(d{\mu }_{\theta }/d\theta {)}^2}{{{ℐ}}_X(\theta )}.$$

See also

• Kullback–Leibler divergence
• Cramér–Rao bound
• Fisher information
• Large deviations theory
• Convex conjugate
• Rate function
• Moment-generating function