Random walks on highly symmetric graphs
type: Item
instance of: scholarly article
title: Random walks on highly symmetric graphs
zbMATH Open document ID: 0711.60068
DOI: 10.1007/BF01046092
author: Amine Sbihi
author: Luc Devroye
published in: Journal of Theoretical Probability
publication date: 1990-01-01T00:00:00Z
review text: The author considers uniform random walks on finite graphs with n nodes. (For a finite Markov chain, let the covering time T be the time taken to visit all the states. D. J. Aldous showed that \({\mathbb{E}}(T)\) is approximately Rn log n, where n is the cardinality of a finite group and R is the mean number of visits to the initial state in a short time.) If a finite connected graph with n vertices is given, the nearest neighbor random walk on this graph is considered: for a vertex i, if \(v_ i\) is the number of edges connected to i, the probability that a particle moves from i to a neighboring vertex j is \(1/v_ i\). Several results have been obtained for the nearest neighbor random walk on graphs (D. J. Aldous), foremost among which is a general lower bound \({\mathbb{E}}_ n(T)=\Omega (n \log n)\) for the walk started with the stationary distribution \(\pi\). In the present paper, graphs for which the nearest neighbor random walk has symmetrical mean hitting times, that is \({\mathbb{E}}_ i(T_ j)={\mathbb{E}}_ j(T_ i)\) for all distinct vertices i,j are considered. Bounds for \({\mathbb{E}}(T)\) are provided, and in more detail two classes of graphs are studied, namely vertex-transitive graphs and distance-regular graphs.
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 4169796
zbMATH Keywords: random walks on finite graphs
zbMATH Keywords: nearest neighbor random walk on graphs
zbMATH Keywords: hitting times
zbMATH Keywords: vertex-transitive graphs and distance-regular graphs
reviewed by: Gabriel V. Orman
MaRDI profile type: Publication
cites work: On the time taken by random walks on finite groups to visit every state
cites work: Minimization algorithms and random walk on the d-cube
cites work: Lower bounds for covering times for reversible Markov chains and random walks on graphs
cites work: Hitting times for random walks on vertex-transitive graphs
cites work: Q3218140
cites work: Q4770409
cites work: Covering problems for Brownian motion on spheres
cites work: Covering problems for Markov chains
cites work: Some sample path properties of a random walk on the cube
cites work: Some Extremal Markov Chains
Recommended article: Random walks and orthogonal functions associated with highly symmetric graphs
Recommended article: Q5203456
Recommended article: Random walks on the random graph
Recommended article: Q3757091
Recommended article: Random Walks on Dense Graphs and Graphons
Recommended article: Recurrent random walks and the absence of continuous symmetry breaking on graphs
Recommended article: Q4888165
Recommended article: Random Walks on Regular and Irregular Graphs
description: scientific article; zbMATH DE number 4169796