# Bounding Entropy in terms of KL-Divergence

Let $h(X)$ be the differential entropy of a continuous random variable $X$ with density $f$, and let $Y$ be another continuous random variable with density $g$. If $KL(X\mid\mid Y)$ is the Kullback-Leibler Divergence between the two, and I know that $KL(X\mid\mid Y)<\alpha$, then can I say anything about $d(H(X),H(Y))$ where $d$ is any metric (e.g. euclidean, L1, etc.)?

I know that $KL(X\mid\mid Y) = H(X,Y)-H(X)$ where $H(X,Y)=\int f(x) \log g(x)dx$ is the cross-entropy. However, I haven't been able to do anything with this. I feel like I'm missing something pretty basic here, but haven't been able to make any progress, nor did I immediately find something in "Elements of Information Theory" (Cover and Thomas).

• There are some issues with your notation and definition. $H(X,Y)$ usually denoted the joint entropy of $X$ and $Y$ and $KL(X\|Y)=\int f\log (f/g)=\int f\log f-\int f\log g$ when the integrals exist. With the given information one can say that $$|H(X)-H(Y)|<\alpha+\int f\log g+H(Y) \text{ when } H(X)\le H(Y)$$ and $$|H(X)-H(Y)|>-\alpha-\int f\log g-H(Y) \text{ when } H(X)>H(Y)$$ May 19 '12 at 6:35
• Thanks for the bounds! What notation would you use for cross-entropy? As far as I can tell, there isn't an established standard. I know that I'm overloading $H(X,Y)$, but this is what I've seen elsewhere. May 21 '12 at 15:53

I interpret the question as asking for an upper bound on $d(H(X),H(Y))$ that merely depends on $\alpha$ (or on $KL(X||Y)$), but which does not depend on other quantities like $H(X)$ or $g$.
Such an upper bound, however, cannot exist for continuous random variables $X$ and $Y$ (unless the metric $d(\cdot,\cdot)$ is itself bounded). To see this, one can look at the following specific example of random variables $X$ and $Y$ with densities $f=h_{(1+t)/2,D}$ and $g=h_{(1-t)/2,D}$, respectively, where $t\in[-1,1]$ and $D>1$ are any fixed real parameters and the density $h_{r,D}$ is defined on the real line (i.e. for $x\in{\mathbb{R}}$) as $$h_{r,D}(x):={\left\{\begin{array}{ll}1-r&\text{for}~x\in[0,1)\\r/(D-1)&\text{for}~x\in[1,D]\\0&\text{otherwise}.\end{array}\right.}$$ For these random variables, $KL(X||Y)=t\log\frac{1+t}{1-t}$ can attain any desired positive value for some $t\neq0$, whereas $H(X)-H(Y)=t\log(D-1)$ can become arbitrarily large (positive or negative) as $D\to\infty$.
But in the case where $X$, $Y$ are discrete random variables with a finite number $n$ of outcomes (atomic events), then the following bound holds:$$|H(X)-H(Y)|\leq\sqrt{2\cdot KL(X||Y)}\log n.$$This bound (and a sharpened version) is proven in the paper http://arxiv.org/abs/1304.0036, from which also the above example is taken.