Antiduality and Möbius monotonicity: generalized coupon collector problem

DOI10.1051/ps/2019004zbMath1506.60075arXiv1903.00247OpenAlexW2951906227MaRDI QIDQ5881046

Paweł Lorek

Publication date: 9 March 2023

Published in: ESAIM: Probability and Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1903.00247

zbMATH Keywords

Markov chainspartial orderingperfect simulationMöbius monotonicityabsorption timesstrong stationary dualityfastest strong stationary timesseparation cutoffantidualitydouble dixie cup problemgeneralized coupon collector problem

Mathematics Subject Classification ID

Partial orders, general (06A06) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Stopping times; optimal stopping problems; gambling theory (60G40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Total variation and separation cutoffs are not equivalent and neither one implies the other
• The cutoff profile for the simple exclusion process on the circle
• Strong stationary duality for Möbius monotone Markov chains
• Strong stationary duality for diffusion processes
• Strong stationary times via a new form of duality
• Coincidence properties of birth and death processes
• On hitting times and fastest strong stationary times for skip-free and more general chains
• On times to quasi-stationarity for birth and death processes
• The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof
• Total variation cutoff in birth-and-death chains
• Separation cut-offs for birth and death chains
• The cutoff phenomenon for ergodic Markov processes
• Strong uniform times and finite random walks
• The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes
• What do we know about the Metropolis algorithm?
• Extreme value distributions for random coupon collector and birthday problems
• An exact formula for the move-to-front rule for self-organizing lists
• Cutoff for the Ising model on the lattice
• Characterization of cutoff for reversible Markov chains
• Generalized gambler's ruin problem: explicit formulas via Siegmund duality
• Computing cutoff times of birth and death chains
• Separation cutoff for upward skip-free chains
• Separation and coupling cutoffs for tuples of independent Markov processes
• The coupon collector’s problem revisited: generalizing the double Dixie cup problem of Newman and Shepp
• A Sufficient Condition for Continuous-Time Finite Skip-Free Markov Chains to Have Real Eigenvalues
• On absorption times and Dirichlet eigenvalues
• The Double Dixie Cup Problem
• The Generalised Coupon Collector Problem
• Shuffling Cards and Stopping Times
• Generating a random permutation with random transpositions
• SIEGMUND DUALITY FOR MARKOV CHAINS ON PARTIALLY ORDERED STATE SPACES
• Log-concavity and log-convexity in passage time densities of diffusion and birth-death processes
• [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]
• On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes