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 alpha on the space Omega := A(IN) of Sequences of letters. Denote by Omega(n) the set of words of length n and by alpha(n) the probability measure induced on Omega(n) by alpha. We consider sequences {Gamma(n) subset of Omega(n): n is an element of IN} having special properties. Call {Gamma(n) subset of Omega(n): n is an element of IN} a supporting sequence for alpha if lim(n) alpha(n)[Gamma(n)] = 1. It is well known that the exponential growth rate of a supporting sequence is bounded below by h(Sh)(alpha), the Shannon entropy of the source alpha. For efficient simulation, we require Gamma(n) to be as large as possible, subject to the condition that the measure alpha(n) is approximated by the equipartition measure beta(n)[.\Gamma(n)], the probability measure on Omega(n) which gives equal weight to the words in Gamma(n) and zero weight to words outside it. We say that a sequence {Gamma(n) subset of Omega(n): n is an element of IN} is a reconstruction sequence for alpha if each Gamma(n) is invariant under cyclic permutations and lim(n) beta(n)[.\Gamma(n)] = alpha(m) for each m is an element of IN. We prove that the exponential growth rate of a reconstruction sequence is bounded above by h(Sh)(alpha). We use a large-deviation property of the cyclic empirical measure to give a constructive proof of an existence theorem: if alpha is a stationary source, then there exists a reconstruction sequence for alpha having maximal exponential growth rate; if alpha 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.
reconstruction asymptotic equipartition property stationary empirical measure ergodic kolmogorov large deviations