Coalescence and meeting times on n-block Markov chains

DOI10.1007/S10959-014-0579-3zbMATH Open1347.60101arXiv1410.0099OpenAlexW2031414464MaRDI QIDQ300286FDOQ300286

Authors: Kathleen Lan, Kevin McGoff 

Publication date: 27 June 2016

Published in: Journal of Theoretical Probability (Search for Journal in Brave)

Abstract: We consider finite state, discrete-time, mixing Markov chains $(V,P)$, where $V$ is the state space and $P$ is transition matrix. To each such chain $(V,P)$, we associate a sequence of chains $(V_n,P_n)$ by coding trajectories of $(V,P)$ according to their overlapping $n$-blocks. The chain $(V_n,P_n)$, called the $n$-block Markov chain associated to $(V,P)$, may be considered an alternate version of $(V,P)$ having memory of length $n$. Along such a sequence of chains, we characterize the asymptotic behavior of coalescence times and meeting times as $n$ tends to infinity. In particular, we define an algebraic quantity $L(V,P)$ depending only on $(V,P)$, and we show that if the coalescence time on $(V_n,P_n)$ is denoted by $C_n$, then the quantity $frac1nlog{C}_n$ converges in probability to $L(V,P)$ with exponential rate. Furthermore, we fully characterize the relationship between $L(V,P)$ and the entropy of $(V,P)$.

Full work available at URL: https://arxiv.org/abs/1410.0099

Recommendations

• Meeting times for independent Markov chains
• Coupling and mixing times in a Markov chain
• Mixing and hitting times for finite Markov chains
• Intersection and mixing times for reversible chains
• scientific article; zbMATH DE number 1567896

zbMATH Keywords

Markov chainsthermodynamic formalismcoalescing random walksmeeting times

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Sums of independent random variables; random walks (60G50) Limit theorems in probability theory (60F99) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Dynamical aspects of statistical mechanics (37A60)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Thermodynamic Formalism
• Equilibrium states and the ergodic theory of Anosov diffeomorphisms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coalescing random walks and voter model consensus times on the torus in \({\mathbb{Z}}^ d\)
• Mean field conditions for coalescing random walks
• Sharp error terms and necessary conditions for exponential hitting times in mixing processes.
• Coalescing random walks and voting on graphs
• Multiple random walks in random regular graphs
• Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression
• On the Stochastic and Topological Structure of Markov Chains
• A recurrence theorem for dependent processes with applications to data compression
• Entropy and data compression schemes
• Almost-sure waiting time results for weak and very weak Bernoulli processes
• On the coalescence time of reversible random walks
• Hidden Markov processes in the context of symbolic dynamics
• Waiting times: Positive and negative results on the Wyner-Ziv problem

This page was built for publication: Coalescence and meeting times on \(n\)-block Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300286)