Premium
Asymptotic behavior of some factorizations of random words
Author(s) -
Zohoorian Azad Elahe,
Chassaing Philippe
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21073
Subject(s) - mathematics , combinatorics , alphabet , dirichlet distribution , distribution (mathematics) , factorization , word (group theory) , discrete mathematics , algorithm , mathematical analysis , philosophy , linguistics , geometry , boundary value problem
In this paper, we consider the normalized lengths of the factors of some factorizations of random words. First, for the Lyndon factorization of finite random words with n independent letters drawn from a finite or infinite totally ordered alphabet according to a general probability distribution, we prove that the limit law of the normalized lengths of the smallest Lyndon factors is a variant of the stickbreaking process. Convergence of the distribution of the lengths of the longest factors to a Poisson–Dirichlet distribution follows. Second, we consider the standard factorization of random Lyndon word : we prove that the distribution of the normalized length of the standard right factor of a random n ‐letters long Lyndon word, derived from such an alphabet, converges, when n is large, to:μ ( d x ) = p 1δ 1 ( d x ) + ( 1 − p 1 ) 1 [ 0 , 1 ) ( x ) d x , $$ \mu (dx)={p}_1{\delta}_1(dx)+\left(1-{p}_1\right){\mathbf{1}}_{\left[0,1\right)}(x) dx, $$ in whichp 1$$ {p}_1 $$ denotes the probability of the smallest letter of the alphabet.