Reconstruction sequences and equipartition measures: an examination of the asymptotic equipartition property

We consider a stationary source emitting letters from a finite alphabet A. The source is described by a stationary probability measure α on the space Ω:=A^IN of sequences of letters. Denote by Ω_n the set of words of length n and by α_n the probability measure induced on Ω_n by α. We consider sequences {Γ_n⊂Ω_n: n∈IN} having special properties. Call {Γ_n⊂Ω_n: n∈IN} a supporting sequence for α if lim_n α _n[Γ_n]=1. It is well known that the exponential growth rate of a supporting sequence is bounded below by h _Sh(α), the Shannon entropy of the source α. For efficient simulation, we require Γ_n to be as large as possible, subject to the condition that the measure α_n is approximated by the equipartition measure β_n[·|Γ_n], the probability measure on Ω_n which gives equal weight to the words in Γ_n and zero weight to words outside it. We say that a sequence {Γ_n⊂Ω_n: n∈IN} is a reconstruction sequence for α if each Γ_n is invariant under cyclic permutations and lim_n β_n [·|Γ_n]=α_m for each m∈IN. We prove that the exponential growth rate of a reconstruction sequence is bounded above by h_Sh(α). We use a large-deviation property of the cyclic empirical measure to give a constructive proof of an existence theorem: if α is a stationary source, then there exists a reconstruction sequence for α having maximal exponential growth rate; if α is ergodic, then the reconstruction sequence may be chosen so as to be supporting for α. We prove also a characterization of ergodic measures which appears to be new