Asymptotic behavior of some factorizations of random words
Elahe Zohoorian Azad, Philippe Chassaing · Random Structures and Algorithms · 2021
Abstract In this paper, we consider the normalized lengths of the factors of some factorizations of random words. First, for theLyndon factorizationof finite random words withnindependent 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 thestandard factorizationof randomLyndon word: we prove that the distribution of the normalized length of the standard right factor of a randomn‐letters long Lyndon word, derived from such an alphabet, converges, whennis large, to: in which denotes the probability of the smallest letter of the alphabet.