Cutoff profiles for colored top-m-to-random shuffles with growing block size
Pith reviewed 2026-06-30 02:02 UTC · model grok-4.3
The pith
The number of untouched labels converges in distribution to Poisson(λ) when block size grows, yielding explicit separation distances to uniform.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
If λ_n → λ ∈ (0,∞) and b_n → ∞, then E_{k_n}^{(m_n)} converges in distribution to Poisson(λ). Consequently the separation distance from (Q_{n,p}^{(m_n)})^{*k_n} to U_{n,p} tends to 1−e^{−λ}(1+λ) for p=1 and to 1−e^{−λ} for p≥2.
What carries the argument
The random variable E_{k_n}^{(m_n)} counting untouched labels after k_n uniform m_n-subset draws, whose Poisson limit is fed into the exact nested-set reduction.
If this is right
- Separation distance tends to 1−e^{−λ}(1+λ) for the one-color case p=1.
- Separation distance tends to 1−e^{−λ} for p≥2.
- The same Poisson limit produces total-variation and integrated-likelihood-ratio profiles via the nested-set reduction.
- The criterion covers small blocks, proportional blocks, and near-full blocks alike.
Where Pith is reading between the lines
- Analogous Poisson limits may govern untouched-element counts in other growing-parameter random walks on symmetric or wreath-product groups.
- The mixing window is governed by the scale at which expected untouched labels reach order one, regardless of how m_n grows provided b_n diverges.
- The Poisson approximation could be checked for other metrics such as L^2 or chi-squared distance to see whether separation captures the sharpest behavior.
Load-bearing premise
The exact nested-set reduction for colored top-m-to-random shuffles stays valid without extra error terms when the block size m_n grows with n.
What would settle it
A counterexample sequence where λ_n → λ > 0, b_n → ∞, yet the distribution of E_{k_n}^{(m_n)} fails to approach Poisson(λ) would falsify the claim.
read the original abstract
We study the $p$-colored top-$m$-to-random shuffle on $C_p\wr S_n$ when the block size $m=m_n$ grows with $n$. Let $E_{k_n}^{(m_n)}$ be the number of labels never touched after $k_n$ independent uniform $m_n$-subset draws, and set $b_n=n-m_n$, $q_n=b_n/n$, and $\lambda_n=nq_n^{k_n}$. We prove that if $\lambda_n\to\lambda\in(0,\infty)$ and $b_n\to\infty$, then $E_{k_n}^{(m_n)}\Rightarrow\mathrm{Poisson}(\lambda)$. Combining this with the exact nested-set reduction for colored top-$m$-to-random shuffles, we obtain growing-block total variation, separation, and integrated likelihood-ratio profiles. In particular, if $Q_{n,p}^{(m_n)}$ is the one-step law and $U_{n,p}$ is uniform on $C_p\wr S_n$, then the separation distance from $(Q_{n,p}^{(m_n)})^{*k_n}$ to $U_{n,p}$ tends to $1-e^{-\lambda}(1+\lambda)$ for $p=1$ and to $1-e^{-\lambda}$ for $p\ge2$. The criterion applies to small blocks, proportional blocks, and near-full blocks.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that for the p-colored top-m-to-random shuffle on the wreath product C_p wr S_n with growing block size m_n, if λ_n = n q_n^{k_n} → λ ∈ (0,∞) and b_n = n - m_n → ∞, then the number of untouched labels E_{k_n}^{(m_n)} converges in distribution to Poisson(λ). Combining this Poisson limit with the exact nested-set reduction yields explicit total variation, separation, and integrated likelihood-ratio cutoff profiles; in particular the separation distance from (Q_{n,p}^{(m_n)})^{*k_n} to U_{n,p} tends to 1−e^{-λ}(1+λ) for p=1 and to 1−e^{-λ} for p≥2. The criterion is stated to apply across small, proportional, and near-full block regimes.
Significance. If the claims hold, the work extends fixed-block cutoff-profile results to the growing-m_n setting and supplies explicit, parameter-free distance limits once the Poisson limit is established. The Poisson convergence itself is a clean technical contribution, and the algebraic substitution into the nested-set reduction produces falsifiable predictions for the separation distance in multiple regimes without additional fitting.
major comments (2)
- [abstract (combination step) and the section deriving the distance profiles from E] The separation-distance limits are obtained from the Poisson convergence solely by algebraic substitution into the nested-set reduction (abstract, final paragraph). The reduction is invoked as exact for growing m_n, yet the identity between the untouched-nested-set probability and the separation distance was previously derived only for fixed m; the manuscript must supply an explicit verification or uniformity argument confirming that the one-step transition probabilities on the colored wreath product preserve the exact identity when b_n → ∞ (including proportional and near-full blocks). This is load-bearing for the distance-profile claims.
- [the section proving the Poisson convergence] The Poisson limit E_{k_n}^{(m_n)} ⇒ Poisson(λ) is stated under the joint conditions λ_n → λ and b_n → ∞. The proof must be checked for uniformity of the convergence (or error bounds) across the three regimes (small blocks, m_n ~ c n, near-full blocks) to ensure the subsequent distance limits remain valid without regime-specific corrections.
minor comments (1)
- [abstract] Clarify whether the notation q_n = b_n / n is introduced before its first use in the scaling λ_n = n q_n^{k_n}.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments on our manuscript. We respond point-by-point to the major comments below.
read point-by-point responses
-
Referee: [abstract (combination step) and the section deriving the distance profiles from E] The separation-distance limits are obtained from the Poisson convergence solely by algebraic substitution into the nested-set reduction (abstract, final paragraph). The reduction is invoked as exact for growing m_n, yet the identity between the untouched-nested-set probability and the separation distance was previously derived only for fixed m; the manuscript must supply an explicit verification or uniformity argument confirming that the one-step transition probabilities on the colored wreath product preserve the exact identity when b_n → ∞ (including proportional and near-full blocks). This is load-bearing for the distance-profile claims.
Authors: The nested-set reduction is an exact algebraic identity derived from the form of the one-step transition operator on C_p wr S_n and the definition of separation distance; it equates the distance to the probability that a certain collection of nested sets contains at least one untouched label. This identity depends only on the per-step untouched probability q_n = b_n/n and holds verbatim for any m (fixed or growing) because the transition probabilities are defined identically. We will insert a short explicit verification (one paragraph) in the revised manuscript confirming that the identity persists without modification when m = m_n and b_n → ∞, covering all three regimes. revision: yes
-
Referee: [the section proving the Poisson convergence] The Poisson limit E_{k_n}^{(m_n)} ⇒ Poisson(λ) is stated under the joint conditions λ_n → λ and b_n → ∞. The proof must be checked for uniformity of the convergence (or error bounds) across the three regimes (small blocks, m_n ~ c n, near-full blocks) to ensure the subsequent distance limits remain valid without regime-specific corrections.
Authors: The proof proceeds via moment matching for the indicators of untouched labels, with all error terms (from the second-moment calculations and the general Poisson approximation lemma employed) controlled uniformly by the hypotheses λ_n → λ and b_n → ∞ alone. The estimates involve only expansions in powers of q_n and 1/n that remain valid independently of the ratio m_n/n. We will add a brief remark at the end of the Poisson-convergence section stating this uniformity explicitly across the small-block, proportional-block, and near-full-block regimes. revision: yes
Circularity Check
Derivation self-contained: Poisson limit proved directly under explicit scalings; separation profiles obtained by substitution into cited exact reduction with no reduction to inputs by construction
full rationale
The paper first proves E_{k_n}^{(m_n)} ⇒ Poisson(λ) when λ_n → λ ∈ (0,∞) and b_n → ∞ as an independent convergence statement. It then combines this limit with the exact nested-set reduction (invoked as a prior identity for the colored top-m-to-random model) to obtain the separation-distance limits via direct algebraic substitution. No step equates a derived quantity back to a fitted parameter, re-derives the reduction inside the paper, or relies on a self-citation chain whose validity is presupposed by the target result. The derivation chain therefore remains self-contained against external benchmarks and does not exhibit any of the enumerated circularity patterns.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The nested-set reduction expressing total-variation, separation, and integrated-likelihood-ratio distances exactly in terms of the untouched-label count E holds without remainder terms when m_n grows.
Reference graph
Works this paper leans on
-
[1]
Asymptotic Results for Uniform Group Drawing in the Coupon Collector's Problem
D. Berend and T. Sher,Asymptotic results for uniform group drawing in the coupon collector’s problem, Stochastic Models (2026), arXiv:2605.06953. DOI: 10.1080/15326349.2026.2669925
work page internal anchor Pith review Pith/arXiv arXiv doi:10.1080/15326349.2026.2669925 2026
-
[2]
C. Betken and C. Thäle,Approaching the coupon collector’s problem with group drawings via Stein’s method, Journal of Applied Probability60(2023), no. 4, 1352–1366. DOI: 10.1017/jpr.2023.6
-
[3]
S. Chatterjee, P. Diaconis, and E. Meckes,Exchangeable pairs and Poisson approximation, Probability Surveys2 (2005), 64–106. DOI: 10.1214/154957805100000096
-
[4]
P. Diaconis, J. A. Fill, and J. Pitman,Analysis of top to random shuffles, Combinatorics, Probability and Computing1(1992), no. 2, 135–155. DOI: 10.1017/S0963548300000158
-
[5]
I. Z. Feng,Explicit cutoff profiles for colored top-m-to-random shuffles, arXiv:2604.09933, 2026
work page internal anchor Pith review Pith/arXiv arXiv 2026
-
[6]
F. Nakano, T. Sadahiro, and T. Sakurai,Top to random shuffles on colored permutations, Discrete Applied Mathematics339(2023), 336–348. DOI: 10.1016/j.dam.2023.06.037
-
[7]
J. Schilling and N. Henze,Two Poisson limit theorems for the coupon collector’s problem with group drawings, Journal of Applied Probability58(2021), no. 4, 966–977. DOI: 10.1017/jpr.2021.15
-
[8]
Stadje,The collector’s problem with group drawings, Advances in Applied Probability22(1990), no
W. Stadje,The collector’s problem with group drawings, Advances in Applied Probability22(1990), no. 4, 866–882. DOI: 10.2307/1427566. Department of Mathematics, University of Southern California, Los Angeles, CA 90089, USA Email address:ifeng@usc.edu URL:https://dornsife.usc.edu/ivan/
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.