Asymptotic behavior of some factorizations of random words. Issue 3 (20th December 2021)

• Record Type: Journal Article
• Authors: Zohoorian Azad, Elahe; Chassaing, Philippe
• Is Part Of: Random structures & algorithms. Volume 61:Issue 3(2022)
• Page Start: 543
• Page End: 572
• Publication Date: 2021-12-20
• Subjects: longest run -- Lyndon word -- Poisson–Dirichlet distribution -- Random word -- standard right factor; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21073
• Languages: English
• ISSNs: 1042-9832

Abstract

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.