Coalescence and meeting times on n-block Markov chains

DOI10.1007/S10959-014-0579-3MaRDI QIDQ300286zbMATH OpenOpenAlexFDO

Authors Kathleen Lan, Kevin McGoff

Publication date 27 June 2016

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

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

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)

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)$.

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

Cites work

• scientific article; zbMATH DE number 3745547 (Why is no real title available?)
• scientific article; zbMATH DE number 918233 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• A recurrence theorem for dependent processes with applications to data compression
• Almost-sure waiting time results for weak and very weak Bernoulli processes
• Coalescing random walks and voter model consensus times on the torus in \({\mathbb{Z}}^ d\)
• Coalescing random walks and voting on graphs
• Entropy and data compression schemes
• Equilibrium states and the ergodic theory of Anosov diffeomorphisms
• Hidden Markov processes in the context of symbolic dynamics
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mean field conditions for coalescing random walks
• Multiple random walks in random regular graphs
• On the Stochastic and Topological Structure of Markov Chains
• On the coalescence time of reversible random walks
• Sharp error terms and necessary conditions for exponential hitting times in mixing processes.
• Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression
• Thermodynamic Formalism
• 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)