Many Roads to Synchrony: Natural Time Scales and Their Algorithms

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 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.

17 pages, 16 figures: http://cse.ucdavis.edu/~cmg/compmech/pubs/kro.htm. Santa Fe Institute Working Paper 10-11-025

References in corpus (6)

• Anatomy of a Bit: Information in a Time Series Observation
• Exact Synchronization for Finite-State Sources
• Synchronization and Control in Intrinsic and Designed Computation: An Information-Theoretic Analysis of Competing Models of Stochastic Computation
• Asymptotic Synchronization for Finite-State Sources
• Enumerating Finitary Processes
• A Light-Based Device for Solving the Hamiltonian Path Problem

Cited by in corpus (19)

• Computational Mechanics of Input-Output Processes: Structured transformations and the $\epsilon$-transducer
• Correlation-powered Information Engines and the Thermodynamics of Self-Correction
• A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression
• A new method for choosing parameters in delay reconstruction-based forecast strategies
• Thermodynamics of complexity and pattern manipulation
• Fisher information of correlated stochastic processes
• Information Symmetries in Irreversible Processes
• Statistical Signatures of Structural Organization: The case of long memory in renewal processes
• Divergent Predictive States: The Statistical Complexity Dimension of Stationary, Ergodic Hidden Markov Processes
• Thermal Efficiency of Quantum Memory Compression
• Fraudulent White Noise: Flat power spectra belie arbitrarily complex processes
• Enumerating Finitary Processes
• The Elusive Present: Hidden Past and Future Dependency and Why We Build Models
• Diffraction Patterns of Layered Close-packed Structures from Hidden Markov Models
• Parameter estimation for quantum jump unraveling
• Circumventing the Curse of Dimensionality in Prediction: Causal Rate-Distortion for Infinite-Order Markov Processes
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications
• Prediction in Projection: A new paradigm in delay-coordinate reconstruction
• The Ambiguity of Simplicity