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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – user1936752
    Jan 27, 2021 at 11:58
  • $\begingroup$ The randomness shouldn't make any difference, since you can always fix it to the best possible value. $\endgroup$
    – Yuval Filmus
    Jan 27, 2021 at 13:02

Your Answer

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

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