Rates of convergence of random walk on distance regular graphs
type: Item
instance of: scholarly article
title: Rates of convergence of random walk on distance regular graphs
zbMATH Open document ID: 0923.60010
author: Eric David Belsley
publication date: 1999-11-02T00:00:00Z
review text: 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.
reviewed by: Michael Voit
Mathematics Subject Classification ID: 60B15
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05E30
zbMATH DE Number: 1267624
zbMATH Keywords: distance regular graphs
zbMATH Keywords: convergence of random walks
zbMATH Keywords: uniform distribution
MaRDI profile type: Publication
full work available at URL: s004400050198
OpenAlex ID: W2008409101
DOI: 10.1007/S004400050198
published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
description: scientific article; zbMATH DE number 1267624