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 version are available: