Simulation of Stationary Sources: the AEP and Beyond
Matthew C. Davey
We consider a source emitting symbols at random from a
finite alphabet A={a_1, a_2,...,a_r}, where we can
define the source by a stationary probability measure on the space of
all sequences Omega:=A^N. We consider a class of probability
measures on the space of all words of length n, Omega_n, called
equipartition measures. These measures assign equal weight to
words belonging to Gamma_n for some subsets Gamma_n of Omega_n and
zero weight to those in Omega_n less Gamma_n. It is known that
for any stationary measure a sequence of sets {Gamma_n} can be
constructed such that, for each m, the sequence of equipartition
measures on Gamma_n induce probability measures on Omega_m which
converge to those induced by the given stationary measure.
We exploit this idea to produce numerical algorithms for simulating
simple stationary sources, namely Bernoulli sources and Markov chains.
The convergence properties of these simulations are examined, and an
efficient algorithm for their implementation is devised using
arithmetic coding. It is shown that good simulations of Markov chains
can be produced using fewer random bits per symbol than the Shannon
entropy of the chain.
Status: Thesis accepted by the University of Dublin for the degree of
Master in Science.
Compressed postscript file.