The source coding game

The encoding of a source whose probability distribution varies arbitrarily from letter to letter is considered. The problem is formulated as a two-person statistical game. The exponential rate of growth with block length of the minimum number of codewords needed to achieve a specified fidelity with respect to a single-letter distortion measure is determined. The rate distortion function of a source whose statistics are entirely unknown is obtained as a special case. The dependence of the results on the rules under which the game is played also is studied. The analysis is based on a refinement of the usual random coding argument for sources which sheds new light on the significance of the term that decays at a doubly exponential rate with block length.