Exact Synchronization for Finite-State Sources

Abstract

We analyze how an observer synchronizes to the internal state of a finite-state information source, using the epsilon-machine causal representation. Here, we treat the case of exact synchronization, when it is possible for the observer to synchronize completely after a finite number of observations. The more difficult case of strictly asymptotic synchronization is treated in a sequel. In both cases, we find that an observer, on average, will synchronize to the source state exponentially fast and that, as a result, the average accuracy in an observer's predictions of the source output approaches its optimal level exponentially fast as well. Additionally, we show here how to analytically calculate the synchronization rate for exact epsilon-machines and provide an efficient polynomial-time algorithm to test epsilon-machines for exactness.

9 pages, 6 figures; now includes analytical calculation of the synchronization rate; updates and corrections added

References in corpus (1)

• Asymptotic Synchronization for Finite-State Sources

Cited by in corpus (15)

• Bayesian Structural Inference for Hidden Processes
• Many Roads to Synchrony: Natural Time Scales and Their Algorithms
• Synchronization and Control in Intrinsic and Designed Computation: An Information-Theoretic Analysis of Competing Models of Stochastic Computation
• Asymptotic Synchronization for Finite-State Sources
• Strong and Weak Optimizations in Classical and Quantum Models of Stochastic Processes
• Spectral Simplicity of Apparent Complexity, Part I: The Nondiagonalizable Metadynamics of Prediction
• The Elusive Present: Hidden Past and Future Dependency and Why We Build Models
• Quantifying Self-Organization with Optimal Wavelets
• Thermodynamically-Efficient Local Computation and the Inefficiency of Quantum Memory Compression
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications
• Testing for Synchronization
• The fundamental thermodynamic bounds on finite models
• On the Synchronization Rate for e-machines
• Synchronization of strongly connected partial DFAs and prefix codes
• Bounds for Algorithmic Mutual Information and a Unifilar Order Estimator