Covering problems for Markov chains

DOI10.1214/AOP/1176991686zbMATH Open0712.60076OpenAlexW2068008593MaRDI QIDQ749044FDOQ749044

D. Kharzeev

Publication date: 1988

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aop/1176991686

zbMATH Keywords

coupon collector's problemmoment-generating function

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sample path properties (60G17)

Cited In (34)

• Cover times for random walk on dynamical percolation
• The hitting and cover times of Metropolis walks
• An introduction to covering problems for random walks on graphs
• Gumbel fluctuations for cover times in the discrete torus
• On an epidemic model on finite graphs
• Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
• The generating functions of hitting times for random walk on trees
• How to Design a Linear Cover Time Random Walk on a Finite Graph
• Random walks on highly symmetric graphs
• On the cover time of \(\lambda\)-biased walk on supercritical Galton-Watson trees
• The Evolution of the Cover Time
• Exponential concentration of cover times
• How long is the chaos game?
• Cover times for words in symmetric and nonsymmetric cases: A comparison
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Random walks on edge transitive graphs
• Limit law for the cover time of a random walk on a binary tree
• Reversible random walks on dynamic graphs
• Cover times for sequences of reversible Markov chains on random graphs
• The cover time of a (multiple) Markov chain with rational transition probabilities is rational
• A spectral characterization for concentration of the cover time
• The hitting and cover times of random walks on finite graphs using local degree information
• Sandwich theorem of cover times
• Hitting time of large subsets of the hypercube
• On the mean and variance of cover times for random walks on graphs
• Painting a graph with competing random walks
• Cover times, blanket times, and majorizing measures
• Covering with blocks in the non-symmetric case
• Expected cover times of random walks on symmetric graphs
• Some sample path properties of a random walk on the cube
• Estimating the Mean Cover Time of a Semi-Markov Process via Simulation
• Cover levels and random interlacements
• Threshold limits for cover times
• Improved approximation of the minimum cover time

Recommendations

• Title not available (Why is that?) 👍 👎
• Lower bounds for covering times for reversible Markov chains and random walks on graphs 👍 👎
• Cover times for sequences of reversible Markov chains on random graphs 👍 👎
• Covering runs in binary Markov sequences 👍 👎
• Finite Markov Chains and Algorithmic Applications 👍 👎
• Reachability problems for Markov chains 👍 👎
• Markov loops, coverings and fields 👍 👎
• Some bounds for Markov chains 👍 👎
• The Littlewood-Offord problem for Markov chains 👍 👎
• Technical comment. A problem on Markov chains 👍 👎

This page was built for publication: Covering problems for Markov chains

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