---
title: "Cutoff for bounded product-weight random transpositions"
date: 2026-09-08
version: "1.0.0-candidate"
doi: 10.5281/zenodo.22662125
pdf: https://github.com/ipitchford/bounded-product-transposition-cutoff/releases/download/v1.0.0-candidate/bounded-product-transposition-cutoff-1.0.0-candidate.pdf
repository: https://github.com/ipitchford/bounded-product-transposition-cutoff
archive: https://zenodo.org/records/22662125
license: CC0-1.0
status: unrefereed (internally replayed; not peer reviewed, not independently reproduced, not formally verified)
---

# Cutoff for bounded product-weight random transpositions

## Summary

Can unequal card-selection probabilities preserve the abrupt transition from an ordered deck to a random permutation? This candidate gives a proof that they do when every probability remains between fixed positive multiples of $1/n$. Each step draws two labels independently and swaps them; drawing the same label twice does nothing.

The result permits arbitrarily many probability classes. The mixing time has order $n\log n$, while the transition window has upper bound $O(n\log\log n)$. That window is a vanishing fraction of the mixing time. The result does not identify the exact transition location or an optimal window, and remains an unrefereed proof candidate.

## Summary for specialists

For any triangular array of probability vectors satisfying $c/n\le p_i^{(n)}\le C/n$, with fixed $0<c\le C<\infty$, the independent-pair transposition walk on $S_n$ has worst-start total-variation cutoff. Uniformly over such arrays, for fixed $0<\epsilon<1/2$,

$$t_P(\epsilon)=\Theta_{c,C,\epsilon}(n\log n).$$

The window from precision $1-\epsilon$ to precision $\epsilon$ has upper bound

$$O_{c,C,\epsilon}(n\log\log n).$$

An unordered distinct transposition has mass $2p_ip_j$ and the identity has mass $q=\sum_i p_i^2$. The theorem concerns only the product-weight branch of AIM-PROBABILITY-0050.

## Technical account

The key reference object is the uniform transposition square-gradient form $\Gamma_0$. Conjugation merely permutes its transposition directions, so Jensen's inequality gives $\Gamma_0T_\nu\le T_\nu\Gamma_0$ for any increment law $\nu$. Comparing the weighted form on both sides yields

$$\Gamma H_t\le (C/c)^2 H_t\Gamma.$$

Crucially, the constant is paid once for the entire time-$t$ law, not once per jump. A variance interpolation identity then supplies the local variance estimate needed by the information-differential method.

Modified logarithmic Sobolev comparison gives an $O(n\log n)$ upper bound. Untouched labels supply a matching lower order; the proof retains the positive covariance caused by their shared swap edge. Entropy and varentropy inequalities shrink the continuous-time transition to an $O(n\log\log n)$ window.

Hermon–Peres averaging transfers the window to two-consecutive-step averages. Since $q$ is only of order $1/n$, fixed laziness cannot be assumed. A separate binomial smoothing estimate shows successive discrete laws are $o(1)$ apart near the mixing scale and removes the averaging.

## Evidence, assurance and limitations

The written argument and its stated literature inputs support the theorem. Exact rational diagnostics on $S_2$ through $S_5$ check normalization, conjugation, a tagged-label projection, gradient inequalities and binomial identities. They include 3,648 gradient point checks and five deliberately invalid constructions that must be rejected, in normal and optimized Python. None of these finite tests certifies the asymptotic statement.

Five producer-coordinated editorial roles reviewed one frozen package. These are internal model-assisted reports, not unaffiliated specialist review or formal verification. Historical priority remains unconfirmed. The original Gao–Quastel full text was not retrieved; its normalized log-Sobolev input was corroborated in the inspected Pedrotti–Salez account.

Excluded conclusions include an explicit cutoff location, optimal window, limiting profile and the general nonproduct edge-weight problem.

## Relationship to earlier work

