On the Longest Increasing Subsequence for Finite and Countable Alphabets

Let $X_1, X_2,..., X_n,... $ be a sequence of iid random variables with values in a finite alphabet $\{1,...,m\}$. Let $LI_n$ be the length of the longest increasing subsequence of $X_1, X_2,..., X_n.$ We express the limiting distribution of $LI_n$ as functionals of $m$ and $(m-1)$-dimensional Brownian motions. These expressions are then related to similar functionals appearing in queueing theory, allowing us to further establish asymptotic behaviors as $m$ grows. The finite alphabet results are then used to treat the countable (infinite) alphabet.

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.