How often do we reject a superior value?

Oliver K. ; Prodinger H. (2011)

Conference Paper

Words a 1a 2...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, thus ignoring perhaps some larger (=superior) values. 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. © 2011 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/21093
This item appears in the following collections: