Abstract
We analyze how an observer synchronizes to the internal state of a finite-state information source, using the ϵ-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 ϵ-machines and provide an efficient polynomial-time algorithm to test ϵ-machines for exactness.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Forney, G.D., Jr.: The Viterbi algorithm: a personal history. CoRR. abs/cs/0504020 (2005)
Viterbi, A.J.: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inf. Theory 13(2), 260–269 (1967)
Jonoska, N.: Sofic shifts with synchronizing presentations. Theor. Comput. Sci. 158(1–2), 81–115 (1996)
Sandberg, S.: Homing and synchronizing sequences. In: Broy, M., et al. (eds.) Lect. Notes Comp. Sci., vol. 3472, pp. 5–33. Springer, Berlin (2005)
Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)
Crutchfield, J.P., Young, K.: Inferring statistical complexity. Phys. Rev. Lett. 63, 105–108 (1989)
Crutchfield, J.P., Ellison, C.J., Mahoney, J.R., James, R.G.: Synchronization and control in intrinsic and designed computation: an information-theoretic analysis of competing models of stochastic computation. Chaos 20(3), 037105 (2010)
Crutchfield, J.P., Feldman, D.P.: Statistical complexity of simple one-dimensional spin systems. Phys. Rev. E 55(2), 1239R–1243R (1997)
Feldman, D.P., Crutchfield, J.P.: Structural information in two-dimensional patterns: entropy convergence and excess entropy. Phys. Rev. E 67(5), 051103 (2003)
Varn, D.P., Canright, G.S., Crutchfield, J.P.: Discovering planar disorder in close-packed structures from x-ray diffraction: beyond the fault model. Phys. Rev. B 66(17), 174110 (2002)
Varn, D.P., Crutchfield, J.P.: From finite to infinite range order via annealing: the causal architecture of deformation faulting in annealed close-packed crystals. Phys. Lett. A 234(4), 299–307 (2004)
Li, C.-B., Yang, H., Komatsuzaki, T.: Multiscale complex network of protein conformational fluctuations in single-molecule time series. Proc. Natl. Acad. Sci. USA 105, 536–541 (2008)
Travers, N., Crutchfield, J.P.: Asymptotic synchronization for finite-state sources. J. Stat. Phys. doi:10.1007/s10955-011-0349-x. arXiv.org:1011.1581 [nlin.CD]
Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley–Interscience, New York (2003). Extensions and notation used here are from [19]
Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 379–423, 623–656 (1948)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Automata Theory, Languages, and Computation. Addison–Wesley, Reading (2007)
Crutchfield, J.P., Packard, N.H.: Symbolic dynamics of noisy chaos. Physica 7D, 201–223 (1983)
Reed, M., Simon, B.: Functional Analysis. Academic Press, San Diego (1980)
Crutchfield, J.P., Feldman, D.P.: Regularities unseen, randomness observed: levels of entropy convergence. Chaos 13(1), 25–54 (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Travers, N.F., Crutchfield, J.P. Exact Synchronization for Finite-State Sources. J Stat Phys 145, 1181–1201 (2011). https://doi.org/10.1007/s10955-011-0342-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10955-011-0342-4