Rates of convergence of random walk on distance regular graphs (Q1281419)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Rates of convergence of random walk on distance regular graphs
scientific article

    Statements

    Rates of convergence of random walk on distance regular graphs (English)
    0 references
    0 references
    2 November 1999
    0 references
    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.
    0 references
    0 references
    distance regular graphs
    0 references
    convergence of random walks
    0 references
    uniform distribution
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references