Séminaire des équipes de recherche

On some factorizations of random words

Séminaires organisés par l'équipe-projet RAP, entrée libre à 10h30.

  • Date : 22/04/2011
  • Lieu : Rocquencourt, bâtiment 9
  • Intervenants : Philippe Chassaing, Institut Élie Cartan, Université Henri Poincaré (Nancy, France)
  • Organisateurs : RAP

We consider the normalized lengths of the factors of the Lyndon decomposition of finite random words with n independent letters drawn from a finite or infinite totally ordered alphabet according to a general probability distribution.
Convergence of the distribution of the lengths of the longest factors to a Poisson-Dirichlet distribution was established by Jenny Hansen and also by Arratia Barbour and Tavare in 1993-94, in the case of equiprobable letters, using combinatorial and probabilistic arguments (in this uniform case, the arguments provide equivalently asymptotics for the degree of the factors in the decomposition of random polynomials over finite fields, and for the size of cycles in the decomposition of some brand of random permutations, called riffle shuffle). In the general case, these arguments seem to break down : we had to rely almost exclusively on probabilistic arguments.
Joint work with Elahe Zohoorian Azad.

Mots-clés : Paris - Rocquencourt Séminaire RAP

Haut de page

Siège et centres de recherche Inria

Accès direct

Social