pith. sign in

arxiv: 2604.09933 · v2 · pith:R4XT7FJNnew · submitted 2026-04-10 · 🧮 math.PR · math.CO

Explicit cutoff profiles for colored top-m-to-random shuffles

Ivan Z. Feng This is my paper

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 in the associated $m$-subset occupancy model 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. For the reversed chain, we also identify optimal strong stationary times whose tail probabilities are exactly the separation distances.

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.