Cutpoint Decoupling and First Passage Times for Random Walks on Graphs

DOI10.1137/S0895479897318800zbMath0934.65004OpenAlexW1965704153MaRDI QIDQ4702233

Michael Neumann, Stephen 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

Markov chainsrandom walksfirst passage timesdivide-and-conquer approachmean first passage matrixnearest-neighbour random walkconnected, undirected graphcutpoint graphs

Mathematics Subject Classification ID

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

Related Items

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