Asymptotic synchronization for finite-state sources

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

Authors: Nicholas F. Travers, James P. Crutchfield 

Publication date: 12 January 2012

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

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.

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

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

zbMATH Keywords

synchronizationstate estimationepsilon-machineentropy rate convergencestate uncertainty

Mathematics Subject Classification ID

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

Cites Work

• Elements of Information Theory
• Title not available (Why is that?)
• Regularities unseen, randomness observed: Levels of entropy convergence
• Prediction, retrodiction, and the amount of information stored in the present
• Hoeffding's inequality for uniformly ergodic Markov chains
• Exact synchronization for finite-state sources
• Information accessibility and cryptic processes
• Title not available (Why is that?)

Cited In (6)

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

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)