Premium
RANDOM WALKS ON REGULAR POLYHEDRA AND OTHER DISTANCE–REGULAR GRAPHS
Author(s) -
Slijpe A.R.D.
Publication year - 1984
Publication title -
statistica neerlandica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.52
H-Index - 39
eISSN - 1467-9574
pISSN - 0039-0402
DOI - 10.1111/j.1467-9574.1984.tb01118.x
Subject(s) - combinatorics , mathematics , vertex (graph theory) , markov chain , path graph , wheel graph , regular graph , graph , random regular graph , neighbourhood (mathematics) , discrete mathematics , graph power , line graph , 1 planar graph , statistics , mathematical analysis
In this paper we consider Markov chains of the following type: the state space is the set of vertices of a connected, regular graph, and for each vertex transitions are to the adjacent vertices, with equal probabilities. When the mean first–passage matrix F of such a Markov chain is symmetric, the expectation and variance of first–entrance times, recurrence times, number of visits to a vertex and the expectation of the number of different vertices visited, can easily be computed from the entries of F. The method is most effective, when the underlying graph is distance–regular; then F is symmetric and the entries of F can easily be obtained from the graph.