pith. machine review for the scientific record. sign in

arxiv: 2604.09933 · v1 · submitted 2026-04-10 · 🧮 math.PR · math.CO

Recognition: 2 theorem links

· Lean Theorem

Explicit Cutoff Profiles for Colored Top-m-to-Random Shuffles

Ivan Z. Feng
Authors on Pith no claims yet

Pith reviewed 2026-05-10 16:25 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords colored shufflestop-m-to-randomwreath productmixing time cutoffPoisson limittotal variation distanceseparation distancelikelihood ratio
0
0 comments X

The pith

The p-colored top-m-to-random shuffle on the wreath product has its mixing cutoff at k = floor(n/m (log n + c)), where the number of never-chosen labels converges in law to Poisson(e^{-c}).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives exact formulas for separation distance and L^∞ norm, plus one-dimensional formulas for total variation, L^q norms, chi-squared, and relative entropy for these shuffles. It achieves this by applying the Nakano-Sadahiro-Sakurai basis elements to obtain exact nested-set occupancy mixtures, reducing the likelihood ratio to one statistic L_p. At the time k = floor(n/m (log n + c)), the count of labels never chosen converges in distribution to a Poisson random variable with mean e^{-c}. This limit supplies the explicit total-variation profile f_p(c) along with the corresponding profiles for the other distances. Special cases include recovery of the colored top-to-random results when m=1 and the Diaconis-Fill-Pitman profile when p=1.

Core claim

Using the Nakano-Sadahiro-Sakurai basis elements B_m, exact nested-set occupancy mixtures are obtained on the wreath product G_{n,p} = C_p wr S_n, allowing the likelihood ratio to reduce to the single statistic L_p. At k = floor(n/m (log n + c)), the number of never-chosen labels converges in law to Poisson(e^{-c}), which determines the total-variation profile f_p(c), the separation profile, and the profiles for L^q(U), L^∞(U), chi-squared, and relative entropy.

What carries the argument

The Nakano-Sadahiro-Sakurai basis elements B_m, which produce exact nested-set occupancy mixtures on the wreath product and reduce the likelihood ratio to the statistic L_p.

If this is right

  • The separation distance and L^∞(U) distance admit exact formulas for all times.
  • One-dimensional formulas exist for total variation, L^q(U) for q finite, chi-squared, and relative entropy.
  • The total variation profile is the function f_p(c) coming from the Poisson(e^{-c}) limit.
  • The results specialize to colored top-to-random when m equals 1.
  • When p equals 1 the total-variation profile reduces to the Diaconis-Fill-Pitman profile.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The Poisson convergence implies that the mixing occurs in a window of width proportional to n/m around the main term (n/m) log n.
  • Similar Poisson limits may hold for variants of the shuffle or on other wreath products with different color structures.
  • Direct computation of the never-chosen label count for moderate n and p could numerically verify the convergence rate to the Poisson law.
  • The single-statistic reduction suggests that the mixing behavior is dominated by the coupon-collector aspect of selecting new labels.

Load-bearing premise

The Nakano-Sadahiro-Sakurai basis elements yield exact nested-set occupancy mixtures on the wreath product that allow the likelihood ratio to reduce exactly to the single statistic L_p.

What would settle it

For large n, if the number of never-chosen labels at time floor(n/m (log n + c)) does not converge in distribution to Poisson with mean e^{-c}, or if the total variation distance does not follow the predicted profile f_p(c).

read the original abstract

We study $p$-colored top-$m$-to-random on the wreath product $G_{n,p}=C_p\wr S_n$, with $m$ fixed. Using the Nakano-Sadahiro-Sakurai basis elements $B_m$, we obtain exact nested-set occupancy mixtures and reduce the likelihood ratio to the single statistic $L_p$. This yields exact formulas for separation and $L^\infty(U)$, and exact one-dimensional formulas for total variation, $L^q(U)$ ($1\le q<\infty$), $\chi^2$, and relative entropy. At $k=\Bigl\lfloor \frac{n}{m}(\log n+c)\Bigr\rfloor$, the number of never-chosen labels converges in law to $\mathrm{Poisson}(e^{-c})$, giving the total-variation profile $f_p(c)$, the separation profile, and the corresponding $L^q(U)$, $L^\infty(U)$, $\chi^2$, and relative-entropy profiles. For $m=1$ we recover colored top-to-random; for $p=1$, the total-variation profile reduces to the Diaconis-Fill-Pitman profile.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper studies the p-colored top-m-to-random shuffle on the wreath product G_{n,p}=C_p wr S_n with m fixed. Using the Nakano-Sadahiro-Sakurai basis elements B_m, it derives exact nested-set occupancy mixtures on G_{n,p}, reduces the likelihood ratio to the single statistic L_p, and obtains exact formulas for separation distance and L^∞(U) together with one-dimensional formulas for total variation, L^q(U) (1≤q<∞), χ², and relative entropy. At the time k=⌊(n/m)(log n + c)⌋ the number of never-chosen labels converges in law to Poisson(e^{-c}), which determines the total-variation profile f_p(c) and the corresponding profiles for separation, L^q, L^∞, χ², and relative entropy. The constructions recover the Diaconis-Fill-Pitman profile when p=1 and the colored top-to-random case when m=1.

Significance. If the derivations hold, the work supplies a complete, explicit set of cutoff profiles for a natural family of generalized shuffles on wreath products. The recovery of the known Diaconis-Fill-Pitman and colored top-to-random results in the special cases supplies independent verification of the key technical step and strengthens the contribution to the literature on mixing times and cutoff phenomena for random walks on groups.

major comments (1)
  1. [Derivation following introduction of B_m] The reduction of the likelihood ratio to the single statistic L_p (stated in the abstract) is load-bearing for all profile formulas. Please supply the explicit definition of L_p together with the precise argument showing that the Nakano-Sadahiro-Sakurai basis B_m produces exact nested-set occupancy mixtures on the wreath product G_{n,p} without additional error terms.
minor comments (2)
  1. [Introduction] The notation G_{n,p} and the wreath-product action should be recalled explicitly in the first section for readers who may not have the colored-permutation representation immediately in mind.
  2. [Final section on special cases] Add a short table or list comparing the recovered special cases (p=1 and m=1) with the corresponding statements in the cited literature.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, the positive summary, and the recommendation of minor revision. The single major comment is addressed below; we agree that greater explicitness on the key reduction will improve the manuscript.

read point-by-point responses

  1. Referee: [Derivation following introduction of B_m] The reduction of the likelihood ratio to the single statistic L_p (stated in the abstract) is load-bearing for all profile formulas. Please supply the explicit definition of L_p together with the precise argument showing that the Nakano-Sadahiro-Sakurai basis B_m produces exact nested-set occupancy mixtures on the wreath product G_{n,p} without additional error terms.

    Authors: We agree that the reduction to L_p is central and that the current exposition would benefit from a more self-contained presentation. In the revised manuscript we will insert, immediately after the introduction of the Nakano-Sadahiro-Sakurai basis elements B_m, a new subsection that (i) gives the explicit definition of the statistic L_p as the p-tuple of occupancy counts for the nested sets under the colored top-m-to-random walk, and (ii) supplies the precise argument that the basis produces exact nested-set occupancy mixtures on G_{n,p}. The argument proceeds by verifying that the transition operator is diagonalized exactly by the B_m elements in the wreath-product representation ring, so that the resulting occupancy probabilities are products of independent geometric distributions with no remainder terms. This expanded subsection will also record the direct verification that the likelihood ratio depends only on L_p, thereby making the subsequent profile derivations fully rigorous and self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via external basis and special-case recovery

full rationale

The paper's core reduction uses the externally cited Nakano-Sadahiro-Sakurai basis B_m to obtain exact nested-set occupancy mixtures on the wreath product, collapsing the likelihood ratio to L_p and producing the Poisson(e^{-c}) limit for never-chosen labels at the stated cutoff time. This is independently supported by explicit recovery of the Diaconis-Fill-Pitman total-variation profile when p=1 and the colored top-to-random case when m=1. No step equates a claimed prediction to a fitted input by construction, invokes a self-citation as the sole justification for a uniqueness claim, or renames a known empirical pattern as a new derivation. The central formulas for TV, separation, L^q, chi^2, and entropy profiles therefore rest on verifiable external structure rather than internal tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on representation-theoretic tools from prior work and standard probabilistic convergence arguments for occupancy statistics; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • domain assumption The Nakano-Sadahiro-Sakurai basis elements B_m exist and allow exact nested-set occupancy mixtures on the wreath product
    Invoked to obtain exact formulas for the mixtures and reduce the likelihood ratio to L_p
  • domain assumption The likelihood ratio reduces to the single statistic L_p
    This reduction is used to yield exact formulas for separation, L^∞(U), and one-dimensional formulas for other distances

pith-pipeline@v0.9.0 · 5502 in / 1566 out tokens · 88256 ms · 2026-05-10T16:25:41.376796+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 12 canonical work pages

  1. [1]

    D. J. Aldous, Random walks on finite groups and rapidly mixing Markov chains, inS´ eminaire de Probabilit´ es XVII 1981/82, Lecture Notes in Mathematics, vol. 986, Springer, Berlin, 1983, pp. 243–297

    1981

  2. [2]

    C. A. Athanasiadis and P. Diaconis, Functions of random walks on hyperplane arrangements,Adv. in Appl. Math.45(2010), 410–437. (Also available as arXiv:0912.1686.)

    work page arXiv 2010

  3. [3]

    Betken and C

    C. Betken and C. Th¨ ale, Approaching the coupon collector’s problem with group drawings via Stein’s method,J. Appl. Prob.60 (2023), no. 4, 1352–1366. DOI: 10.1017/jpr.2023.6

    work page doi:10.1017/jpr.2023.6 2023

  4. [4]

    Bj¨ orner, Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries, InBuilding Bridges, M

    A. Bj¨ orner, Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries, InBuilding Bridges, M. Gr¨ otschel, G. O. H. Katona, and G. S´ agi, eds., Bolyai Society Mathematical Studies, vol. 19, Springer, Berlin, Heidelberg, 2008, pp. 165–203. DOI: 10.1007/978-3-540-85221-6 5

    work page doi:10.1007/978-3-540-85221-6 2008

  5. [5]

    K. S. Brown, Semigroups, rings, and Markov chains,J. Theoret. Probab.13(2000), 871–938

    2000

  6. [6]

    K. S. Brown and P. Diaconis, Random walks and hyperplane arrangements,Ann. Probab.26(1998), no. 4, 1813–1854. DOI: 10.1214/aop/1022855884

    work page doi:10.1214/aop/1022855884 1998

  7. [7]

    Diaconis, The cutoff phenomenon in finite Markov chains,Proc

    P. Diaconis, The cutoff phenomenon in finite Markov chains,Proc. Natl. Acad. Sci. USA93(1996), 1659–1664

    1996

  8. [8]

    Diaconis, J

    P. Diaconis, J. A. Fill, and J. Pitman, Analysis of top to random shuffles,Combinatorics, Probability and Computing1(1992), 135–155

    1992

  9. [9]

    Diaconis and J

    P. Diaconis and J. Fulman,The Mathematics of Shuffling Cards, American Mathematical Society, Providence, RI, 2023

    2023

  10. [10]

    Diaconis and L

    P. Diaconis and L. Saloff-Coste, Separation cut-offs for birth and death chains,Ann. Appl. Probab.16(2006), no. 4, 2098–2122. DOI: 10.1214/105051606000000501

    work page doi:10.1214/105051606000000501 2006

  11. [11]

    A. L. Gibbs and F. E. Su, On choosing and bounding probability metrics,International Statistical Review70(2002), no. 3, 419–435

    2002

  12. [12]

    Liese and I

    F. Liese and I. Vajda, On divergences and informations in statistics and information theory,IEEE Transactions on Information Theory52(2006), no. 10, 4394–4412

    2006

  13. [13]

    D. A. Levin, Y. Peres, and E. L. Wilmer,Markov Chains and Mixing Times, 2nd ed., American Mathematical Society, Providence, RI, 2017

    2017

  14. [14]

    Nakagawa and F

    Y. Nakagawa and F. Nakano, Tsetlin library onp-colored permutations andq-analogue,Math. J. Okayama Univ.67(2025), 133–147

    2025

  15. [15]

    Nakano, T

    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

    work page doi:10.1016/j.dam.2023.06.037 2023

  16. [16]

    Nestoridi, Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement,Probability Theory and Related Fields174(2019), 929–943

    K. Nestoridi, Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement,Probability Theory and Related Fields174(2019), 929–943. DOI: 10.1007/s00440-018-0872-7

    work page doi:10.1007/s00440-018-0872-7 2019

  17. [17]

    Nishiyama and I

    T. Nishiyama and I. Sason, On relations between the relative entropy andχ 2-divergence, generalizations and applications,Entropy 22(2020), no. 5, 563. DOI: 10.3390/e22050563

    work page doi:10.3390/e22050563 2020

  18. [18]

    C. Y. Amy Pang, Markov chains from descent operators on combinatorial Hopf algebras, Preprint, arXiv:1609.04312, 2016. DOI: 10.48550/arXiv.1609.04312

    work page doi:10.48550/arxiv.1609.04312 2016

  19. [19]

    Schilling and N

    J. Schilling and N. Henze, Two Poisson limit theorems for the coupon collector’s problem with group drawings,J. Appl. Prob.58 (2021), 966–977. DOI: 10.1017/jpr.2021.15

    work page doi:10.1017/jpr.2021.15 2021

  20. [20]

    Stadje, The collector’s problem with group drawings,Advances in Applied Probability22(1990), 866–882

    W. Stadje, The collector’s problem with group drawings,Advances in Applied Probability22(1990), 866–882

    1990

  21. [21]

    Stark, Information loss in top-to-random shuffling,Combinatorics, Probability and Computing11(2002), no

    D. Stark, Information loss in top-to-random shuffling,Combinatorics, Probability and Computing11(2002), no. 6, 607–627. DOI: 10.1017/S0963548302005382

    work page doi:10.1017/s0963548302005382 2002

  22. [22]

    IEEE Transactions on Information Theory , author =

    T. van Erven and P. Harremo¨ es, R´ enyi divergence and Kullback–Leibler divergence,IEEE Transactions on Information Theory 60(2014), no. 7, 3797–3820. DOI: 10.1109/TIT.2014.2320500. Department of Mathematics, University of Southern California, Los Angeles, CA 90089-2532, USA Email address:ifeng@usc.edu URL:https://dornsife.usc.edu/ivan/

    work page doi:10.1109/tit.2014.2320500 2014