Universal finitary codes with exponential tails
| dc.creator | Harvey, Nate | |
| dc.creator | Holroyd, Alexander E. | |
| dc.creator | Peres, Yuval | |
| dc.creator | Romik, Dan | |
| dc.date | 2005-02-23 | |
| dc.date.accessioned | 2026-07-07T05:17:24Z | |
| dc.date.available | 2026-07-07T05:17:24Z | |
| dc.description | 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. | |
| dc.description | 33 pages | |
| dc.identifier | https://arxiv.org/abs/math/0502484 | |
| dc.identifier | http://arxiv.org/abs/math/0502484 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/74291 | |
| dc.subject | Probability | |
| dc.subject | 37A50; 28D20 | |
| dc.title | Universal finitary codes with exponential tails | |
| dc.type | text |