×

Cutpoint decoupling and first passage times for random walks on graphs. (English) Zbl 0934.65004

The paper considers random walks on a connected, undirected graph and investigates the problem of computing the corresponding mean first passage matrix \(E\). Random walks on undirected graphs occur in such applications as Markov chains on hypercubes, which are a type of nearest-neighbour random walk.
The authors prove that for such Markov chains, the presence of cutpoints in the graph can be exploited to simplify the computation of the mean first passage matrix \(E\). This leads to a divide-and-conquer approach to the computation of the matrix \(E\) in the case that the underlying graph is a tree. When there is a cutpoint in the graph, an explicit formula for the mean first passage matrix \(E\) is provided and the computation of \(E\) can be broken into many smaller tasks of the same type that can be computed in parallel.

MSC:

65C40 Numerical analysis or methods applied to Markov chains
15B51 Stochastic matrices
60G50 Sums of independent random variables; random walks
60J22 Computational methods in Markov chains
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI