Bounds on expected hitting times for a random walk on a connected graph

DOI10.1016/0024-3795(90)90321-3MaRDI QIDQ922556zbMATH OpenOpenAlexFDO

Authors José Luis Palacios

Publication date 1990

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(90)90321-3

zbMATH Keywords

connected graphexpected hitting timesmaximum expected number of steps to get from one vertex to anotherrandom walk

Mathematics Subject Classification ID

Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50)

Recommendations

• Expected hitting times for a random walk on a connected graph
• Maximum hitting time for random walks on graphs
• Expected cover times of random walks on symmetric graphs
• On partial sums of hitting times
• On a Result of Aleliunas et al. Concerning Random Walks on Graphs

Cites work

• A bound on the spectral radius of graphs
• Bounds on the spectral radius of graphs with e edges
• Expected hitting times for a random walk on a connected graph
• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• scientific article; zbMATH DE number 3181418 (Why is no real title available?)
• Non-negative matrices and Markov chains. 2nd ed

Cited in

(31)

• Expected hitting times for a random walk on a connected graph
• First hitting times of simple random walks on graphs with congestion points
• Further results on the expected hitting time, the cover cost and the related invariants of graphs
• The hitting times of random walks on bicyclic graphs
• Dumbbell graphs with extremal (reverse) cover cost
• Lower bounds on partial sums of expected hitting times
• Slowdown for the geodesic-biased random walk
• Expected hitting times for random walks on the \(k\)-triangle graph and their applications
• Decomposing hitting times of walks on graphs into simpler ones
• On hitting times for a simple random walk on dense Erdös-Rényi random graphs
• Finding hitting times in various graphs
• On some general operators of hypergraphs
• A Spanning Tree Method for Bounding Hitting Times of Random Walks on Graphs
• scientific article; zbMATH DE number 5629593 (Why is no real title available?)
• Maximum hitting time for random walks on graphs
• Expected hitting and cover times of random walks on some special graphs
• On partial sums of hitting times
• Hitting times for random walks on subdivision and triangulation graphs
• Expected hitting times for random walks on quadrilateral graphs and their applications
• Return probabilities and hitting times of random walks on sparse Erdös-Rényi graphs
• Expected hitting times for random walks on the diamond hierarchical graphs involving some classical parameters
• Chung-Yau invariants and graphs with symmetric hitting times
• The hitting time of random walk on unicyclic graphs
• Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs
• Hitting times for random walks on tricyclic graphs
• Leontief meets Markov: sectoral vulnerabilities through circular connectivity
• Laplace eigenvalues of graphs---a survey
• Hitting times of random walks on unicyclic graphs with a given number of pendant vertices
• The hitting time of random walks on unicyclic graphs with a given maximum degree
• Hitting times in the binomial random graph
• The expected hitting times for finite Markov chains

This page was built for publication: Bounds on expected hitting times for a random walk on a connected graph

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