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

For the purposes of estimating quality-of-service parameters, it is enough to know the large deviation rate-function of an ATM traffic stream; modeling procedures can be bypassed if we can estimate the rate-function directly, exploiting the analogy between the rate-function and thermodynamic entropy. We show that this proposal is soundly based on statistical sampling theory. Experiments on the Fairisle ATM network at the University of Cambridge have established that it is feasible to collect the required data in real time.>