Geodesic
Combinatorial Problems Related to Geometrically Distributed Random Variables
Séminaire lotharingien de combinatoire, Tome 30 (1993)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

Assume that we have n independent geometrically distributed random variables. We consider the statistics "left-to-right maxima in the strict (resp. weak) sense" and the "path length", which is sort of a cumulated quantity, motivated by analyzing "Skip lists". By appropriate "languages" and (functional) difference equations, we manage to set up explicit formulae for the average and the variance. These quantities are quite involved, and asymptotic evaluations are required. Everything is expressed in terms of certain standard (alternating) sums, which are attacked by "Rice's method".

This is essentially a summary of:
H. Prodinger, Combinatorics of geometrically distributed random variables: Left-to-right maxima, 5th FPSAC (Firenze), also: Discrete Mathematics, to appear.
P. Kirschenhofer, H. Prodinger, The path length of random skip lists, Acta Informatica 31 (1994), 775-792. 

@article{SLC_1993_30_a1,
     author = {Helmut Prodinger},
     title = {Combinatorial {Problems} {Related} to {Geometrically} {Distributed} {Random} {Variables}},
     journal = {S\'eminaire lotharingien de combinatoire},
     publisher = {mathdoc},
     volume = {30},
     year = {1993},
     url = {http://geodesic.mathdoc.fr/item/SLC_1993_30_a1/}
}
TY  - JOUR
AU  - Helmut Prodinger
TI  - Combinatorial Problems Related to Geometrically Distributed Random Variables
JO  - Séminaire lotharingien de combinatoire
PY  - 1993
VL  - 30
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_1993_30_a1/
ID  - SLC_1993_30_a1
ER  - 
%0 Journal Article
%A Helmut Prodinger
%T Combinatorial Problems Related to Geometrically Distributed Random Variables
%J Séminaire lotharingien de combinatoire
%D 1993
%V 30
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_1993_30_a1/
%F SLC_1993_30_a1
Helmut Prodinger. Combinatorial Problems Related to Geometrically Distributed Random Variables. Séminaire lotharingien de combinatoire, Tome 30 (1993). http://geodesic.mathdoc.fr/item/SLC_1993_30_a1/