Inferring Markov Chains: Bayesian Estimation, Model Comparison, Entropy Rate, and Out-of-class Modeling

Abstract

Markov chains are a natural and well understood tool for describing one-dimensional patterns in time or space. We show how to infer $k$-th order Markov chains, for arbitrary $k$, from finite data by applying Bayesian methods to both parameter estimation and model-order selection. Extending existing results for multinomial models of discrete data, we connect inference to statistical mechanics through information-theoretic (type theory) techniques. We establish a direct relationship between Bayesian evidence and the partition function which allows for straightforward calculation of the expectation and variance of the conditional relative entropy and the source entropy rate. Finally, we introduce a novel method that uses finite data-size scaling with model-order comparison to infer the structure of out-of-class processes.

14 pages, 12 figures; http://cse.ucdavis.edu/~cmg/compmech/pubs/imc.html

References in corpus (2)

• Statistical Complexity of Simple 1D Spin Systems
• Estimating probabilities from experimental frequencies

Cited by in corpus (19)

• Modeling sequences and temporal networks with dynamic community structures
• Detecting Memory and Structure in Human Navigation Patterns Using Markov Chain Models of Varying Order
• When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
• Dynamics of Bayesian Updating with Dependent Data and Misspecified Models
• HypTrails: A Bayesian Approach for Comparing Hypotheses About Human Trails on the Web
• Bayesian Structural Inference for Hidden Processes
• Structure and Randomness of Continuous-Time Discrete-Event Processes
• Predictive Bayesian selection of multistep Markov chains, applied to the detection of the hot hand and other statistical dependencies in free throws
• Enumerating Finitary Processes
• Measuring the rationality in evacuation behavior with deep learning
• Entropy estimators for Markovian sequences: A comparative analysis
• MixedTrails: Bayesian hypothesis comparison on heterogeneous sequential data
• Predicting Sequences of Traversed Nodes in Graphs using Network Models with Multiple Higher Orders
• The Inherent Randomness of Evolving Populations
• Hidden Markov model analysis for fluorescent time series of quantum dots
• Learning the Markov order of paths in a network
• Information-theoretic analysis of temporal dependence in discrete stochastic processes: Application to precipitation predictability
• Entropy Rates of the Multidimensional Moran Processes and Generalizations
• Inference of Markovian Properties of Molecular Sequences from NGS Data and Applications to Comparative Genomics