Zero-rate feedback can achieve the empirical capacity

Abstract

The utility of limited feedback for coding over an individual sequence of DMCs is investigated. This study complements recent results showing how limited or noisy feedback can boost the reliability of communication. A strategy with fixed input distribution $P$ is given that asymptotically achieves rates arbitrarily close to the mutual information induced by $P$ and the state-averaged channel. When the capacity achieving input distribution is the same over all channel states, this achieves rates at least as large as the capacity of the state averaged channel, sometimes called the empirical capacity.

Revised version of paper originally submitted to IEEE Transactions on Information Theory, Nov. 2007. This version contains further revisions and clarifications

References in corpus (2)

• Balancing forward and feedback error correction for erasure channels with unreliable feedback
• Why block length and delay behave differently if feedback is present

Cited by in corpus (13)

• Communication over Individual Channels
• Communication over Individual Channels -- a general framework
• Universal communication part I: modulo additive channels
• Learning an Adversary's Actions for Secret Communication
• Feedback Communication over Individual Channels
• Scheduling of Multicast and Unicast Services under Limited Feedback by using Rateless Codes
• Universal Communication over Arbitrarily Varying Channels
• An Achievable Rate for the MIMO Individual Channel
• Universal communication part II: channels with memory
• Searching with Measurement Dependent Noise
• Rateless codes for AVC models
• Power Adaptive Feedback Communication over an Additive Individual Noise Sequence Channel
• Achievable Error Exponents in the Gaussian Channel with Rate-Limited Feedback