Title :
Guesswork and entropy
Author :
Malone, David ; Sullivan, Wayne G.
Author_Institution :
Commun. Network Res. Inst., Dublin Inst. of Technol., Ireland
fDate :
3/1/2004 12:00:00 AM
Abstract :
We derive the moments of the guesswork , the number of attempts required to correctly guess the output of a random source, for a source determined by a Markov chain via a large deviations type estimate. These moments are related to the Perron-Frobenius eigenvalue of the matrix formed by element-wise powers of the Markov chain´s transition matrix.
Keywords :
Markov processes; eigenvalues and eigenfunctions; entropy; matrix algebra; Markov chain transition matrix; Perron-Frobenius eigenvalue; Renyi entropy; deviation estimation; element-wise power; guesswork; matrix formation; Communication networks; Eigenvalues and eigenfunctions; Entropy; Probability distribution; Stochastic processes;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2004.824921
