How often do we reject a superior value?

Abstract

Words a ₁ a ₂…a _n with independent letters a_k taken from the set of natural numbers, and a weight (probability) attached via the geometric distribution pq ^i–1 (p + q = 1) are considered. A consecutive record (motivated by the analysis of a skip list structure) can only advance from k to k + 1 when k is the current consecutive record, and the value k + 1 is seen when scanning the word from left to right. Some larger (= superior) values are therefore ignored (= rejected). We investigate the number of these rejected superior values. Further, we study the probability that there is a single consecutive maximum and show that (apart from fluctuations) it tends to a constant.

Keywords:

• enumeration of words
• records
• generating functions
• asymptotics
• Rice's method
• periodic oscillations
• partition identities