The hitting time of multiple random walks

DOI10.1137/15M1010737MaRDI QIDQ3185674zbMATH OpenFDO

Authors Rushabh Patel, Andrea Carron, Francesco Bullo

Publication date 4 August 2016

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

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

zbMATH Keywords

hitting timeKemeny constantMarkov chainmultiple random walksroboticssequential quadratic programmingsurveillance

Mathematics Subject Classification ID

Random walks on graphs (05C81) 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) Computational methods in Markov chains (60J22) Methods of successive quadratic programming type (90C55)

Recommendations

• Finding hitting times in various graphs
• An explicit formula of hitting times for random walks on graphs
• Hitting times for random walks on vertex-transitive graphs
• A Spanning Tree Method for Bounding Hitting Times of Random Walks on Graphs
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning

Cites work

• A note on expected hitting times for birth and death chains
• A tight upper bound on the cover time for random walks on graphs
• An in-depth analysis of stochastic Kronecker graphs
• Bounds on the cover time
• Fastest expected time to mixing for a Markov chain on a directed graph
• How Well Do Random Walks Parallelize?
• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• scientific article; zbMATH DE number 3514781 (Why is no real title available?)
• scientific article; zbMATH DE number 635657 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• Kemeny's Constant and the Random Surfer
• Many Random Walks Are Faster Than One
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Multiple Random Walks and Interacting Particle Systems
• Multiple random walks in random regular graphs
• Non-negative matrices and Markov chains. 2nd ed
• On hitting times of random walks on trees
• On the Kemeny constant and stationary distribution vector for a Markov chain
• Random walks and the effective resistance of networks
• Robotic Surveillance and Markov Chains With Minimal Weighted Kemeny Constant
• Stochastic Kronecker graphs
• The hitting and cover times of Metropolis walks
• The Kemeny constant for finite homogeneous ergodic Markov chains
• The Kronecker Product of Graphs
• The role of Kemeny's constant in properties of Markov chains
• Tight bounds for the cover time of multiple random walks

Cited in

(19)

• Further results on the expected hitting time, the cover cost and the related invariants of graphs
• Hitting times for the perturbed reflecting random walk
• Dumbbell graphs with extremal (reverse) cover cost
• On the robustness of a synchronized multi-robot system
• On the (reverse) cover cost of trees with some given parameters
• Expected hitting times for random walks on the \(k\)-triangle graph and their applications
• Finding hitting times in various graphs
• Hitting and commute times in large random neighborhood graphs
• Optimal running times for systems of random walks involving several particles
• 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
• Extremal hitting times of trees with some given parameters
• Spatio-temporal dynamics of random transmission events: from information sharing to epidemic spread
• Multiple random walks on graphs: mixing few to cover many
• Hitting times for second-order random walks
• Random walks and consensus problem on tree network with an identical degree distribution
• Collaboration of random walks on graphs
• First exit-time analysis for an approximate Barndorff-Nielsen and Shephard model with stationary self-decomposable variance process
• The hitting and cover times of Metropolis walks

This page was built for publication: The hitting time of multiple random walks

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