Coalescence and Meeting Times on $$n$$ n -Block Markov Chains

Kathleen Lan and Kevin McGoff ()
Additional contact information
Kathleen Lan: Duke University
Kevin McGoff: Duke University

Journal of Theoretical Probability, 2016, vol. 29, issue 2, 527-549

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

Keywords: Coalescing random walks; Meeting times; Markov chains; Thermodynamic formalism; 60J10; 60K35; 37A50; 37A60 (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-014-0579-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:29:y:2016:i:2:d:10.1007_s10959-014-0579-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-014-0579-3

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().