Nestoridi–Yan obtain a sharper location and order-$n$ window for two equally sized weight classes. This candidate trades that sharpness for arbitrary bounded vectors. Pedrotti–Salez supply the entropy method and, in their later work, general subcommutation machinery. The candidate contribution is the reference-form comparison and its application with a discrete-time bridge, not invention of the broader method.

## Who should care, and why

| Audience | Potential use | Required caution |
|---|---|---|
| Probability researchers | Inspect a comparison route for inhomogeneous shuffles. | Check the full proof and literature independently. |
| Sampling researchers | Understand qualitative mixing robustness under bounded selection bias. | The theorem is not an exact operational stopping rule. |
| Research agents | Reuse the proof decomposition and exact diagnostic controls. | Preserve the all-$n$ versus finite-test distinction. |

## Why the problem matters

Unequal selection rates destroy a symmetry available to the usual uniform shuffle. A reference-gradient comparison can retain enough structure to prove an abrupt transition without solving the full spectrum. That is a methodological possibility, not evidence of a measured computational speedup or a theorem about arbitrary perturbations.

## How to inspect or reproduce the recorded checks

Download and extract the versioned source ZIP. In its `research` directory, run `python3 verify.py` and `python3 -O verify.py`. Both outputs should match `verification.json`, including all five expected rejection controls. The checker uses only the standard library; the release records the tested local interpreter and separate Linux CI. Verify file hashes against `MANIFEST.sha256` before replay.

Read Sections 3–6 of the paper for the all-time comparison, entropy step and removal of averaging. A successful replay does not replace those arguments.

## The most valuable next projects

1. Obtain unaffiliated scrutiny of the complete probability argument and contribution-specific novelty.
2. Determine a cutoff location for general bounded arrays and improve the window bound.
3. Fix normalization and periodicity conventions before extending the argument to nonproduct rates.

## Who might contribute

Specialists in mixing times, entropy methods and interchange processes can assess the proof and its relationship to existing cutoff criteria. Independent software checks would add a different, finite assurance dimension.

## What is in the evidence package

The package contains the six-page PDF, TeX and accessible Markdown, exact checker and output, machine-readable claims, citation audit, review response, internal editorial reports, manifest and component licences. GitHub provides versioned source and CI; Zenodo supplies the archived version identity. Original prose and data are CC0-1.0, original code is MIT, and cited third-party works retain their own rights.




## Open directions for follow-up research

- Determine an explicit cutoff location for general bounded vectors.
- Improve the window bound and investigate limiting profiles.
- Fix normalization and periodicity conventions before extending to nonproduct rates.
- Independently assess the proof, contribution-specific novelty and priority.

## Research process, metrics and reusable methods

This is prospective process metadata under the Evidence Press operating model and research-metrics policy. It records the intended handoff, measured scope and claim boundary; it is not evidence that the method accelerated this work.

