Many Roads to Synchrony: Natural Time Scales and Their Algorithms
Skip to main content
Open Access Publications from the University of California

UC Davis

UC Davis Previously Published Works bannerUC Davis

Many Roads to Synchrony: Natural Time Scales and Their Algorithms

  • Author(s): James, Ryan G.;
  • Mahoney, John R.;
  • Ellison, Christopher J.;
  • Crutchfield, James P.
  • et al.

Published Web Location
No data is associated with this publication.

We consider two important time scales---the Markov and cryptic orders---that monitor how an observer synchronizes to a finitary stochastic process. We show how to compute these orders exactly and that they are most efficiently calculated from the epsilon-machine, a process's minimal unifilar model. Surprisingly, though the Markov order is a basic concept from stochastic process theory, it is not a probabilistic property of a process. Rather, it is a topological property and, moreover, it is not computable from any finite-state model other than the epsilon-machine. Via an exhaustive survey, we close by demonstrating that infinite Markov and infinite cryptic orders are a dominant feature in the space of finite-memory processes. We draw out the roles played in statistical mechanical spin systems by these two complementary length scales.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item