Premium
Universal finitary codes with exponential tails
Author(s) -
Harvey Nate,
Holroyd Alexander E.,
Peres Yuval,
Romik Dan
Publication year - 2007
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/pdl018
Subject(s) - finitary , mathematics , homomorphism , bernoulli process , alphabet , discrete mathematics , bernoulli's principle , markov chain , entropy (arrow of time) , kullback–leibler divergence , exponential function , combinatorics , exponential family , statistics , mathematical analysis , linguistics , philosophy , physics , quantum mechanics , engineering , aerospace engineering
In 1977, Keane and Smorodinsky showed that there exists a finitary homomorphism from any finite‐alphabet Bernoulli process to any other finite‐alphabet Bernoulli process of strictly lower entropy. In 1996, Serafin proved the existence of a finitary homomorphism with finite expected coding length. In this paper, we construct such a homomorphism in which the coding length has exponential tails. Our construction is source‐universal, in the sense that it does not use any information on the source distribution other than the alphabet size and a bound on the entropy gap between the source and target distributions. We also indicate how our methods can be extended to prove a source‐specific version of the result for Markov chains.