- Work ID: ep-work:bounded-product-transposition-cutoff
- Attempt and metric receipts: ep-attempt:bounded-product-transposition-cutoff-remaining-assurance-publication: published / positive; scope assurance-through-publication; target Reviewed and openly archived unrefereed cutoff candidate, provenance-bound media and guarded canonical publication.; active forecast 150 minutes (100-230); Fermi components Consolidated package and source checks: 1 x 30/45/65 minutes low/central/high (Short written proof and bounded attribution and exposition revisions; new PDF and checker controls.); Internal five-role review: 1 x 20/30/50 minutes low/central/high (One differentiated round.); Public archives and media: 1 x 30/45/65 minutes low/central/high (Existing publisher tools.); Gates and public readback: 1 x 20/30/50 minutes low/central/high (Two mandatory seal/deploy loops.); positive-signal/closure probabilities 0.95/0.85 within 300 active minutes; observed active-agent/human/compute/wait/blocked/rework minutes 31/unknown/unknown/0/0/2; cycles positive/negative/inconclusive 0/0/0; falsification gates 1; architectures tested/rejected 0/0; result target-closed; target reached true; forecast error -119 minutes; ratio 0.21; inside interval false; positive-signal/target-closure Brier scores 0.0025/0.0225; missing telemetry activeHumanMinutes: Human effort not instrumented.; computeMinutes: No complete inference or research compute meter; publication build time is not a substitute.; deduplicatedModelTokens: No authoritative task-local fork-aware runtime counter; inherited token events not summed.; uncachedInputTokens: No authoritative task-local uncached-input counter.; appended measurement corrections measurement.reworkMinutes -> metrics.outcome.reworkMinutes: 2 rounded minutes, an observed lower bound of 91.179 seconds; other unsegmented repair time excluded from subtotal. (reason: Opening zero is retained as intake snapshot; terminal field records two observed repair windows, not an exhaustive rework clock.); measurement.agentRuns -> metrics.outcome.agentRuns: Opening 1 remains; terminal total 6. (reason: Opening count retained; terminal total includes coordinator and five separate role reviewers.). Work ledger: https://evidencepress.org/api/work-ledger.json. Metrics policy: https://evidencepress.org/api/research-metrics-policy.json
- Intended aims: science
- Artifact roles: research-output, evidence-assessment
- Decision object: bound — Total-variation cutoff for arbitrary bounded product-weight transpositions. Scope: Independent pair draws, including identity moves, with fixed c/n and C/n bounds.
- Reusable methods: Structural compression (structural-compression); Explicit research-lineage reuse (research-lineage-reuse); Adversarial scientific controls (adversarial-controls); Assurance as a vector (assurance-vector); Agent-readable research objects (agent-readable-research-object). Registry: https://evidencepress.org/api/method-registry.json
- Targeted clocks: assurance, publication
- Semantic bridge: explicit — Conjugacy-invariant reference-gradient comparison yields all-time subcommutation; entropy controls the continuous window, then averaging and binomial smoothing give the original discrete-time theorem. Remaining risks: Written argument awaits unaffiliated specialist scrutiny.; No proof-assistant verification.; Historical priority remains bounded uncertainty..
- Human judgement gates: Check the entropy and discrete-time transfer arguments.; Assess contribution-specific novelty and significance.; Preserve product-only scope, candidate status and component rights.
- Next assurance action: Obtain unaffiliated probability-specialist scrutiny of the complete argument.
- Claim ceiling: Unrefereed proof candidate for the product-weight branch only. Producer finite checks and internal model-assisted editorial review are not independent reproduction, unaffiliated specialist review or formal verification. No explicit cutoff location, optimal window, limiting profile, nonproduct resolution or historical priority is claimed.
- Aim-scoped impact evidence:
  - science: NO_IMPACT_EVIDENCE — Inspectable mathematical proof candidate in Producer-coordinated publication; design none; comparator No matched comparator.; estimand No speed or impact effect estimated.; no real-world effect evidence asserted
- Parent handoffs: depends-on-claim https://arxiv.org/abs/2501.13079v1; inherited claim: Normalized log-Sobolev and information-differential inputs.; inherited ceiling: Published literature input is not validation of this application.



## Verification status

Unrefereed proof candidate for the product-weight branch only. Producer finite checks and internal model-assisted editorial review are not independent reproduction, unaffiliated specialist review or formal verification. No explicit cutoff location, optimal window, limiting profile, nonproduct resolution or historical priority is claimed.

## References

1. AIM Markov chain mixing times workshop (2016), originating problem context. <https://aimath.org/pastworkshops/markovmixing.html>
2. Nestoridi–Yan (2024), Cutoff for the biased random transposition shuffle: sharper two-class comparator. <https://arxiv.org/abs/2409.16387v1>
3. Pedrotti–Salez (2025), A new cutoff criterion for non-negatively curved chains: entropy method and normalized inputs. <https://arxiv.org/abs/2501.13079v1>
4. Pedrotti–Salez (2026), The local product condition implies cutoff: general subcommutation context. <https://arxiv.org/abs/2607.05345v2>
5. Hermon–Peres (2017), The power of averaging at two consecutive time steps. <https://doi.org/10.1214/16-AIHP782>