Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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).

share|improve this question
    
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)$$ –  Ashok 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. –  Ben Charrow May 21 '12 at 15:53

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.