Shared randomness does not increase capacity of a noisy channel - Why? 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!
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.