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?

  • $\begingroup$ Bob, given $s(x)$, can recover each bit of $x$ with probability $2/3$. I want to conclude that $|s(x)| = \Omega(|x|)$. $\endgroup$
    – Mike
    Nov 14, 2019 at 18:38
  • $\begingroup$ 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... $\endgroup$
    – Mike
    Nov 14, 2019 at 18:44
  • $\begingroup$ 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)$. $\endgroup$ Nov 14, 2019 at 20:01
  • 1
    $\begingroup$ Your premise is expressed rather informally. Can you make it more precise? $\endgroup$ Nov 14, 2019 at 20:02
  • $\begingroup$ 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. $\endgroup$
    – Mike
    Nov 15, 2019 at 18:10

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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