Suppose Alice has a bit string of length $n$ where $n/2$ bits are chosen uniformly at random to be 1's; and the rest are 0's. Alice sends a message to Bob.

If Bob needs to reconstruct the bit string, then $\Omega(n)$ communication is needed.

However, suppose Bob only needs to reconstruct at least $0.99n$ bits correctly (without knowing which bits are correct). Would this lower bound still hold?


1 Answer 1


This is a basic exercise and is not research level. Hints:

How many possible answers from Bob would be accepted as valid? How many possible strings might Alice have chosen? From this, what can you conclude about the number of bits of entropy that must be communicated?


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.