Asymptotic results on weakly increasing subsequences in random words
Discrete Applied Mathematics, cilt.251, ss.171-189, 2018 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 251
- Basım Tarihi: 2018
- Doi Numarası: 10.1016/j.dam.2018.05.043
- Dergi Adı: Discrete Applied Mathematics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.171-189
- Anahtar Kelimeler: Central limit theorem, Moment asymptotics, Random permutations, Random words, Weakly increasing subsequences
- Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Let X = (X1,…,Xn) be a vector of i.i.d. random variables where Xi's take values over [Formula presented]. 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.