Many roads to synchrony: Natural time scales and their algorithms

Ryan G. James, John R. Mahoney, Christopher J. Ellison, and James P. Crutchfield
Phys. Rev. E 89, 042135 – Published 18 April 2014

Abstract

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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
8 More
  • Received 23 December 2010
  • Revised 20 December 2013

DOI:https://doi.org/10.1103/PhysRevE.89.042135

©2014 American Physical Society

Authors & Affiliations

Ryan G. James1,2,*, John R. Mahoney3,†, Christopher J. Ellison1,4,‡, and James P. Crutchfield1,5,§

  • 1Complexity Sciences Center and Department of Physics, University of California at Davis, One Shields Avenue, Davis, California 95616, USA
  • 2Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado 80309, USA
  • 3School of Natural Sciences, University of California, Merced, California 95344, USA
  • 4Center for Complexity and Collective Computation, Wisconsin Institute for Discovery, University of Wisconsin—Madison, Madison, Wisconsin 53715, USA
  • 5Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA

  • *rgjames@ucdavis.edu
  • jmahoney3@ucmerced.edu
  • cellison@cse.ucdavis.edu
  • §chaos@ucdavis.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 89, Iss. 4 — April 2014

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×