The Hitting Time of Multiple Random Walks

DOI10.1137/15M1010737zbMath1344.60043MaRDI QIDQ3185674

Rushabh Patel, Bullo, Francesco, Andrea Carron

Publication date: 4 August 2016

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

zbMATH Keywords

surveillancesequential quadratic programmingMarkov chainroboticshitting timeKemeny constantmultiple random walks

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Methods of successive quadratic programming type (90C55) Random walks on graphs (05C81)

Related Items (10)

Further results on the expected hitting time, the cover cost and the related invariants of graphs ⋮ On the robustness of a synchronized multi-robot system ⋮ Extremal hitting times of trees with some given parameters ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ On the (reverse) cover cost of trees with some given parameters ⋮ Expected hitting times for random walks on quadrilateral graphs and their applications ⋮ Expected hitting times for random walks on the diamond hierarchical graphs involving some classical parameters ⋮ Expected hitting times for random walks on the \(k\)-triangle graph and their applications ⋮ Dumbbell graphs with extremal (reverse) cover cost ⋮ Spatio-temporal dynamics of random transmission events: from information sharing to epidemic spread

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tight bounds for the cover time of multiple random walks
• Fastest expected time to mixing for a Markov chain on a directed graph
• The Kemeny constant for finite homogeneous ergodic Markov chains
• Random walks and the effective resistance of networks
• The hitting and cover times of Metropolis walks
• On hitting times of random walks on trees
• A note on expected hitting times for birth and death chains
• Non-negative matrices and Markov chains. 2nd ed
• Bounds on the cover time
• Robotic Surveillance and Markov Chains With Minimal Weighted Kemeny Constant
• Multiple Random Walks in Random Regular Graphs
• The Kronecker Product of Graphs
• Multiple Random Walks and Interacting Particle Systems
• How Well Do Random Walks Parallelize?
• A tight upper bound on the cover time for random walks on graphs
• Kemeny's Constant and the Random Surfer
• Stochastic kronecker graphs
• Many Random Walks Are Faster Than One
• An in-depth analysis of stochastic Kronecker graphs
• The Role of Kemeny's Constant in Properties of Markov Chains
• On the Kemeny constant and stationary distribution vector for a Markov chain

This page was built for publication: The Hitting Time of Multiple Random Walks