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.,

This paper is available in the Tex, Dvi, and PostScript format.

(Back to List of Papers)