Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T14:03:00.380Z Has data issue: false hasContentIssue false
  • English
  • Français

Limit Law of the Length of the Standard Right Factor of a Lyndon Word

Published online by Cambridge University Press:  01 May 2007

R. MARCHAND  and
E. ZOHOORIAN AZAD
R. MARCHAND
Affiliation:
Institut Elie Cartan Nancy (mathématiques), Université Henri Poincaré Nancy 1, Campus Scientifique, BP 239, 54506 Vandoeuvre-lès-Nancy Cedex, France (e-mail: [email protected], [email protected])
E. ZOHOORIAN AZAD
Affiliation:
Institut Elie Cartan Nancy (mathématiques), Université Henri Poincaré Nancy 1, Campus Scientifique, BP 239, 54506 Vandoeuvre-lès-Nancy Cedex, France (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider the set of finite words on a totally ordered alphabet with two letters. We prove that the distribution of the length of the standard right factor of a random Lyndon word with length n, divided by n, converges to when n goes to infinity. The convergence of all moments follows. This paper thus completes the results of [2], in which the limit of the first moment is given.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 3 , May 2007 , pp. 417 - 434
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Andrews, G. E. (1984) The Theory of Partitions, Cambridge University Press.CrossRefGoogle Scholar
[2]Bassino, F., Clément, J. and Nicaud, C. (2005) The standard factorization of Lyndon words: An average point of view. Discrete Math. 290 1–25.CrossRefGoogle Scholar
[3]Bollobás, B. (2001) Random Graphs, Vol. 73 of Cambridge Studies in Advanced Mathematics, 2nd edn, Cambridge University Press.Google Scholar
[4]Diaconis, P., McGrath, M. J. and Pitman, J. (1995) Riffle shuffles, cycles, and descents. Combinatorica 15 11–29.CrossRefGoogle Scholar
[5]Erdös, P. and Révész, P. (1977) On the length of the longest head-run. In Topics in Information Theory (Second Colloq., Keszthely, 1975), Vol. 16 of Colloq. Math. Soc. Janos Bolyai, North-Holland, Amsterdam, pp. 219–228.Google Scholar
[6]Gordon, L., Schilling, M. F. and Waterman, M. S. (1986) An extreme value theory for long head runs. Probab. Theory Related Fields 72 279–287.CrossRefGoogle Scholar
[7]Hitczenko, P. and Louchard, G. (2001) Distinctness of compositions of an integer: A probabilistic analysis. Random Struct. Alg. 19 407–437.CrossRefGoogle Scholar
[8]Lothaire, M. (1983) Combinatorics on Words, Vol. 17 of Encyclopedia of Mathematics and its Applications, Addison-Wesley.Google Scholar
[9]Lyndon, R. (1954) On Burnside problem I. Trans. Amer. Math. Soc. 77 202–215.Google Scholar
[10]Pitman, J. (2002) Combinatorial stochastic processes. Technical report no. 621, Department of Statistics, University of California.Google Scholar
[11]Rachev, S. T. (1991) Probability Metrics and the Stability of Stochastic Models, Wiley, Chichester, UK.Google Scholar
[12]Reutenauer, C. (1993) Free Lie Algebras, London Mathematical Society Monographs, New Series, Oxford Science Publications.CrossRefGoogle Scholar
[13]Shorack, G. R. and Wellner, J. A. (1986) Empirical Processes with Applications to Statistics, Wiley.Google Scholar