Séminaire Lotharingien de Combinatoire, B30b (1993), 9
pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1993, 1993/034, p.
87-95.]
Helmut Prodinger
Combinatorial Problems Related to Geometrically Distributed Random Variables
Abstract.
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.
The following versions are available: