Word-Valued Sources: An Ergodic Theorem, an AEP, and the Conservation of Entropy
Roy Timo, Kim L. Blackmore, Leif Hanlen · IEEE Transactions on Information Theory · 2010
A word-valued source Y = Y1,Y2,...is discrete random process that is formed by sequentially encoding the symbols of a random process X = X1,X2,...with codewords from a codebookC. These processes appear frequently in information theory (in particular, in the analysis of source-coding algorithms), so it is of interest to give conditions onXandCfor whichYwill satisfy an ergodic theorem and possess an asymptotic equipartition property (AEP). In this paper, we prove the following: 1) ifXis asymptotically mean stationary (AMS), thenYwill satisfy a pointwise ergodic theorem and possess an AEP; and 2) if the codebookCis prefix-free, then the entropy rate ofYis equal to the entropy rate ofXnormalized by the average codeword length.