RÉnyi Entropy, Guesswork Moments, and Large Deviations

Abstract

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.