Covering problems for Markov chains

DOI10.1214/AOP/1176991686MaRDI QIDQ749044zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Covering runs in binary Markov sequences
• Markov loops, coverings and fields
• Cover times for sequences of reversible Markov chains on random graphs
• scientific article; zbMATH DE number 36205
• Reachability problems for Markov chains
• Finite Markov Chains and Algorithmic Applications
• Technical comment. A problem on Markov chains
• The Littlewood-Offord problem for Markov chains
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Some bounds for Markov chains

Cited in

(36)

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

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)