Universal communication over arbitrarily varying channels

We consider the problem of universally communicating over an unknown and arbitrarily varying channel, using feedback. In a previous paper we focused on the problem of determining the communication prior using a universal prediction scheme. Based on this result we present a full 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 rate is shown to be the maximum rate as a function of the channel sequence, which is asymptotically achievable, without relying on the order of the channel sequence. While no prior knowledge of the channel sequence is assumed, the rate achieved 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.