RECONSTRUCTION SEQUENCES AND EQUIPARTITION MEASURES - AN EXAMINATION OF THE ASYMPTOTIC EQUIPARTITION PROPERTY

We consider a stationary source emitting letters from a finite alphabe t 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 measur e 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 seque nce 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 efficien t simulation, we require Gamma(n) to be as large as possible, subject to the condition that the measure alpha(n) is approximated by the equi partition measure beta(n)[.\Gamma(n)], the probability measure on Omeg a(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 a bove 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 s upporting for . We prove also a characterization of ergodic measures w hich appears to be new.