# Can samples be compressed?

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.

• Maybe I'm not quite getting your question, but suppose I take $k=3$ and let $g(x_1,x_2,x_3)$ be the majority function. Then $f_g(1;\theta) = \theta^3+\theta^2(1-\theta)$ and $f_g(0;\theta)=1-f_g(1;\theta)$. If I now evaluate $-\sum_{Z=0,1} f_g(Z;\theta) (\partial^2/\partial\theta^2) \log f_g(Z;\theta) = 36/(3 + 4\theta -4\theta^2)$, this can be either greater or smaller than $1/(\theta-\theta^2)$ depending on the value of $\theta$. – Yoav Kallus May 10 '16 at 19:24
• Yoav: OK, great answer for $k\geq 3$ and for some values of $\theta$- thanks!. I'm mainly interested in $k=2$ in fact... is there a counterexample here? – Daniel Moskovich May 10 '16 at 19:35
• Let's take Or_2 instead of Majority_3: $f_g(1;\theta) = \theta^2 + 2\theta(1-\theta)$. I get $\mathcal{I}_g(\theta) = 4/(2\theta-\theta^2)$, which again can be greater or smaller than $1/(\theta-\theta^2)$. – Yoav Kallus May 10 '16 at 19:41
• The intuition is that if $\theta$ is near $0$, $Or(x_1,x_2)$ has double the chance of being informative than just $x_1$. On the opposite end of the spectrum, if $\theta$ is near $1$, you have to be very lucky for $Or(x_1,x_2)$ to be informative. – Yoav Kallus May 10 '16 at 19:45
• Fantastic- thanks! This answers my question. So my expectation was too naïve. – Daniel Moskovich May 10 '16 at 19:50

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.