Prediction and Generation of Binary Markov Processes: Can a Finite-State Fox Catch a Markov Mouse?
arXiv:1708.00113 · doi:10.1063/1.5003041
Abstract
Understanding the generative mechanism of a natural system is a vital component of the scientific method. Here, we investigate one of the fundamental steps toward this goal by presenting the minimal generator of an arbitrary binary Markov process. This is a class of processes whose predictive model is well known. Surprisingly, the generative model requires three distinct topologies for different regions of parameter space. We show that a previously proposed generator for a particular set of binary Markov processes is, in fact, not minimal. Our results shed the first quantitative light on the relative (minimal) costs of prediction and generation. We find, for instance, that the difference between prediction and generation is maximized when the process is approximately independently, identically distributed.
arXiv comment12 pages, 12 figures; http://csc.ucdavis.edu/~cmg/compmech/pubs/gmc.htm
References in corpus (5)
- Computational Mechanics: Pattern and Prediction, Structure and Simplicity
- Synchronization and Control in Intrinsic and Designed Computation: An Information-Theoretic Analysis of Competing Models of Stochastic Computation
- How Hidden are Hidden Processes? A Primer on Crypticity and Entropy Convergence
- The Markov Memory for Generating Rare Events
- Trimming the Independent Fat: Sufficient Statistics, Mutual Information, and Predictability from Effective Channel States
Cited by in corpus (6)
- Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
- Strong and Weak Optimizations in Classical and Quantum Models of Stochastic Processes
- Spectral Simplicity of Apparent Complexity, Part I: The Nondiagonalizable Metadynamics of Prediction
- The fundamental thermodynamic bounds on finite models
- Quantum Dimension Reduction of Hidden Markov Models
- Ideal stochastic process modeling with post-quantum quasiprobabilistic theories