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

  • 2
    $\begingroup$ 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. $\endgroup$
    – fedja
    Aug 28, 2020 at 21:59
  • $\begingroup$ It seems a better goal to bound from below the conditional variance of $X$ given $\hat{X}$. $\endgroup$ Aug 29, 2020 at 21:04
  • $\begingroup$ Is Alice's alphabet restricted to $\{0,1\}$ or can they send any message with Shannon entropy 1? (Not sure if this matters yet) $\endgroup$ Mar 18, 2021 at 15:30

1 Answer 1


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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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