# How much reduction in expected variance can we get from a single bit?

Consider the following protocol:

Alice has a number $$X$$, chosen according to a known distribution $$\mathcal D$$ (e.g., $$X\sim U[0,1]$$).

She can send a bit to Bob, giving him more information about $$X$$ (e.g., she can send $$Y=\mbox{Bernoulli}(X)$$. In turn, Bob estimates $$X$$ (e.g., as $$\widehat X = Y$$).

I'm interested in lower bounding the expected (over the choice of $$X$$) variance of any such protocol.

In the above example, we have $$\mbox{Var}[\widehat X | X] = X(1-X)$$ and thus $$\mathbb E[\mbox{Var}[\widehat X]] = \mathbb E[\mbox{Var}[\widehat x | X]] = \int_0^1x(1-x)dx = 1/6.$$

For this specific distribution (uniform), this protocol seems to yield the lowest possible expected variance for any unbiased estimation.

Can we use information-theoretic arguments to lower bound the variance for different distributions $$\mathcal D$$ for any protocol?

I looked into applying conditional differential entropy, but this seems to apply to a specific choice of protocol (how to choose which bit to send).

• Formally, as posed, Bob can just estimate $\widehat X=EX$ without even looking at what Alice sent him (and she can just send him a bit independent of $X$ to avoid tempting him to do anything), thus achieving variance $0$. Apparently you wanted to ask something else, but I'll leave it to you to figure out what exactly it was. Aug 28, 2020 at 21:59
• It seems a better goal to bound from below the conditional variance of $X$ given $\hat{X}$. Aug 29, 2020 at 21:04
• Is Alice's alphabet restricted to $\{0,1\}$ or can they send any message with Shannon entropy 1? (Not sure if this matters yet) Mar 18, 2021 at 15:30

This is a specific instance of one-shot lossy source coding which is still open in general. The best work I know of is in this preprint by Elkayam and Feder where they distill it down to the open problem of identifying a convex minimizer $$\tilde{D}(z,Q_Y)$$.