Asymptotic behavior of some factorizations of random words. Issue 3 (20th December 2021) - Zohoorian Azad, Elahe; Chassaing, Philippe
Abstract: 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 which p 1 $$ {p}_1 $$ denotes the probability of the smallest letter of the alphabet.