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)

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)