Strong uniform times and finite random walks (Q1094756)

This paper is concerned with obtaining bounds for the rate of convergence to the stationary distribution for finite Markov chains \(\{X_ n,n\geq 0\}\) having strong symmetry properties for the transition matrices. The use of strong uniform times to bound separation distance is emphasized, the strong uniform time T being a randomized stopping time such that \(P(X_ k=i| T=k)=\pi (i)\) for all \(0\leq k<\infty\) and i, \(\pi\) being the stationary distribution. It is shown that a strong uniform time T always exists and that, if \(\pi_ n\) is the distribution of \(X_ n\), the separation distance \(\max_{i}(1-\pi_ n(i)/\pi (i))\leq P(T>n)\), \(n\geq 0\). This methodology is related to coupling and Fourier analysis procedures. Various examples for random walks on groups are given to illustrate the results.