Rates of convergence of random walk on distance regular graphs (Q1281419): Difference between revisions

The cutoff phenomenon (in the sense of D. Aldous and P. Diaconis) is investigated for all simple random walks on non-bipartite distance regular graphs of \(q\)-type. The notion \(q\)-type means that the graph belongs to a known list of graphs which are constructed from matrix groups over the finite fields \(\mathbb{F}_q\). The main result of this paper states that for a large class of non-bipartite distance regular graphs of \(q\)-type \((q\) fixed) with diameter \(d\) the cutoff phenomenon appears after \(d\) steps for \(d\to\infty\). In this generality, this result is quite astonishing (at least for the reviewer). As usual, the statement of the cutoff phenomenon is derived from explicit upper and lower bounds for the total variation distance between the laws of the random walks and the uniform distribution. These estimates are obtained by using a combination of known general methods (like strong stationary times and spectral methods) as well as a lot of detailed results on the concrete graphs contained in the list under consideration. Besides the proof of the main result, the paper contains several further interesting results, for instance, on the distributions of first hitting times of antipodal points.