Stephen Chestnut ; Manuel E. Lladser - Occupancy distributions in Markov chains via Doeblin's ergodicity coefficient

dmtcs:2789 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2789
Occupancy distributions in Markov chains via Doeblin's ergodicity coefficientArticle

Authors: Stephen Chestnut 1; Manuel E. Lladser 1

  • 1 Department of Applied Mathematics [Boulder]

We state and prove new properties about Doeblin's ergodicity coefficient for finite Markov chains. We show that this coefficient satisfies a sub-multiplicative type inequality (analogous to the Markov-Dobrushin's ergodicity coefficient), and provide a novel but elementary proof of Doeblin's characterization of weak-ergodicity for non-homogeneous chains. Using Doeblin's coefficient, we illustrate how to approximate a homogeneous but possibly non-stationary Markov chain of duration $n$ by independent and short-lived realizations of an auxiliary chain of duration of order $\ln (n)$. This leads to approximations of occupancy distributions in homogeneous chains, which may be particularly useful when exact calculations via one-step methods or transfer matrices are impractical, and when asymptotic approximations may not be yet reliable. Our findings may find applications to pattern problems in Markovian and non-Markovian sequences that are treatable via embedding techniques.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: pattern,compound Poisson approximation,Doeblin,Markov chain embedding technique,motif,occupancy distribution,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
Funding:
    Source : OpenAIRE Graph
  • AMC-SS: Markovian Embeddings for the Analysis and Computation of Patterns in non-Markovian Random Sequences; Funder: National Science Foundation; Code: 0805950

3 Documents citing this article

Consultation statistics

This page has been seen 173 times.
This article's PDF has been downloaded 857 times.