Online Permutation Embedding: Optimal Stopping and Scaling Laws

Abstract

We study optimal online algorithms for embedding a permutation $π$ of $[k]$ into an iid stream of uniform $[0,1]$ random variables. This problem is a broad generalization of the classical online monotone subsequence selection problem, recovered in the special case $π=\mathrm{Id}_k$. Our first contribution is an efficiently solvable dynamic program for the optimal embedding time of any $k$-permutation $π$. This dynamic program also yields an explicit optimal online embedding algorithm. We then investigate the asymptotic scaling of the optimal embedding time for uniformly random target permutations, as well as the extremal problem of identifying the permutations with largest expected online embedding time. Our second main result shows that, to first order, random permutations are strictly faster to embed than monotone permutations, which in turn are strictly faster to embed than the extremal permutations. This separation stands in sharp contrast to prevailing conjectures and heuristics in the offline theory of permutation embeddings.

Disclosure

“32 ONLINE PERMUTATION EMBEDDING Acknowledgments KT is partially supported by the NSF grant DMS 2331037. ChatGPT 5.5 Pro was used to prepare the figures and computational supplement. The idea of using the CLT from [18], parts of the martingale construction in Proposition 3.3, and simplifications in several calculus computations arose in conversation”

PDF page 32

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-22T18:21:00.092666Z

Structural counts