×

zbMATH — the first resource for mathematics

Combinatorial problems related to geometrically distributed random variables. (English) Zbl 0889.05010
Motivated from computer science problems we consider the following situation (compare [P. Kirschenhofer and H. Prodinger, The path length of random skip lists, Acta Inf. 31, No. 8, 775-792 (1994)] and [H. Prodinger, Discrete Math. 153, No. 1-3, 253-270 (1996; Zbl 0853.60006)]). In these papers the reader will find a more complete description as well as additional references.
Let \(X\) denote a geometrically distributed random variable, i.e. \(\mathbb{P}\{X=k\} =pq^{k-1}\) for \(k\in\mathbb{N}\) and \(q=1 -p\). Assume that we have \(n\) independent random variables \(X_1, \dots, X_n\) according to this distribution.
The first parameter of interest is the number of left-to-right maxima, where we say that \(X_i\) is a left-to-right maximum (in the strict sense) if it is strictly larger than the elements to left. A left-to-right maximum in the loose sense is defined analogously but “larger” is replaced by “larger or equal”. The second parameter of interest is the (horizontal) path length, i.e. the sum of the left-to-right maxima in the loose sense of all the sequences \(X_i, \dots, X_n\), where \(i\) is running from 1 to \(n\).
MSC:
05A15 Exact enumeration problems, generating functions
05A16 Asymptotic enumeration
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: EMIS EuDML