Coalescence and meeting times on \(n\)-block Markov chains (Q300286)

This work studies coalescence times for a type of Markov chains with memory of finite length \(n\). Starting from a standard discrete-time Markov chain on a finite space \(V\) with transition matrix \(P\), the authors consider a Markov chain on \(V^n\) by keeping track of the last \(n\) positions visited by the Markov chain. One step of this \(n\)-block Markov chain then consists in forgetting the first element of the \(n\)-tuple, and adding the next site visited. The main result the authors obtain is that the sequence of coalescence times of the \(n\)-block Markov chains \((C_n)\) satisfies \[ \mathbb{P}\left[\left|\frac{1}{n}\log C_n - L(V,P)\right| > \varepsilon \right] \leq e^{-\delta n} \] for \(n\) large enough, where \(L(V,P) = -\log \lambda\) with \(\lambda\) the spectral radius of the matrix \(P^2\). They also show that the quantity \(L(V,P)\) governs the asymptotics of the maximal and the expected meeting times of independent copies of the \(n\)-block chains at a logarithmic scale.