Exact Sampling of Permutations with a Fixed Longest Increasing Subsequence
This work provides the first exact samplers for this combinatorial structure, addressing a gap in random generation for constrained permutations.
The paper presents two exact uniform sampling algorithms for permutations of length n with a longest increasing subsequence of prescribed length k. For k in Θ(n), a rejection sampler runs in O(n log log n) expected time; for arbitrary k, a sampler based on the Robinson-Schensted correspondence runs in Õ(n³k⁴) expected time.
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.