2
$\begingroup$

Why is it the case that when Alice and Bob use a noisy channel for communication, the capacity of the channel does not increase even if they are allowed to share pre-distributed randomness?

This is mentioned in some notes (see paragraph before Section 4 of https://cds.cern.ch/record/613098/files/0304102.pdf) but I have not seen a proof or an intuitive argument for it yet. Any reference to where this is covered would also be appreciated!

$\endgroup$
2
$\begingroup$

Each value of the shared randomness corresponds to a communication protocol. So overall, we have a mixture of communication protocols, whose expected quality is good. There must therefore be one of these communication protocols – a setting of the shared randomness – which is as good.

As an example, we know that a random code achieves capacity. This means that some particular code achieves capacity. It might be hard to find that code, but we know that it exists.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer. Wouldn't one need to prove the converse statement (communication at rate greater than capacity results in exponential error) in the presence of shared randomness? But it seems like Cover and Thomas's proof using Fano's inequality goes through without any modification $\endgroup$ Jan 27 at 11:58
  • $\begingroup$ The randomness shouldn't make any difference, since you can always fix it to the best possible value. $\endgroup$ Jan 27 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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