Skip to main content
SpringerLink
Log in

Asymptotic Synchronization for Finite-State Sources

  • Published:
Journal of Statistical Physics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Travers, N., Crutchfield, J.P.: Exact synchronization for finite-state sources. J. Stat. Phys. doi:10.1007/s10955-011-0342-4. arxiv.org:1008.4182 [nlin.CD]

  2. Crutchfield, J.P., Feldman, D.P.: Regularities unseen, randomness observed: Levels of entropy convergence. Chaos 13(1), 25–54 (2003)

    Article  MATH  ADS  MathSciNet  Google Scholar 

  3. Ellison, C.J., Mahoney, J.R., Crutchfield, J.P.: Prediction, retrodiction, and the amount of information stored in the present. J. Stat. Phys. 136(6), 1005–1034 (2009)

    Article  MATH  ADS  MathSciNet  Google Scholar 

  4. Mahoney, J.R., Ellison, C.J., Crutchfield, J.P.: Information accessibility and cryptic processes. J. Phys. A, Math. Theor. 42, 362002 (2009)

    Article  MathSciNet  Google Scholar 

  5. Crutchfield, J.P., Young, K.: Inferring statistical complexity. Phys. Rev. Lett. 63, 105–108 (1989)

    Article  ADS  MathSciNet  Google Scholar 

  6. Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley-Interscience, New York (2006)

    MATH  Google Scholar 

  7. Shannon, C.E., Weaver, W.: The Mathematical Theory of Communication. University of Illinois Press, Champaign-Urbana (1962)

    Google Scholar 

  8. Massey, J.L.: Markov information sources. In: Skwirzynski, J.K. (ed.) New Directions in Signal Processing in Communication and Control. NATO Advanced Study Institutes Series, vol. E25, pp. 15–26. Noordhoff, Leyden (1975)

    Google Scholar 

  9. Glynn, P.W., Ormoneit, D.: Hoeffding’s inequality for uniformly ergodic Markov chains. Stat. Probab. Lett. 56(2), 143–146 (2002)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Complexity Sciences Center, University of California at Davis, One Shields Avenue, Davis, CA, 95616, USA

    Nicholas F. Travers & James P. Crutchfield

  2. Mathematics Department, University of California at Davis, One Shields Avenue, Davis, CA, 95616, USA

    Nicholas F. Travers & James P. Crutchfield

  3. Physics Department, University of California at Davis, One Shields Avenue, Davis, CA, 95616, USA

    James P. Crutchfield

  4. Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM, 87501, USA

    James P. Crutchfield

Authors
  1. Nicholas F. Travers
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. James P. Crutchfield
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to James P. Crutchfield.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Travers, N.F., Crutchfield, J.P. Asymptotic Synchronization for Finite-State Sources. J Stat Phys 145, 1202–1223 (2011). https://doi.org/10.1007/s10955-011-0349-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10955-011-0349-x

Keywords

Search

Navigation