Asymptotic results on weakly increasing subsequences in random words
| Autor: | Alperen Y. Özdemir, Ümit Işlak |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Riffle
Applied Mathematics 010102 general mathematics 0102 computer and information sciences Similarity measure 01 natural sciences Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics 60F05 62E20 0101 mathematics Random variable Mathematics - Probability Mathematics Central limit theorem |
| Popis: | Let $X=(X_1,\ldots,X_n)$ be a vector of i.i.d. random variables where $X_i$'s take values over $\mathbb{N}$. The purpose of this paper is to study the number of weakly increasing subsequences of $X$ of a given length $k$, and the number of all weakly increasing subsequences of $X$. For the former, it is shown that a central limit theorem holds. Also, the first two moments of each of those two random variables are analyzed, their asymptotics are investigated, and results are related to the case of similar statistics in uniformly random permutations. We conclude the paper with applications on a similarity measure of Steele, and on increasing subsequences of riffle shuffles. Comment: Final version |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|