Exact Sampling of Permutations with a Fixed Longest Increasing Subsequence
2026-06-01 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to randomly pick permutations of length n where the longest increasing part has a specific length k. For cases where k grows proportionally with n, they create a rejection sampling method that runs efficiently in about n log log n time. For all other values of k, they develop a different exact method using a known mathematical tool called the Robinson--Schensted correspondence, which involves counting certain patterns via determinants. They also improve the efficiency of this method by using advanced matrix techniques, lowering the expected running time considerably.
permutationlongest increasing subsequence (LIS)uniform samplingrejection samplingRobinson--Schensted correspondencePlancherel measuredeterminantHankel matrixword-RAM modelalgorithm complexity
Authors
Peter Clifford, Raphaël Clifford
Abstract
We study exact uniform sampling of permutations of length $n$ whose longest increasing subsequence (LIS) has prescribed length $k$. For $k \in Θ(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.