Exact Sampling of Permutations with a Fixed Longest Increasing Subsequence

Abstract

We study exact uniform sampling of permutations of length $n$ whose longest increasing subsequence (LIS) has prescribed length $k$. Our main result is, to the best of our knowledge, the first polynomial-time exact sampler for this problem, valid for every $1\le k\le n$. Via the Robinson--Schensted correspondence the problem reduces to sampling a Young diagram with first row of length $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 $\tilde{O}(n^4{k}^5)$ time in the word-RAM model. Aggregating the scores and exploiting the Hankel structure of the evaluated matrices reduces this to $\tilde{O}(n^2{k}^4)$. In the linear regime $k\in \Theta (n)$ we give a direct rejection sampler running in expected $O(n\log \log n)$ time, matching, up to constants, the cost of computing the LIS of one permutation. For the relaxed constraint $LIS(\pi )\le k$, plain rejection sampling gives expected $O(n\log \log n)$ time for every $k\ge 4\sqrt{n}$, and so the worst case over all $k$ improves to $\tilde{O}(n^4)$.