On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes

DOI10.1016/S0166-218X(00)00201-8zbMath0983.60036OpenAlexW2106699235WikidataQ126550952 ScholiaQ126550952MaRDI QIDQ5936463

Van H. Vu, Igor Pak

Publication date: 2 April 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00201-8

zbMATH Keywords

Markov chainsrandom walksstopping timerandom graphscutoff phenomenonseparation distancesharp threshold

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Antiduality and Möbius monotonicity: generalized coupon collector problem, A new large \(N\) phase transition in \(\text{YM}_2\), More on average case vs approximation complexity, Separation cut-offs for birth and death chains, Random doubly stochastic tridiagonal matrices, Two-dimensional gauge theories of the symmetric group \(S_n\) and branched \(n\)-coverings of Riemann surfaces in the large-\(n\) limit, Rapidly mixing random walks and bounds on characters of the symmetric group

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong stationary times via a new form of duality
• Strong uniform times and finite random walks
• Random walks on finite groups with few random generators
• On Russo's approximate zero-one law
• Random random walks on \(\mathbb{Z}_2^d\)
• Enumeration and random walks on finite groups
• On random random walks
• A Model for Random Random-Walks on Finite Groups
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Every monotone graph property has a sharp threshold
• The theory of Möbius functions
• The cutoff phenomenon in finite Markov chains.