|
|||||
|
|
Universal finitary codes with exponential tails |
|
| Authors: | Harvey Nate; Holroyd Alexander E; Peres Yuval; Romik Dan |
| Institution: | 1 Department of Mathematics University of California at Berkeley Berkeley, CA 94720 USA 2 Department of Mathematics University of British Columbia Vancouver, BC V6T 1Z2 Canada holroyd{at}math.ubc.ca 3 Departments of Statistics and Mathematics University of California at Berkeley CA 94720, Berkeley USA peres{at}stat.berkeley.edu 4 The Mathematical Sciences Research Institute 17 Gauss Way Berkeley, CA 94720-5070 USA romik{at}msri.org |
| Abstract: | In 1977, Keane and Smorodinsky showed that there exists a finitaryhomomorphism from any finite-alphabet Bernoulli process to anyother finite-alphabet Bernoulli process of strictly lower entropy.In 1996, Serafin proved the existence of a finitary homomorphismwith finite expected coding length. In this paper, we constructsuch a homomorphism in which the coding length has exponentialtails. Our construction is source-universal, in the sense thatit does not use any information on the source distribution otherthan the alphabet size and a bound on the entropy gap betweenthe source and target distributions. We also indicate how ourmethods can be extended to prove a source-specific version ofthe result for Markov chains. |
| Keywords: | |
| 本文献已被 Oxford 等数据库收录！ | |