Stationary and Transition Probabilities in Slow Mixing, Long Memory Markov Processes
Authors:
- 30 July 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 60 (9) , 5682-5701
Abstract
We observe a length-n sample generated by an unknown, stationary ergodic Markov process (model) over a finite alphabet A. Given any string w of symbols from A we want estimates of the conditional probability distribution of symbols following w, as well as the stationary probability of w. Two distinct problems that complicate estimation in this setting are: 1) long memory and 2) slow mixing, which could happen even with only one bit of memory. Any consistent estimator in this setting can only converge pointwise over the class of all ergodic Markov models. Namely, given any estimator and any sample size n, the underlying model could be such that the estimator performs poorly on a sample of size n with high probability. But can we look at a length-n sample and identify if an estimate is likely to be accurate? Since the memory is unknown a-priori, a natural approach is to estimate a potentially coarser model with memory k n = O(log n). As n grows, pointwise consistent estimates that hold eventually almost surely (e.a.s.) are known so long as the scaling of k n is not superlogarithmic in n. Here, rather than e.a.s. convergence results, we want the best answers possible with a length-n sample. Combining results in universal compression with Aldous' coupling arguments, we obtain sufficient conditions on the lengthn sample (even for slow mixing models) to identify when naive: 1) estimates of the conditional probabilities and 2) estimates related to the stationary probabilities are accurate, and also bound the deviations of the naive estimates from true values.Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- On Rate of Convergence of Statistical Estimation of Stationary Ergodic ProcessesIEEE Transactions on Information Theory, 2010
- On the minimal penalty for Markov order estimationProbability Theory and Related Fields, 2010
- Exponential Inequalities for Empirical Unbounded Context Trees2008
- ON SEQUENTIAL ESTIMATION AND PREDICTION FOR DISCRETE TIME SERIESStochastics and Dynamics, 2007
- Order Estimation of Markov ChainsIEEE Transactions on Information Theory, 2005
- The consistency of the BIC Markov order estimator2002
- Large-scale typicality of Markov sample paths and consistency of MDL order estimatorsIEEE Transactions on Information Theory, 2002
- The optimal error exponent for Markov order estimationIEEE Transactions on Information Theory, 1996
- On the estimation of the order of a Markov chain and universal data compressionIEEE Transactions on Information Theory, 1989
- Compression of individual sequences via variable-rate codingIEEE Transactions on Information Theory, 1978