A combinatorial and probabilistic study of initial and end heights of descents in samples of geometrically distributed random variables and in permutations

Abstract : In words, generated by independent geometrically distributed random variables, we study the lth descent, which is, roughly speaking, the lth occurrence of a neighbouring pair ab with a>b. The value a is called the initial height, and b the end height. We study these two random variables (and some similar ones) by combinatorial and probabilistic tools. We find in all instances a generating function Ψ(v,u), where the coefficient of vjui refers to the jth descent (ascent), and i to the initial (end) height. From this, various conclusions can be drawn, in particular expected values. In the probabilistic part, a Markov chain model is used, which allows to get explicit expressions for the heights of the second descent. In principle, one could go further, but the complexity of the results forbids it. This is extended to permutations of a large number of elements. Methods from q-analysis are used to simplify the expressions. This is the reason that we confine ourselves to the geometric distribution only. For general discrete distributions, no such tools are available.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.137--170
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00966508
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 16:59:26
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:56:21

Fichier

616-2508-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966508, version 1

Collections

Citation

Guy Louchard, Helmut Prodinger. A combinatorial and probabilistic study of initial and end heights of descents in samples of geometrically distributed random variables and in permutations. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.137--170. 〈hal-00966508〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

249