Adversarial Source Coding and Continuity of the Rate-Distortion Function
Harikrishna R Palaiyanur, Cheng Chang and Anant Sahai
We consider the problem of finding the rate-distortion function of an arbitrarily varying source (AVS) with a finite number of sources with known distributions. Berger's paper "The Source Coding Game," IEEE Trans. Inform. Theory, 1971, considers this problem under the condition that the adversary is allowed only causal access to the source realizations. We consider the case when the adversary has access to the source realizations non-causally. Using the type covering lemma, this new rate distortion function can be determined to be the maximum of the IID rate distortion function over a set of source distributions attainable by the adversary. We find a bound on the number of distributions that need to be sampled to determine the rate distortion function of an AVS to within a certain accuracy. This bound is developed through an explicit bound on the continuity of the IID rate-distortion function. We plan to investigate the usefulness of this bound in the problem of estimating the rate-distortion function for an unknown source.
- H. Palaiyanur, C. Chang, and A. Sahai, "The Source Coding Game with a Cheating Switcher," Proc. International Symposium on Information Theory, Nice, France, June 2007.