# Standard information-theoretic lower bound?

There should be a simple argument, but I'm struggling to see it.

Suppose Alice has a string $$x \in \{0, 1\}^n$$ and sends a message $$s = s(x)$$ to Bob. And suppose that given $$s$$, Bob can reconstruct each bit of $$x$$ with probability $$2/3$$ (say). (Note that this is weaker than the claim "with probability $$2/3$$, Bob can recover the entire string $$x$$." A clean proof of this case would be appreciated too.)

Then we should be able to conclude $$|s| = \Omega(n)$$, and this seems obvious, but can someone formalize this for me?

• Bob, given $s(x)$, can recover each bit of $x$ with probability $2/3$. I want to conclude that $|s(x)| = \Omega(|x|)$. – Mike Nov 14 '19 at 18:38
• I want to prove that Alice must send at least $\Omega(|x|)$ bits in order for Bob to recover each bit of $x$ with probability $2/3$. If Alice sends nothing, then I don't see how Bob can recover anything... – Mike Nov 14 '19 at 18:44
• Try the following: the mutual information between $x$ and $s$ is at least $nh(2/3) = \Omega(n)$, and since $I(x;s) \leq H(s) \leq |s|$, we must have $|s| = \Omega(n)$. – Yuval Filmus Nov 14 '19 at 20:01
• Your premise is expressed rather informally. Can you make it more precise? – Yuval Filmus Nov 14 '19 at 20:02
• The closest thing I can find is the one-way gap-Hamming problem. I want to show that any one-way communication protocol that allows Bob to recover each bit with probability $2/3$ requires $\Omega(n)$ bits. Unfortunately, I don't see how this fits in the standard notions of communication complexity. Again, even a proof of the weaker claim would be appreciated, so I would at least know what to search. – Mike Nov 15 '19 at 18:10

I understand your question this way:

Assume Alice has some $$X\in\{0,1\}^n$$. Alice encodes (compresses) $$X$$ into $$s = s(X)$$, where $$|s|\le n$$. Bob decodes $$s$$ to obtain $$X'=dec(s)$$. Show that unless $$|s|=\Omega(n)$$ it cannot hold that Hamming$$(X,X') < n/3$$.

If this is what you meant, then this follows from the fact that most strings cannot be compressed. Assume that for any $$X$$, $$|s(X)|=o(n)$$. Note that there are at most $$2^{|s|}\ll 2^n$$ such strings. More accurately, $$2^{|s|} / 2^n \to_{n\to\infty} 0$$.

Then, for each possible $$s$$ construct $$dec(s)$$ and define $$Y_s$$ to be a Hamming ball of radius $$n/3$$ centered at $$dec(s)$$. Verify that $$|Y_s| = \sum_{d=0}^{n/3}\binom{n}{d} < 2^{n\cdot h(1/3)}$$, with $$h(\cdot)$$ the binary entropy function. Thus $$\left|\bigcup_s |Y_s|\right| \le 2^{o(n)}2^{0.92n} \ll 2^n$$. This means that there exists a string $$X$$ not covered by the $$Y_s$$ for any $$s$$, i.e., not within a Hamming-distance of $$n/3$$ from any of the decoding of any $$s$$.

If this is not what you meant, you will have to formulate your statement in a proper way. For instance, you say "with probability 2/3", but there is no probability space defined in your statement, etc.