|
R. G. James, J. R. Mahoney, C. J. Ellison, and J. P. Crutchfield Complexity Sciences Center Physics Department University of California at Davis Davis, California 95616 USA |
ABSTRACT: 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.