4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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)$$ $\endgroup$
    – Ashok
    May 19, 2012 at 6:35
  • 1
    $\begingroup$ 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. $\endgroup$ May 21, 2012 at 15:53

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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