Exact Sampling of Permutations with a Prescribed Longest Increasing Subsequence Length

Peter Clifford, Raphaël Clifford · 2026

Read Exact Sampling of Permutations with a Prescribed Longest Increasing Subsequence Length by Peter Clifford, Raphaël Clifford (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-02263.txt.

Introduction

Clifford and Clifford sample permutations with a fixed longest increasing subsequence. Exact uniform sampling is the problem studied here. Permutations have length n and prescribed LIS length k. No polynomial-time exact sampler was known for this task. The result covers every k from one to n.

The Robinson-Schensted correspondence reduces the problem to Young diagrams. The diagram's first row must have length k. Its law is the hook-length-squared, or conditioned Plancherel, law. The shape is sampled one coordinate at a time. Each conditional weight is a sum over many completions. Through the Cauchy-Binet formula, it collapses to one coefficient. That coefficient comes from a determinant of a small polynomial matrix. A direct implementation runs in near n to the fourth times k to the fifth expected time.

Catalog record

CREATORPeter Clifford, Raphaël Clifford
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.02263

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exact Sampling of Permutations with a Prescribed Longest Increasing Subsequence Length Peter Clifford, Raphaël Clifford Abstract We study exact uniform sampling of permutations of length n n whose longest increasing subsequence (LIS) has prescribed length k k . Our main result is, to the best of our knowledge, the first polynomial-time exact sampler for this problem, valid for every 1 ≤ k ≤ n 1\leq k\leq n . Via the Robinson–Schensted correspondence the problem reduces to sampling a Young diagram with first row of length k k from the hook-length-squared (conditioned Plancherel) law. We sample this shape one coordinate at a time, where each conditional weight, a sum over exponentially many completions, collapses, through the Cauchy–Binet formula, to a single coefficient of the determinant of a small polynomial matrix. A direct implementation runs in expected O ~ ​ ( n 4 ​ k 5 ) \tilde{O}(n^{4}k^{5}) time in the word-RAM model. Exploiting the Hankel structure of the evaluated matrices reduces this to O ~ ​ ( n 3 ​ k 4 ) \tilde{O}(n^{3}k^{4}) . In the linear regime k ∈ Θ ⁡ ( n ) k\in\Theta(n) we give a direct rejection sampler running in expected O ⁡ ( n ​ log ⁡ log ​ n ) O(n\log\log n) time, matching, up to constants, the cost of computing the LIS of one permutation. For the relaxed constraint LIS ⁡ ( π ) ≤ k \operatorname{LIS}(\pi)\leq k , plain rejection sampling gives expected O ⁡ ( n ​ log ⁡ log ​ n ) O(n\log\log n) time for every k ≥ 4 ​ n k\geq 4\sqrt{n} , and so the worst case over all k k improves to O ~ ​ ( n 5 ) \tilde{O}(n^{5}) . 1 Introduction The longest increasing subsequence is one of the most intensively studied of all permutation statistics. Interest in its behaviour on a uniformly random permutation goes back to Ulam, and its analysis, through Hammersley’s interacting particle process, the limit-shape theorems of Logan–Shepp and Vershik–Kerov, and the Baik–Deift–Johansson fluctuation theorem, helped to build the modern theory connecting random permutations to random matrices and determinantal processes [ 17 , 24 , 35 , 20 , 5 , 7 , 26 ] . See the papers of Aldous and Diaconis [ 2 , 3 ] , Stanley’s survey [ 33 ] , and Romik’s book [ 29 ] for a comprehensive introduction. This paper asks a basic algorithmic question about this much-studied statistic, a question that appears to have gone unaddressed. Can one efficiently sample a permutation of length n uniformly at random , subject to the constraint that its LIS has a prescribed length k ? Formally, for a permutation \pi\in S_{n} , let \operatorname{LIS}(\pi) denote the length of its longest increasing subsequence. Given input parameters (n,k) , we want to sample exactly from the uniform distribution on \Omega_{n,k}:=\{\pi\in S_{n}:\operatorname{LIS}(\pi)=k\}. Simple approaches fail. A uniform permutation has \operatorname{LIS} equal to a specific k with probability that can be as small as 1/n! , so rejection sampling from S_{n} is hopeless in general. The one exception is a narrow window around the typical value k\approx 2\sqrt{n} , where plain rejection sampling runs in polynomial time. Elsewhere \mathbf{P}(\operatorname{LIS}=k) is superpolynomially small. A potentially viable route is to attempt Markov chain Monte Carlo on \Omega_{n,k} , but no chain with a provable polynomial mixing time is known and our goal is exact, not approximate, sampling. The Robinson–Schensted correspondence reduces the problem to sampling a Young diagram with first row of length k from a hook-length-squared distribution, but there are \exp(\Theta(\sqrt{n})) partitions of n , so a naive dynamic program over shapes is also superpolynomial. Summary of results. Our main result is, to the best of our knowledge, the first polynomial-time exact sampler for \Omega_{n,k} , valid for every 1\leq k\leq n . A direct implementation runs in expected \tilde{O}(n^{4}k^{5}) time (Theorem 2.1 ), and a structured implementation of the same sampler runs in expected \tilde{O}(n^{3}k^{4}) time (Theorem 2.2 ). Since k\leq n , this is in particular an \tilde{O}(n^{7}) exact sampler for every k . In the linear regime k\in\Theta(n) a much faster solution is possible. Rejection sampling on an expanded proposal space achieves expected O(n\log\log n) time (Theorem 2.3 ). This matches, up to constants, the best known bound for merely computing the LIS of a single permutation [ 10 ] , so in this regime sampling a uniform element of \Omega_{n,k} is as cheap as testing membership in it. The same sampler degrades gracefully, remaining polynomial for all k\geq\eta n/\log n (Corollary 5.3 ). Table 1 summarises these bounds, and Section 2 states the results formally. The general sampler extends, with the same bounds, to the relaxed constraint \operatorname{LIS}(\pi)\leq k (Corollary 2.4 ). For this relaxed problem, plain rejection from S_{n} already gives expected O(n\log\log n) time for every k\geq 4\sqrt{n} , and so the worst case over all k improves to \tilde{O}(n^{5}) . Techniques. The main sampler rests on the Robinson–Schensted correspondence, which reduces uniform sampling from \Omega_{n,k} to sampling a Young diagram with first row of length k from Plancherel measure conditioned on \lambda_{1}=k . We conjugate the shape and apply a coordinate shift, re-expressing this law as a fixed-sum distribution on strict partitions whose weight is a squared Vandermonde factor times independent factorial weights. The sampler then exposes the shifted coordinates one at a time. At each partial state, it chooses the next coordinate with probability proportional to the total weight of all valid completions. The completion sums range over exponentially many suffixes, but they are not enumerated. By Cauchy–Binet, each such sum is a coefficient of the determinant of a polynomial moment matrix. At each scalar evaluation this moment matrix is Hankel, so the needed determinant values can be computed from O(k) moments in near-linear time. The resulting completion scores are exact integers. They are computed modulo word-size primes and reconstructed by Chinese remaindering, so no rounding enters the procedure and the output law is exactly uniform. Conceptually, this is an extension-counting sampler in the sense of Jerrum, Valiant and Vazirani [ 19 ] . Exact counts of completions from each partial state determine the conditional distribution of the next step. The new ingredient here is the determinant-based oracle that makes these completion counts efficient. For the linear regime where k\in\Theta(n) a lighter idea suffices. We sample from an expanded space of pairs (\pi,I) in which I is a distinguished k -term increasing subsequence of the permutation \pi , and accept only when I is the leftmost LIS of \pi . This is a canonical witness computable in O(n\log\log n) time. Every permutation with \operatorname{LIS}=k then survives in exactly one accepted pair, so acceptance yields exact uniformity, and a Plancherel-measure tail bound shows that the acceptance probability is bounded below by a constant. This same rejection sampling idea gives a polynomial-time sampling algorithm as long as k\in\Omega(n/\log n) . Related work. On static inputs, the computation of the LIS admits an O(n\log n) comparison-based algorithm [ 13 ] . For permutations of [n] , faster word-RAM algorithms are known. In particular, the standard predecessor-based implementation gives O(n\log\log n) time, and Crochemore and Porat give an O(n\log\log\ell) bound in terms of the LIS length

Read the complete text