Asymptotic synchronization for finite-state sources

DOI10.1007/S10955-011-0349-XzbMATH Open1238.68059OpenAlexW3102138220MaRDI QIDQ658485FDOQ658485

Authors Nicholas F. Travers, James P. Crutchfield

Publication date 12 January 2012

Published in Journal of Statistical Physics (Search for Journal in Brave)

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

zbMATH Keywords

synchronizationstate estimationepsilon-machineentropy rate convergencestate uncertainty

Mathematics Subject Classification ID

Markov processes: estimation; hidden Markov models (62M05)

Abstract: We extend a recent synchronization analysis of exact finite-state sources to nonexact sources for which synchronization occurs only asymptotically. Although the proof methods are quite different, the primary results remain the same. We find that an observer's average uncertainty in the source state vanishes exponentially fast and, as a consequence, an observer's average uncertainty in predicting future output converges exponentially fast to the source entropy rate.

Recommendations

• Exact synchronization for finite-state sources
• SYNCHRONIZATION THROUGH FILTERING
• Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation
• Optimal Sequential Frame Synchronization
• Regularities unseen, randomness observed: Levels of entropy convergence

Cites work

• scientific article; zbMATH DE number 3590188 (Why is no real title available?)
• scientific article; zbMATH DE number 3205804 (Why is no real title available?)
• Elements of Information Theory
• Exact synchronization for finite-state sources
• Hoeffding's inequality for uniformly ergodic Markov chains
• Information accessibility and cryptic processes
• Prediction, retrodiction, and the amount of information stored in the present
• Regularities unseen, randomness observed: Levels of entropy convergence

Cited in

(6)

• Exponential bounds for convergence of entropy rate approximations in hidden Markov models satisfying a path-mergeability condition
• Spectral simplicity of apparent complexity. I: The nondiagonalizable metadynamics of prediction
• Careful synchronization of partial deterministic finite automata
• Topology, convergence, and reconstruction of predictive states
• Exact synchronization for finite-state sources
• The fundamental thermodynamic bounds on finite models

This page was built for publication: Asymptotic synchronization for finite-state sources

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