Can samples be compressed?

Question

The Fisher information of a random variable $Y$ about a parameter $\theta$ upon which the probability of $Y$ depends is:

$\mathcal{I}_Y(\theta)= -E\left[\left.\strut \frac{\partial^2}{\partial \theta^2} \,\log f\left(Y;\theta\right)\right | \theta \right]\enspace ,$

where $f\left(Y;\theta\right)$ denotes the probability density of $Y$ conditional on the value of $\theta$. Roughly speaking, Fisher information measures the extent to which $Y$ can be used to estimate $\theta$, the precise statement given by the Cramér-Rao Theorem.

In the case of a $\{0,1\}$ -valued Bernoulli random variable $X$ with mean $\theta\in(0,1)$, a sample of $X$ (considered itself as a random variable) has Fisher information $(\theta(1-\theta))^{-1}$ about $\theta$, as computed for example on Wikipedia. My question is whether this is known to be optimal for a single bit.

More precisely:

Question: Let $x_1,x_2,\ldots,x_k$ be iid $\{0,1\}$-valued Bernoulli random variables with mean $\theta$ (I'm happy taking $k=2$), and let $g$ be a function mapping $(x_1,x_2,\ldots,x_k)$ to another $\{0,1\}$-valued Bernoulli random variable $Y$. Is it guaranteed that $\mathcal{I}_{g(x_1,x_2,\ldots,x_k)}(\theta)\leq (\theta(1-\theta))^{-1}= \mathcal{I}_{x_1}(\theta)$ ?

My naïve intuition is that this is true, because no single bit ought to be able to carry more information about $\theta$ than a sample. In this sense, if you want to communicate a parameter of a random variable you can't do better than sending samples. If there were any way to compress the information in Bernoulli samples, everyone would be doing it! But I don't know where such problems are discussed and I can't see a proof.

Answer 1

No, the inequality is not guaranteed. One example with $k=2$ is for $g(x_1,x_2) = OR(x_1,x_2)$. Then $f_g(1;\theta) = 1-(1-\theta)^2$, and $\mathcal{I}_g(\theta) = 4/(2\theta-\theta^2)$. We have $\mathcal{I}_g(\theta)>\mathcal{I}_{x_1}(\theta)$ when $\theta<\tfrac23$ and the reverse inequality when $\theta>\tfrac23$.

The reason this should not be too surprising is that you are asking whether, in order to estimate the bias of an unfair coin, you should prefer to see the results of $N$ tosses or the results of ORing $N$ pairs of tosses. If $\theta\ll 1$, then each result of the OR has roughly twice the chance of being informative ($\neq 0$) than a single toss does. If $1-\theta\ll1$, then you have to be extraordinary lucky ($(1-\theta)^2$) for the OR to be informative ($\neq 1$), while only ordinarily lucky for a single toss to be informative.