Cutpoint Decoupling and First Passage Times for Random Walks on Graphs

DOI10.1137/S0895479897318800MaRDI QIDQ4702233zbMATH OpenOpenAlexFDO

Authors M. Neumann, S. J. Kirkland

Publication date 24 November 1999

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895479897318800

zbMATH Keywords

connected, undirected graphcutpoint graphsdivide-and-conquer approachfirst passage timesMarkov chainsmean first passage matrixnearest-neighbour random walkrandom walks

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions
• On the first passage time of a simple random walk on a tree
• The expected hitting times for graphs with cutpoints.
• scientific article; zbMATH DE number 878897
• Exact and approximate mean first passage times on trees and other necklace structures: a local equilibrium approach

Cited in

(11)

• The expected hitting times for graphs with cutpoints.
• Markov chain sensitivity measured by mean first passage times
• The hitting times of random walks on bicyclic graphs
• Decomposing hitting times of walks on graphs into simpler ones
• Cutoff phenomenon for the simple exclusion process on the complete graph
• Cutpoints and Exchangeable Events for Random Walks
• Extremal first passage times for trees
• A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions
• Hitting times for random walks on tricyclic graphs
• On the inverse mean first passage matrix problem and the inverse \(M\)-matrix problem
• Some further results on the maximal hitting times of trees with some given parameters

This page was built for publication: Cutpoint Decoupling and First Passage Times for Random Walks on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4702233)