Many Roads to Synchrony: Natural Time Scales and Their Algorithms

We survey the variety of ways in which one synchronizes to a stochastic process. We define associated length scales, providing characterization theorems and efficient algorithms for their calculation. We demonstrate that many of the length scales are minimized by using the ε-machine, compared to all of a process's alternative models. We also show that the concept of Markov order, familiar in stochastic process theory, is a topological property of the ε-machine presentation. Moreover, we find that it can only be computed when using the ε-machine, not any alternative. We illustrate the results by presenting evidence that infinite Markov order and infinite crypticity are dominant properties in the space of finite-memory processes.