Universal Communication Over Arbitrarily Varying Channels

Consider the problem of universally communicating over an arbitrarily varying channel, i.e., a channel comprised of an unknown, arbitrary sequence of memoryless channels. It is shown that there is a communication system using feedback and common randomness that asymptotically attains, with high probability, the capacity of the time-averaged channel, universally for every sequence of channels. This attainable rate is optimal under certain conditions. While no prior knowledge of the channel sequence is assumed, the capacity of the time-averaged channel meets or exceeds the traditional arbitrarily varying channel (AVC) capacity for every memoryless AVC defined over the same alphabets, and therefore, the system universally attains the random code AVC capacity, without knowledge of the AVC parameters. The presented system combines rateless coding with a universal prediction scheme for the input “prior” distribution, from which the codebook is randomly drawn. Because at each point in time, the future of the channel sequence is unknown to the communicators, the adaptation of the input behavior, by universally predicting the prior, plays a major role in the result.