Universal finitary codes with exponential tails

DOI10.1112/PLMS/PDL018MaRDI QIDQ3434058zbMATH OpenOpenAlexFDO

Authors Nate Harvey, A. E. Holroyd, Yuval Peres, Dan Romik

Publication date 23 April 2007

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0502484

zbMATH Keywords

Bernoulli processfinitary codesfinitary homomorphism

Mathematics Subject Classification ID

Entropy and other invariants (28D20) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Symbolic dynamics (37B10) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Theory of error-correcting codes and error-detecting codes (94B99)

Abstract: 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.

Recommendations

• The finitary coding of two Bernoulli schemes with unequal entropies has finite expectation
• Explicit codes for some infinite entropy Bernoulli shifts
• A class of finitary codes
• Finitary Codes, a short survey
• An invariant of finitary codes with finite expected square root coding length

Cites work

• A class of finitary codes
• Bernoulli schemes of the same entropy are finitarily isomorphic
• Code length between Markov processes
• Explicit codes for some infinite entropy Bernoulli shifts
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 3614066 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• Interval algorithm for random number generation
• Iterating von Neumann's procedure for extracting random bits
• Sharp entropy bounds for discrete statistical simulation
• The Efficient Construction of an Unbiased Random Sequence
• The finitary coding of two Bernoulli schemes with unequal entropies has finite expectation

Cited in

(13)

• Explicit codes for some infinite entropy Bernoulli shifts
• A class of finitary codes
• Code length between Markov processes
• Finitary coding for the sub-critical Ising model with finite expected coding volume
• Finitary isomorphisms of Poisson point processes
• A monotone Sinai theorem
• An invariant of finitary codes with finite expected square root coding length
• Markov chains with exponential return times are finitary
• Finitary Codes, a short survey
• Sinai factors of nonsingular systems: Bernoulli shifts and Anosov flows
• Finitary isomorphisms of Brownian motions
• Finitely dependent processes are finitary
• Finitary codings for spatial mixing Markov random fields

This page was built for publication: Universal finitary codes with exponential tails

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434058)