Discrete Mathematics & Theoretical Computer Science, Vol 8 (2006)

Font Size:  Small  Medium  Large

d-records in geometrically distributed random variables

Helmut Prodinger


We study d–records in sequences generated by independent geometric random variables and derive explicit and asymptotic formulæ for expectation and variance. Informally speaking, a d–record occurs, when one computes the d–largest values, and the variable maintaining it changes its value while the sequence is scanned from left to right. This is done for the “strict model,” but a “weak model” is also briefly investigated. We also discuss the limit q → 1 (q the parameter of the geometric distribution), which leads to the model of random permutations.

Full Text: PDF PostScript