IEEE International Symposium on Information Theory (ISIT)
Dispersion of the discrete arbitrarily-varying channel with limited shared randomness
Oliver Kosut, Jörg Kliewer
Abstract
The second-order behavior of the discrete memoryless arbitrarily-varying channel is considered in the fixed error regime when the encoder and decoder share randomness that is independent from the adversarial choice of state. The dispersion (coefficient of the second-order term) is exactly characterized for most channels of interest when infinite shared randomness is allowed, and it is shown that precisely the same dispersion is achievable with only O (log n) bits of shared randomness. We also show that the dispersion is identical to that of the non-adversarial channel induced by the adversary simply choosing an i.i.d. state sequence according to the correct distribution. Further, we present some remarks on the connection to the compound channel, as well as on cost constraints for input and state sequences.