The Source Coding Game With a Cheating Switcher

摘要

The problem of finding the rate-distortion function of an arbitrarily varying source (AVS) composed of a finite number of memoryless subsources is revisited. Berger''s 1971 paper “The Source Coding Game” solves this problem when the adversary is allowed only strictly causal access to the subsource realizations. The case when the adversary has access to the subsource realizations non-causally is considered. This new rate-distortion function is determined to be the maximum of the rate-distortion function over a set of independent and identically distributed (IID) random variables that can be simulated by the adversary. The results are extended to allow for partial or noisy observations of subsource realizations. The model is further explored by attempting to find the rate-distortion function when the ‘adversary’ is actually helpful. Finally, a bound is developed on the uniform continuity of the IID rate-distortion function for finite-alphabet sources. The bound is used to give a sufficient number of distributions that need to be sampled to compute the rate-distortion function of an AVS to within a desired accuracy. The bound is also used to give a rate of convergence for the estimate of the rate-distortion function for an unknown IID source.