How often do we reject a superior value?
Date
2011
Authors
Oliver K.
Prodinger H.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Keywords
Citation
FPSAC'11 - 23rd International Conference on Formal Power Series and Algebraic Combinatorics
741
752
741
752