--- title: "Random transpositions on Dyck paths mix in order n log n" date: 2026-09-06 version: "0.1.0-candidate" doi: 10.5281/zenodo.22556925 pdf: https://github.com/ipitchford/dyck-transpositions-n-log-n/releases/download/v0.1.0-candidate/dyck-transpositions-n-log-n-0.1.0-candidate.pdf repository: https://github.com/ipitchford/dyck-transpositions-n-log-n archive: https://zenodo.org/records/22556925 license: CC0-1.0 status: unrefereed (internally replayed; not peer reviewed, not independently reproduced, not formally verified) --- # Random transpositions on Dyck paths mix in order n log n ## Summary How long does a constrained random shuffle take to forget its starting point? A Dyck path goes up and down without crossing below ground, ending where it started. Here a step of the shuffle picks two positions independently at random and swaps them, unless that would make the path invalid. This unrefereed proof candidate gives matching upper and lower orders: for a path of length $2n$, the worst-start mixing time is $\Theta(n\log n)$. The statement counts every proposal, including rejected ones. Its proof is analytic; the accompanying finite computations are checks, not a substitute for an argument valid at every size. ## Summary for specialists Let $K$ choose an ordered pair $(i,j)$ independently uniformly from $[2n]^2$, transpose the corresponding letters when the resulting word is Dyck, and hold otherwise. Its stationary law $\pi$ is uniform on $C_n$ Dyck words. The candidate establishes an absolute $A<\infty$ such that $$\operatorname{Ent}_\pi(Kf)\leq\left(1-\frac{1}{24An}\right)\operatorname{Ent}_\pi(f).$$ Consequently $t_{\mathrm{mix}}(1/4)=\Theta(n\log n)$, with lower bound $(n/2)\log n-O(n)$. No cutoff or sharp leading upper constant is asserted. ## Technical account Condition on heights at two separated path positions. Each conditioned half is a uniform basis of a truncated prefix matroid. The established matroid deletion-entropy inequality controls the remaining conditional entropy using global deletion and addition fibres larger than $n/3$. The information shared by the two heights is controlled separately. Exact ballot formulas give a one-dimensional height channel. A uniform classical log-Sobolev bound follows from discrete Hardy estimates, including the bottom, intermediate and rare upper-tail regimes. Discrete hypercontractivity across the changing height marginals then yields a two-cut entropy inequality through the established Brascamp–Lieb/entropy duality. These height-channel positions are spatial indices within one path, not steps of the mixing walk. Finally a retained-fibre heat bath satisfies an exact constant-factor stochastic decomposition with $K$. This returns the result to the original proposal clock. A midpoint-height drift argument supplies the matching lower order. ## Evidence, assurance and limitations The package contains a standalone paper, accessible proof, expanded route notes, seven finite producer replay stages and deliberately corrupted-input controls. Bounded computations check kernels, labelled-fibre embeddings, height identities, drift and moments. They do not certify the all-size Hardy inequality or the universal theorem. The supplied review was actioned, and the release records its internal editorial process. Producer-coordinated AI review is not external peer review, independent reproduction or formal verification. The literature search is bounded; novelty and priority remain unestablished. No fastest general Dyck sampler, arbitrary Catalan-chain result or measured computational speed-up is claimed. ## Relationship to earlier work Cohen, Tetali and Yeliussizov provide the lattice-path matroid context. Cryan, Guo and Mousa supply the deletion-entropy input; Barthe and Roberto provide the entropy Hardy framework. Carlen and Cordero-Erausquin establish the generic entropy duality used here. The general down-up theorem of Anari and colleagues uses a different kernel: its legal exchange probability depends on the number of completions of a deletion core. The Burnside sampler studied by Feng and Paguyo is different again. Neither result is silently transferred to this rejection walk. The candidate's claimed contribution is the Dyck-specific two-cut construction and its constant-cost return to the original chain. ## Who should care, and why | Audience | Potential use | Required caution | | --- | --- | --- | | Probability researchers | Inspect a two-cut entropy route for constrained sampling. | Check the all-size inequalities, not just finite replay. | | Algorithm researchers | Compare distinct update kernels and proposal clocks. | Mixing steps are not implementation time or sampler optimality. | | Research-tool builders | Reuse exact finite checks and preserved failed routes. | Internal implementation diversity is not independent validation. | | Interested readers | See how local constraints affect random shuffling. | This remains an unrefereed candidate. | ## Why the problem matters The constraint is simple, but rejecting invalid moves changes the dynamics. Determining the correct mixing order tests whether a convenient alternative sampling rule actually describes the original process. The proof also offers an inspectable example of combining local conditional-entropy estimates with control of the information left in a coarse observation. ## How to inspect or reproduce the recorded checks Download the versioned evidence ZIP and extract it into a fresh directory. With Python 3.10 or later, run: ```sh python3 full_replay.py python3 release_checks.py ``` The standard library suffices. Expected results are `PASS_FINITE_REPLAY` and `PASS_NEGATIVE_CONTROLS`. Optimized Python execution is rejected because assertions are part of the finite checks. Replay verifies the manifest before regenerating some runtime-bearing receipts. Read the analytic proof separately. ## The most valuable next projects 1. Obtain unaffiliated specialist scrutiny of the uniform Hardy estimates and changing-marginal norm composition. 2. Reconstruct the labelled-fibre embedding and comparison independently. 3. Make the upper constant explicit before studying sharp asymptotics or cutoff. 4. Test extensions as new claims, without assuming every Catalan model inherits the same entropy structure. ## Who might contribute Expertise in logarithmic Sobolev inequalities, matroid sampling and discrete functional inequalities would be especially useful. These are suggested areas of scrutiny, not claims of endorsement or an outreach programme. ## What is in the evidence package The PDF, TeX, bibliography and accessible proof state the current candidate. The code and JSON records expose finite corroboration and historical obstructions. Status, claims, provenance, licences, review responses and manifests distinguish what is asserted from what was checked. Historical notes retain their original arguments behind explicit status banners. The immutable GitHub release and Zenodo record identify the archived version. ## Open directions for follow-up research - Obtain unaffiliated specialist scrutiny of the uniform Hardy and channel-composition arguments. - Independently reconstruct the retained-fibre embedding and original-clock comparison. - Derive an explicit upper constant and investigate sharp asymptotics or cutoff as new work. - Assess extensions without transferring the result to different Catalan kernels by analogy alone. ## 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:dyck-transpositions-n-log-n - Attempt and metric receipts: ep-attempt:dyck-transpositions-n-log-n-assurance-publication: published / positive; scope assurance-through-publication; target Revised proof and finite replay, five-role internal editorial acceptance, byte-identical GitHub and Zenodo assets, standard media and first canonical guarded public readback.; active forecast 150 minutes (100-210); Fermi components Package and PDF checks: 1 x 25/35/50 minutes low/central/high (Existing proof, seven finite stages.); Five-role editorial review: 1 x 20/30/45 minutes low/central/high (One bounded round.); Archives, page and media: 1 x 35/50/65 minutes low/central/high (Established scripts and authenticated services.); Guarded public readback: 1 x 20/35/50 minutes low/central/high (Composite gates and CI.); positive-signal/closure probabilities 0.95/0.85 within 240 active minutes; observed active-agent/human/compute/wait/blocked/rework minutes 9/unknown/unknown/4/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 -141 minutes; ratio 0.06; inside interval false; positive-signal/target-closure Brier scores 0.0025/0.0225; missing telemetry activeHumanMinutes: No contemporaneous human active-time telemetry.; computeMinutes: No complete scoped substantive-computation timing; normal builds and CI are not research compute.; appended measurement corrections measurement.agentRuns -> metrics.outcome.agentRuns: Terminal runtime receipt records 6; the earlier snapshot is preserved. (reason: The intake snapshot predates completed reviewers and media repair.); measurement.reworkMinutes -> metrics.outcome.reworkMinutes: Terminal runtime receipt records 2; the earlier snapshot is preserved. (reason: The intake snapshot predates completed reviewers and media repair.); assuranceEndpoint.missingnessReason: Canonical publication is now established by the separate public-release milestone; the earlier assurance timestamp and external-assurance limitations remain unchanged. (reason: The historical assessment explicitly marked canonical publication pending.). 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, communication - Decision object: bound — Analytic two-cut entropy factorization and exact constant-factor return to the original rejection chain. Scope: Uniform Dyck words of length 2n, ordered independent-coordinate proposals, rejection holds, worst-start total variation at 1/4. - Reusable methods: Structural compression (structural-compression); Exact regime stitching (regime-stitching); Productive failure and stop receipts (productive-failure); 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 — Ballot height laws, conditional matroid fibres and stochastic-mixture comparison refer to the same original kernel; spatial channel positions are not mixing-clock steps. Remaining risks: All-size analytic estimates remain subject to specialist scrutiny.; Finite computations cannot establish the universal theorem.; Novelty and priority search is bounded.; No practical runtime or sampler-optimality claim.. - Human judgement gates: Check uniformity over rare heights and all sizes.; Check fibre entropy normalization and original-clock comparison.; Separate imported theorems from the proposed construction.; Preserve Anonymous authorship, component rights and assurance boundaries. - Next assurance action: Seek unaffiliated analytic and computational scrutiny; sharp constants and extensions remain new work. - Claim ceiling: Unrefereed analytic proof candidate for the original length-2n ordered independent-coordinate Dyck rejection walk. No cutoff, sharp upper constant, numerical burn-in guarantee, computational-runtime bound, sampler optimality, external peer review, formal verification or priority clearance. - Aim-scoped impact evidence: - science: NO_IMPACT_EVIDENCE — Inspectable original-clock mixing proof candidate in Producer-coordinated mathematical publication; design none; comparator No matched workflow comparator.; estimand No discovery-speed, effort, reuse or impact effect estimated.; no real-world effect evidence asserted - Parent handoffs: depends-on-claim https://arxiv.org/abs/1903.06081v3; inherited claim: Matroid deletion-entropy contraction, Lemma 11.; inherited ceiling: Established external input; not validation of this candidate application. ## Verification status Unrefereed analytic proof candidate for the original length-2n ordered independent-coordinate Dyck rejection walk. No cutoff, sharp upper constant, numerical burn-in guarantee, computational-runtime bound, sampler optimality, external peer review, formal verification or priority clearance. ## References 1. Cohen, Tetali and Yeliussizov (2015). Lattice Path Matroids: Negative Correlation and Fast Mixing. 2. Cryan, Guo and Mousa (2021). Modified log-Sobolev inequalities for strongly log-concave distributions. Deletion entropy input. 3. Barthe and Roberto (2003). Sobolev inequalities for probability measures on the real line. Hardy framework. 4. Carlen and Cordero-Erausquin (2009). Subadditivity of the entropy and its relation to Brascamp-Lieb type inequalities. 5. Anari et al. (2021). Log-concave polynomials IV. General down-up mixing for a different kernel. 6. Feng and Paguyo (2026), version 2. Analysis of a twisted Bose-Einstein Markov chain with applications to sampling Catalan structures. Different sampler.