Many roads to synchrony: Natural time scales and their algorithms
- Author(s): James, RG
- Mahoney, JR
- Ellison, CJ
- Crutchfield, JP
- et al.
Published Web Locationhttps://doi.org/10.1103/PhysRevE.89.042135
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 ε-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 ε-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. © 2014 American Physical Society.
Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.