Asymptotic behavior of some factorizations of random words

DOI10.1002/RSA.21073MaRDI QIDQ6052484zbMATH OpenWikidataFDO

Authors Elahe Zohoorian Azad, Philippe Chassaing

Publication date 17 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.4062

zbMATH Keywords

Lyndon wordlongest runrandom wordPoisson-Dirichlet distributionstandard right factor

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Combinatorics on words (68R15)

Abstract: In this paper we consider the normalized lengths of the factors of some factorizations of random words. First, for the emph{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. Secondly we consider the emph{standard factorization} of random emph{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: ${\displaystyle }$mu(dx)=p_1 delta_{1}(dx) + (1-p_1) mathbf{1}_{[0,1)}(x)dx,${\displaystyle }$ in which $p_1$ denotes the probability of the smallest letter of the alphabet.

Recommendations

• Limit Law of the Length of the Standard Right Factor of a Lyndon Word
• scientific article; zbMATH DE number 1948508
• The standard factorization of Lyndon words: an average point of view
• Positions of the ranks of factors in certain finite long length words
• The height of the Lyndon tree

Cites work

• scientific article; zbMATH DE number 417855 (Why is no real title available?)
• scientific article; zbMATH DE number 49698 (Why is no real title available?)
• scientific article; zbMATH DE number 3518091 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 1988973 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 894522 (Why is no real title available?)
• Counting permutations with given cycle structure and descent set
• Empirical Processes with Applications to Statistics
• Factorization in F_q[x] and Brownian Motion
• Foundations of Modern Probability
• Limit Law of the Length of the Standard Right Factor of a Lyndon Word
• Logarithmic combinatorial structures: A probabilistic approach
• On Burnside's Problem
• On Poisson–Dirichlet Limits for Random Decomposable Combinatorial Structures
• On random polynomials over finite fields
• Order statistics for decomposable combinatorial structures
• Riffle shuffles, cycles, and descents
• Size-biased sampling of Poisson point processes and excursions
• Some inequalities relating to the partial sum of binomial probabilities
• The origins of combinatorics on words
• The standard factorization of Lyndon words: an average point of view
• Trailing the dovetail shuffle to its lair

Cited in

(8)

• On the distribution of characteristic parameters of words II
• Asymptotic Behavior of k-Word Matches Between two Uniformly Distributed Sequences
• Percolation of arbitrary words in \(\{0, 1\}^ \mathbb{N}\)
• The standard factorization of Lyndon words: an average point of view
• scientific article; zbMATH DE number 1948508 (Why is no real title available?)
• Limit Law of the Length of the Standard Right Factor of a Lyndon Word
• scientific article; zbMATH DE number 939777 (Why is no real title available?)
• The height of the Lyndon tree

This page was built for publication: Asymptotic behavior of some factorizations of random words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6052484)