Combinatorics of Geometrically Distributed Random Variables:
Left-to-Right Maxima
Abstract.
Assume that the numbers $x_1,\dots,x_n$ are the output of $n$
independent geometrically distributed random variables. The number
$x_i$ is a left-to-right maximum if it is greater (or equal, for a variation,)
than $x_1,\dots,x_{i-1}$. A precise average case analysis is performed
for the parameter `number of left-to-right maxima'. The methods include
generating functions and a technique from complex analysis, called
Rice's method. Some additional results are also given.
helmut@gauss.cam.wits.ac.za,
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)