3
$\begingroup$

I am reading the book "Elements of information theory" by thomas M. Cover and Joy A. Thomas, second edition. In page 255 of the book there is a theorem:

For any random variables $X$ and estimator $\hat{X}$, $E(X - \hat{X})^2 \geq \frac{1}{2\pi e}e^{2h(X)}$. The proof uses at its core the fact that $var(X) \geq \frac{1}{2\pi e}e^{2h(X)}$.

Edit: I include here the proof:

$E(X-\hat{X})^2 \geq \min_{\hat{X}}E(X-\hat{X})^2 = E(X-E(X))^2 = var(X) \geq \frac{1}{2\pi e}e^{2h(X)}$

Right after the proof there is a corollary that says: Given side information $Y$ and estimator $\hat{X}(Y)$, it follows that: $E(X - \hat{X}(Y))^2 \geq \frac{1}{2\pi e}e^{2h(X|Y)}$, however, no further explanation is supplied for how to derive this corollary from the previous theorem.

I assume that if I fight the equations for a while I might be able to derive the corollary from something, however I can't manage to find a simple way to derive it from the previous theorem. I wonder if I miss something very simple here.

So far my best attempt was to split $(X - \hat{X}(Y))$ into $(X - Y) + (Y - \hat{X}(Y))$.

$\endgroup$

3 Answers 3

2
$\begingroup$

Apply the given result, which works for arbitrary $X$, to the conditional distribution $X(Y)$ whose differential entropy is $h(X|Y)$.

$\endgroup$
1
  • $\begingroup$ Two questions: 1. Is $X(Y)$ in your notation some kind of a random variable? If so, how is it defined? 2. The given result assumes that $\hat{X}$, the estimator of $X$, is constant (The proof uses this fact). In the second result it seems to me that $\hat{X}(Y)$ doesn't have to be a constant. It depends on $Y$. Hence I can't see how to apply the first result to the second one using your suggested method. $\endgroup$
    – real
    May 18, 2016 at 8:13
1
$\begingroup$

I propose here an answer using some calculations.

We want to prove that $E[(X-\hat{X}(Y))^2] \geq \frac{1}{2\pi e}e^{2h(X|Y)}$. Assuming that $X,Y$ are continuous random variables, we get:

$$E[(X-\hat{X}(Y))^2] = \int_{x,y} \left(x-\hat{X}(y)\right)^2 f(x,y)dxdy = \int_{x,y} \left(x-\hat{X}(y)\right)^2 f(y)f(x|y)dxdy$$

$$ = \int_{y} f(y)\left(\int_{x}\left(x-\hat{X}(y)\right)^2 f(x|y)dx\right)dy$$

Using the given theorem, we know that $$\int_{x}\left(x-\hat{X}(y)\right)^2 f(x|y)dx \geq \frac{1}{2\pi e}e^{2h(X|Y=y)}$$

Hence $$E[(X-\hat{X}(Y))^2] \geq \int_{y} f(y)\frac{1}{2\pi e}e^{2h(X|Y=y)}dy = \frac{1}{2\pi e}\int_{y} f(y)e^{2h(X|Y=y)}dy$$

By Jensen inequality, $$\int_{y} f(y)e^{2h(X|Y=y)}dy \geq e^{\int_{y}2h(X|Y=y)f(y)dy}$$

And so

$$E[(X-\hat{X}(Y))^2] \geq \frac{1}{2\pi e}e^{\int_{y}2h(X|Y=y)f(y)dy} = \frac{1}{2\pi e}e^{2h(X|Y)}$$

As required.

$\endgroup$
0
$\begingroup$

$$h(X|Y) = h(X-E(X|Y)|Y),$$ since shift (as opposed to scaling) does not change differential entropy. Now apply previous result (and Jensen's inequality) in the following fashion: $$ h(X|Y) = h(X-\hat X|Y) \leq E\left(\frac 12 \log (2\pi e E( (X - \hat{X})^2|Y)) \right) \leq \frac 12 \log (2\pi e E(X-\hat{X})^2)).$$

$\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.