pith. sign in

arxiv: 2606.02263 · v1 · pith:XPH5WH5Qnew · submitted 2026-06-01 · 💻 cs.DS · math.CO

Exact Sampling of Permutations with a Fixed Longest Increasing Subsequence

Peter Clifford , Rapha\"el Clifford This is my paper

Pith reviewed 2026-06-28 12:08 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords exact samplingpermutationslongest increasing subsequencerejection samplingRobinson-Schensted correspondencedeterminant identitiesHankel matricesYoung tableaux
0
0 comments X

The pith

Permutations with longest increasing subsequence of exact length k can be sampled uniformly via a rejection method that runs in expected O(n log log n) time when k is linear in n.

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

The paper gives exact algorithms for sampling a uniform random permutation of length n whose longest increasing subsequence has length exactly k. For k proportional to n a rejection sampler works on an expanded space of permutations paired with one distinguished increasing subsequence of length k, accepting only when that subsequence is the leftmost longest one. The resulting distribution is uniform over the target set and the expected running time is O(n log log n) in the word-RAM model. For general k the method first samples the shape under the Plancherel measure conditioned on having longest row or column equal to k by using determinant identities to obtain exact completion counts, then draws two uniform standard Young tableaux of that shape.

Core claim

The central claim is that proposals consisting of a permutation together with a specified increasing subsequence of length k, accepted precisely when the subsequence is the leftmost longest increasing subsequence, produce an exact uniform sample from the set of all permutations whose longest increasing subsequence has length k. When k is Theta(n) the expected cost of this procedure is O(n log log n). For arbitrary k the same idea is realized by sampling the conditioned Plancherel shape through exact determinant evaluations of completion counts, implemented via Hankel moment matrices to reach expected tilde O(n^3 k^4) time, followed by uniform generation of the two tableaux.

What carries the argument

The expanded proposal space of (permutation, specified increasing subsequence) together with the leftmost-LIS acceptance rule that conditions on the distinguished subsequence being the leftmost longest increasing subsequence.

If this is right

  • The output distribution is exactly uniform over the desired set of permutations.
  • When k is linear in n the expected running time is O(n log log n) in the word-RAM model.
  • The determinant-oracle approach yields an exact polynomial-time sampler for every fixed k.
  • Hankel moment matrices reduce the cost of each determinant evaluation from the direct implementation.
  • Two uniform standard Young tableaux of the sampled shape can be generated after the shape is obtained.

Where Pith is reading between the lines

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

  • The same marked-proposal technique might extend to exact sampling of permutations with other fixed subsequence or pattern statistics.
  • Exact counts obtained from the determinant identities could be reused for enumeration or asymptotic analysis of the conditioned sets.
  • Small-instance implementations allow direct verification against exhaustive generation of all qualifying permutations.
  • The conditioned-shape sampler supplies a concrete way to explore the geometry of Young diagrams under a height or width constraint.

Load-bearing premise

The leftmost-LIS acceptance rule on the marked proposals produces exactly the uniform distribution over permutations whose longest increasing subsequence has length k, and the determinant formulas give the precise completion counts for the conditioned shapes.

What would settle it

For small n and k, run the sampler a large number of times and check whether every permutation with LIS length k appears with equal frequency up to sampling error, or whether the empirical distribution over shapes matches the known conditional Plancherel probabilities.

Figures

Figures reproduced from arXiv: 2606.02263 by Peter Clifford, Rapha\"el Clifford.

