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

2009/04/24 by Roy Timo, Timo, Roy, Kim Blackmore +3
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.0904.3778

21 pages

arxiv created 2009/04/24 · arxiv updated 2009/12/01

Abstract

A word-valued source Y = Y₁,Y₂,... is discrete random process that is formed by sequentially encoding the symbols of a random process X = X₁,X₂,... with codewords from a codebook \mathscrC. 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 X and \mathscrC for which Y will satisfy an ergodic theorem and possess an Asymptotic Equipartition Property (AEP). In this correspondence, we prove the following: (1) if X is asymptotically mean stationary, then Y will satisfy a pointwise ergodic theorem and possess an AEP; and, (2) if the codebook \mathscrC is prefix-free, then the entropy rate of Y is equal to the entropy rate of X normalized by the average codeword length.

Related

• On typical encodings of multivariate ergodic sources
• Non-asymptotic Equipartition Properties for Independent and Identically Distributed Sources
• Asymptotic equipartition property for a Markov source having ambiguous alphabet
• Computing Entropy Rate Of Symbol Sources & A Distribution-free Limit Theorem
• The ergodic decomposition of asymptotically mean stationary random sources