On the Longest Increasing Subsequence for Finite and Countable Alphabets
| dc.creator | houdré, Christian | |
| dc.creator | Litherland, Trevis J. | |
| dc.date | 2006-12-13 | |
| dc.date.accessioned | 2026-07-07T06:43:13Z | |
| dc.date.available | 2026-07-07T06:43:13Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/math/0612364 | |
| dc.identifier | http://arxiv.org/abs/math/0612364 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/102332 | |
| dc.subject | Probability | |
| dc.subject | 60C05, 60F05, 60F17, 60G15, 60G17, 05A16 | |
| dc.title | On the Longest Increasing Subsequence for Finite and Countable Alphabets | |
| dc.type | text |