Figure 1
Figure 1. Figure 1: An example of the Robinson–Schensted correspondence. The permutation [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

We study exact uniform sampling of permutations of length $n$ whose longest increasing subsequence (LIS) has prescribed length $k$. For $k \in \Theta(n)$, we give a direct rejection sampler whose expected running time is $O(n\log\log n)$ in the word-RAM model. The sampler uses an expanded proposal space consisting of permutations together with a specified increasing subsequence, and accepts exactly those proposals whose specified subsequence is the leftmost LIS. For arbitrary $1\le k\le n$, we give an exact sampler based on the Robinson--Schensted correspondence. The algorithm samples the corresponding Plancherel-conditioned shape by computing exact completion counts via determinant identities, and then samples two uniform tableaux of that shape. The direct implementation runs in $\tilde O(n^4k^5)$ expected time. We then show that the same sampler can be implemented in expected $\tilde O(n^3k^4)$ time by evaluating a determinant oracle through Hankel moment matrices.

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

2 major / 2 minor

Summary. The paper presents exact uniform sampling algorithms for permutations of [n] with longest increasing subsequence (LIS) of exact length k. For k = Θ(n), it gives a direct rejection sampler over an expanded space of (permutation, specified increasing subsequence) pairs that accepts precisely when the specified subsequence is the leftmost LIS, with expected O(n log log n) time in the word-RAM model. For general 1 ≤ k ≤ n, it gives an RS-correspondence sampler that first samples a Plancherel-conditioned Young diagram shape by exact determinant evaluation of completion counts (via Hankel moment matrices), then samples two uniform standard Young tableaux of that shape; the improved implementation runs in expected ilde O(n^3 k^4) time.

Significance. If the uniformity and runtime claims hold, the work supplies the first near-linear-time exact sampler for the dense regime k = Θ(n) and a polynomial-time exact method for arbitrary k, both using only standard combinatorial bijections and algebraic identities with no fitted parameters. The Hankel-matrix acceleration of the determinant oracle is a concrete technical improvement over the direct ilde O(n^4 k^5) implementation.

major comments (2)
  1. [§3 (rejection sampler)] The central uniformity claim for the rejection sampler (abstract and §3) rests on the acceptance rule (specified subsequence is the leftmost LIS) exactly canceling proposal bias. The manuscript must contain an explicit calculation showing that every target permutation π with LIS(π)=k is proposed with total mass proportional to the number of its qualifying leftmost increasing subsequences of length k; without this derivation the exactness guarantee is not yet load-bearing.
  2. [§4.2 (Hankel acceleration)] §4.2, determinant identities: the reduction from Plancherel-conditioned shape probabilities to Hankel determinants of moment matrices must be accompanied by a proof that the oracle returns exact integer counts (not approximations) for every admissible shape; the current runtime analysis assumes this exactness but does not verify the bit-complexity of the arithmetic.
minor comments (2)
  1. Notation for the leftmost LIS is introduced without a formal definition or example; a small diagram would clarify the acceptance condition.
  2. The word-RAM model assumptions (word size, comparison model for the proposal) should be stated explicitly in the runtime theorem.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points where the manuscript's arguments can be made more explicit. We address each major comment below and will revise the manuscript to incorporate the requested derivations.

read point-by-point responses

  1. Referee: [§3 (rejection sampler)] The central uniformity claim for the rejection sampler (abstract and §3) rests on the acceptance rule (specified subsequence is the leftmost LIS) exactly canceling proposal bias. The manuscript must contain an explicit calculation showing that every target permutation π with LIS(π)=k is proposed with total mass proportional to the number of its qualifying leftmost increasing subsequences of length k; without this derivation the exactness guarantee is not yet load-bearing.

    Authors: We agree that an explicit derivation is needed to make the uniformity argument fully self-contained. In the revised version we will add a dedicated lemma in §3 that computes the total proposal mass for each fixed π: the proposal distribution is uniform over all pairs (π, S) where S is an increasing subsequence of length k in π, and the leftmost-LIS acceptance condition selects precisely those S that are leftmost, with acceptance probability inversely proportional to their number. This yields proposal mass exactly proportional to the number of leftmost length-k increasing subsequences, so that after acceptance every target π is equally likely. The calculation relies only on partitioning the proposal space by the leftmost property and does not require additional combinatorial machinery. revision: yes

  2. Referee: [§4.2 (Hankel acceleration)] §4.2, determinant identities: the reduction from Plancherel-conditioned shape probabilities to Hankel determinants of moment matrices must be accompanied by a proof that the oracle returns exact integer counts (not approximations) for every admissible shape; the current runtime analysis assumes this exactness but does not verify the bit-complexity of the arithmetic.

    Authors: We agree that the exact integrality and bit-complexity warrant an explicit statement. In the revision we will augment §4.2 with a short argument establishing that each Hankel determinant equals the exact non-negative integer completion count (by the known combinatorial interpretation of the moment sequence as counting SYT of skew shapes and the integrality of the underlying RSK correspondence). We will also bound the bit length of all intermediate integers by O(n² log n), confirming that the arithmetic cost remains absorbed in the stated ãO(n³k⁴) word-RAM bound. revision: yes

Circularity Check

0 steps flagged

No circularity; derivations are constructive reductions to Robinson-Schensted bijection and determinant identities

full rationale

The paper's samplers are defined via explicit proposal distributions (permutations with a marked increasing subsequence) and acceptance rules (leftmost LIS condition), plus exact counting via Plancherel measures and Hankel matrices. These steps invoke standard, externally known combinatorial facts (RS correspondence, determinant formulas for Young tableaux) rather than self-defining the target distribution or renaming fitted quantities as predictions. No load-bearing self-citation chains or ansatzes appear in the provided claims. The uniformity follows directly from the bijection and the acceptance rule's combinatorial justification, which is independent of the paper's own fitted values.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard combinatorial bijections and algebraic identities with no free parameters fitted to data, no ad-hoc constants, and no new postulated entities.

axioms (2)
  • standard math Robinson-Schensted correspondence bijects permutations to pairs of standard Young tableaux of identical shape.
    Invoked to reduce the general-k sampling problem to shape sampling plus tableau generation.
  • standard math Determinant identities compute exact completion counts for Young diagrams under the relevant conditioning.
    Used to sample the Plancherel-conditioned shape exactly.

pith-pipeline@v0.9.1-grok · 5696 in / 1529 out tokens · 40465 ms · 2026-06-28T12:08:36.703552+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

38 extracted references · 18 canonical work pages · 1 internal anchor

  1. [1]

    doi:10.1016/j.tcs.2004.03.057 , file =

    Longest Increasing Subsequences in Sliding Windows , author =. doi:10.1016/j.tcs.2004.03.057 , file =

    work page doi:10.1016/j.tcs.2004.03.057 2004

  2. [2]

    doi:10.1007/BF01204214 , file =

    Hammersley's Interacting Particle Process and Longest Increasing Subsequences , author =. doi:10.1007/BF01204214 , file =

    work page doi:10.1007/bf01204214

  3. [3]

    Longest Increasing Subsequences: From Patience Sorting to the

    Aldous, David and Diaconis, Persi , date =. Longest Increasing Subsequences: From Patience Sorting to the. doi:10.1090/S0273-0979-99-00796-X , file =

    work page doi:10.1090/s0273-0979-99-00796-x

  4. [4]

    doi:10.1090/S0894-0347-99-00307-0 , file =

    On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations , author =. doi:10.1090/S0894-0347-99-00307-0 , file =

    work page doi:10.1090/s0894-0347-99-00307-0

  5. [5]

    Perfect Sampling Algorithms for

    Betea, Dan and Boutillier, Cédric and Bouttier, Jérémie and Chapuy, Guillaume and Corteel, Sylvie and Vuletić, Mirjana , date =. Perfect Sampling Algorithms for. 1407.3764 , eprinttype =

    Pith/arXiv arXiv

  6. [6]

    Asymptotics of

    Borodin, Alexei and Okounkov, Andrei and Olshanski, Grigori , date =. Asymptotics of

  7. [7]

    The Dynamic Longest Increasing Subsequence Problem

    The Dynamic Longest Increasing Subsequence Problem , author =. doi:10.48550/arXiv.1309.7724 , file =. 1309.7724 , eprinttype =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1309.7724

  8. [8]

    doi:10.1016/j.ic.2010.04.003 , file =

    Fast Computation of a Longest Increasing Subsequence and Application , author =. doi:10.1016/j.ic.2010.04.003 , file =

    work page doi:10.1016/j.ic.2010.04.003 2010

  9. [9]

    On Distance to Monotonicity and Longest Increasing Subsequence of a Data Stream , booktitle =

    Ergün, Funda and Jowhari, Hossein , date =. On Distance to Monotonicity and Longest Increasing Subsequence of a Data Stream , booktitle =

  10. [10]

    doi:10.4153/CJM-1954-030-1 , file =

    The Hook Graphs of the Symmetric Group , author =. doi:10.4153/CJM-1954-030-1 , file =

    work page doi:10.4153/cjm-1954-030-1 1954

  11. [11]

    doi:10.1016/0012-365X(75)90103-X , file =

    On Computing the Length of Longest Increasing Subsequences , author =. doi:10.1016/0012-365X(75)90103-X , file =

    work page doi:10.1016/0012-365x(75)90103-x

  12. [12]

    Gopalan, Parikshit and Jayram, T. S. and Krauthgamer, Robert and Kumar, Ravi , date =. Estimating the Sortedness of a Data Stream , booktitle =. doi:10.5555/1283383.1283417 , file =

    work page doi:10.5555/1283383.1283417

  13. [13]

    , date =

    Greene, Curtis and Nijenhuis, Albert and Wilf, Herbert S. , date =. A Probabilistic Proof of a Formula for the Number of. doi:10.1016/0001-8708(79)90023-9 , file =

    work page doi:10.1016/0001-8708(79)90023-9

  14. [14]

    Hammersley, J. M. , editor =. A Few Seedlings of Research , booktitle =

  15. [15]

    Matrix Analysis , author =

  16. [16]

    The Longest Increasing Subsequence in a Random Permutation and a Unitary Random Matrix Model , author =

  17. [17]

    Discrete Orthogonal Polynomial Ensembles and the Plancherel Measure , author =

  18. [18]

    Discrete Orthogonal Polynomial Ensembles and the

    Johansson, Kurt , date =. Discrete Orthogonal Polynomial Ensembles and the

  19. [19]

    Permutations, Matrices, and Generalized Young Tableaux , author =

  20. [20]

    Improved Dynamic Algorithms for Longest Increasing Subsequence , booktitle =

    Kociumaka, Tomasz and Seddighin, Saeed , date =. Improved Dynamic Algorithms for Longest Increasing Subsequence , booktitle =. doi:10.1145/3406325.3451026 , file =

    work page doi:10.1145/3406325.3451026

  21. [21]

    Liu, Feihu and Xin, Guoce and Zhang, Zihao , date =. An. 2501.05182 , eprinttype =

    arXiv

  22. [22]

    Logan, B. F. and Shepp, L. A. , date =. A Variational Problem for Random. doi:10.1016/0001-8708(77)90030-5 , file =

    work page doi:10.1016/0001-8708(77)90030-5

  23. [23]

    Symmetric Functions and Hall Polynomials , author =

  24. [24]

    Dynamic Algorithms for

    Mitzenmacher, Michael and Seddighin, Saeed , date =. Dynamic Algorithms for. Proceedings of the 52nd. doi:10.1145/3357713.3384240 , file =

    work page doi:10.1145/3357713.3384240

  25. [25]

    doi:10.1155/S1073792800000532 , file =

    Random Matrices and Random Permutations , author =. doi:10.1155/S1073792800000532 , file =

    work page doi:10.1155/s1073792800000532

  26. [26]

    , date =

    Pan, Victor Y. , date =. Nearly Optimal Computations with Structured Matrices , booktitle =

  27. [27]

    and Zheng, A

    Pan, Victor Y. and Zheng, A. and Abu Tabanjeh, M. and Chen, Z. and Providence, S. , date =. Superfast Computations with Singular Structured Matrices over Abstract Fields , booktitle =

  28. [28]

    doi:10.2307/2372326 , file =

    On the Representations of the Symmetric Group , author =. doi:10.2307/2372326 , file =

    work page doi:10.2307/2372326

  29. [29]

    The Surprising Mathematics of Longest Increasing Subsequences , author =

  30. [30]

    , date =

    Sagan, Bruce E. , date =. The Symmetric Group:

  31. [31]

    doi:10.1137/130942152 , file =

    Estimating the Longest Increasing Sequence in Polylogarithmic Time , author =. doi:10.1137/130942152 , file =

    work page doi:10.1137/130942152

  32. [32]

    doi:10.4153/CJM-1961-015-3 , file =

    Longest Increasing and Decreasing Subsequences , author =. doi:10.4153/CJM-1961-015-3 , file =

    work page doi:10.4153/cjm-1961-015-3 1961

  33. [33]

    Enumerative Combinatorics , author =

  34. [34]

    , editor =

    Stanley, Richard P. , editor =. Increasing and Decreasing Subsequences and Their Variants , booktitle =

  35. [35]

    Enumerative Combinatorics, Volume 1 , author =

  36. [36]

    Longest Increasing Subsequences,

    Thomas, Hugh and Yong, Alexander , date =. Longest Increasing Subsequences,. doi:10.1016/j.aam.2009.07.005 , file =

    work page doi:10.1016/j.aam.2009.07.005 2009

  37. [37]

    Design and Implementation of an Efficient Priority Queue , author =

  38. [38]

    Vershik, A. M. and Kerov, S. V. , date =. Asymptotics of the