A Gumbel law for Markovian super-coupon collection

An $r$-element subset of an $n$-element universe evolves by replacing a uniformly chosen element with a uniformly chosen element outside the current set. Each configuration collects all of its $s$-element subsets. For every fixed pair $2\le s<r$, we prove that the expected time to collect all $s$-subsets is asymptotic to\[\frac{\binom ns}{\binom{r-1}{s-1}}\log\binom ns.\]This proves the fixed-parameter off-diagonal case of the conjecture of Athreya, Mukherjee and Mukherjee. We also obtain a Poisson limit for the number of subsets still missing near completion and a standard Gumbel limit for the centered and scaled collection time. The conclusions hold from every initial configuration. The proof controls joint avoidance of any fixed family of target subsets, uniformly over their overlaps. Restricting the walk to the labels in that family gives a finite transition matrix, and a stationary-flow identity determines its leading killing rate. Standard spectral and factorial-moment arguments then give the collection-time limits. This record contains the PDF preprint and matching editable LaTeX sources with build instructions. The results are analytic, with fixed r and s as n tends to infinity. AI assistance is disclosed in the manuscript. This is a preprint and has not undergone journal peer review.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-12
DOI
https://doi.org/10.5281/zenodo.24175197
Primary Topic
Stochastic processes and statistical mechanics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A Gumbel law for Markovian super-coupon collection

Sam Vaseghi
Zenodo (CERN European Organization for Nuclear Research)
Stochastic processes and statistical mechanics
preprint

A Gumbel law for Markovian super-coupon collection

Sam Vaseghi
preprint en

Abstract

An $r$-element subset of an $n$-element universe evolves by replacing a uniformly chosen element with a uniformly chosen element outside the current set. Each configuration collects all of its $s$-element subsets. For every fixed pair $2\le s<r$, we prove that the expected time to collect all $s$-subsets is asymptotic to\[\frac{\binom ns}{\binom{r-1}{s-1}}\log\binom ns.\]This proves the fixed-parameter off-diagonal case of the conjecture of Athreya, Mukherjee and Mukherjee. We also obtain a Poisson limit for the number of subsets still missing near completion and a standard Gumbel limit for the centered and scaled collection time. The conclusions hold from every initial configuration. The proof controls joint avoidance of any fixed family of target subsets, uniformly over their overlaps. Restricting the walk to the labels in that family gives a finite transition matrix, and a stationary-flow identity determines its leading killing rate. Standard spectral and factorial-moment arguments then give the collection-time limits. This record contains the PDF preprint and matching editable LaTeX sources with build instructions. The results are analytic, with fixed r and s as n tends to infinity. AI assistance is disclosed in the manuscript. This is a preprint and has not undergone journal peer review.

Zenodo (CERN European Organization for Nuclear Research)
Stochastic processes and statistical mechanics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon