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

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