Exact synchronization for finite-state sources

DOI10.1007/S10955-011-0342-4MaRDI QIDQ658481zbMATH OpenOpenAlexFDO

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/1008.4182

zbMATH Keywords

\(\epsilon\)-machinecausal statesentropy rate convergencestate estimationstate uncertaintysynchronization

Mathematics Subject Classification ID

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

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.

Review text

The synchronization process for a class of finite-state hidden Markov models, the \(\epsilon\)-machines, is analyzed. An \(\epsilon\)-machine is exactly synchronizable if the observer synchronizes to almost every sequence generated by the machine in finite time. One proves that an observer synchronizes exactly to the internal state of any \(\epsilon \)-machine exponentially fast. The synchronization rate can be computed analytically. The observers average uncertainty in the machine state as well as the average uncertainty in predictions of the future symbols decay exponentially fast. At the end of the article, necessary and sufficient conditions for exactness of an \(\epsilon\)-machine together with a test-algorithm are provided.

Recommendations

• Asymptotic synchronization for finite-state sources
• Quantifying communication in synchronized languages
• Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation
• On the probability of being synchronizable
• SYNCHRONIZING TO PERIODICITY: THE TRANSIENT INFORMATION AND SYNCHRONIZATION TIME OF PERIODIC SEQUENCES

Cites work

• A Mathematical Theory of Communication
• Asymptotic synchronization for finite-state sources
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• From finite to infinite range order via annealing: the causal architecture of deformation faulting in annealed close-packed crystals
• scientific article; zbMATH DE number 3719745 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Regularities unseen, randomness observed: Levels of entropy convergence
• Sofic shifts with synchronizing presentations
• Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation

Cited in

(17)

• Dealing with final state sensitivity for synchronous communication
• Computational complexity of problems for deterministic presentations of sofic shifts
• Careful synchronization of partial deterministic finite automata
• Strong and weak optimizations in classical and quantum models of stochastic processes
• The ambiguity of simplicity in quantum and classical simulation
• Subset synchronization and careful synchronization of binary finite automata
• SYNCHRONIZING TO THE ENVIRONMENT: INFORMATION-THEORETIC CONSTRAINTS ON AGENT LEARNING
• Spectral simplicity of apparent complexity. I: The nondiagonalizable metadynamics of prediction
• The fundamental thermodynamic bounds on finite models
• Complexity of a problem concerning reset words for Eulerian binary automata
• Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation
• SYNCHRONIZING TO PERIODICITY: THE TRANSIENT INFORMATION AND SYNCHRONIZATION TIME OF PERIODIC SEQUENCES
• Asymptotic synchronization for finite-state sources
• An improved algorithm for finding the shortest synchronizing words
• Synchronizing strongly connected partial DFAs
• Synchronization of strongly connected partial DFAs and prefix codes
• Exponential bounds for convergence of entropy rate approximations in hidden Markov models satisfying a path-mergeability condition

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

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