Prediction and generation of binary Markov processes: Can a finite-state fox catch a Markov mouse?
- 1 January 2018
- journal article
- conference paper
- Published by AIP Publishing in Chaos: An Interdisciplinary Journal of Nonlinear Science
- Vol. 28 (1) , 013109
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.Keywords
Funding Information
- National Science Foundation (REU Program)
- Foundational Questions Institute (FQXi-RFP-1609)
- DOD | United States Army | RDECOM | Army Research Office (W911NF-13-1-0340, W911NF-13-1-0390)
- John Templeton Foundation (52095)
This publication has 14 references indexed in Scilit:
- Minimum memory for generating rare eventsPhysical Review E, 2017
- Predictive models and generative complexityJournal of Systems Science and Complexity, 2012
- Between order and chaosNature Physics, 2011
- How hidden are hidden processes? A primer on crypticity and entropy convergenceChaos: An Interdisciplinary Journal of Nonlinear Science, 2011
- Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computationChaos: An Interdisciplinary Journal of Nonlinear Science, 2010
- ON THE GENERATIVE NATURE OF PREDICTIONAdvances in Complex Systems, 2009
- Non-sufficient Memories That Are Sufficient for Prediction2009
- Computational Mechanics: Pattern and Prediction, Structure and SimplicityJournal of Statistical Physics, 2001
- A new outlook on Shannon's information measuresIEEE Transactions on Information Theory, 1991
- On Stochastic Processes Derived From Markov ChainsThe Annals of Mathematical Statistics, 1965