Word-Valued Sources: an Ergodic Theorem, an AEP and the Conservation of Entropy

Abstract

A word-valued source $\mathbf{Y}=Y_1,Y_2,...$ is discrete random process that is formed by sequentially encoding the symbols of a random process $\mathbf{X}=X_1,X_2,...$ with codewords from a codebook $\mathcal{C}$. These processes appear frequently in information theory (in particular, in the analysis of source-coding algorithms), so it is of interest to give conditions on $\mathbf{X}$ and $\mathcal{C}$ for which $\mathbf{Y}$ will satisfy an ergodic theorem and possess an Asymptotic Equipartition Property (AEP). In this correspondence, we prove the following: (1) if $\mathbf{X}$ is asymptotically mean stationary, then $\mathbf{Y}$ will satisfy a pointwise ergodic theorem and possess an AEP; and, (2) if the codebook $\mathcal{C}$ is prefix-free, then the entropy rate of $\mathbf{Y}$ is equal to the entropy rate of $\mathbf{X}$ normalized by the average codeword length.

21 pages