For a large class of stationary probability measures on A/sup N/, where A is a finite alphabet, we compute the specific Renyi entropy of order /spl alpha/ and the specific guesswork moments of order /spl beta/ > -1. We show that the specific guesswork moment of order /spl beta/ equals the specific Renyi entropy of order /spl alpha/ = 1 / (1 + /spl beta/) multiplied by /spl beta/. The method is based on energy-entropy estimates suggested by statistical physics. The technique also yields a simple proof of the large deviation principle for the empirical measure on the space of an irreducible sofic shift with reference probability measure /spl nu/, which is stationary and satisfies a rate condition on the probability of allowed words.

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.