Kamilla Oliver ; Helmut Prodinger
-
How often do we reject a superior value? (Extended abstract)
dmtcs:2949 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2011,
DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
-
https://doi.org/10.46298/dmtcs.2949
How often do we reject a superior value? (Extended abstract)Article
Authors: Kamilla Oliver 1; Helmut Prodinger 2
NULL##NULL
Kamilla Oliver;Helmut Prodinger
1 Department Mathematik [Erlangen]
2 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]
Words $a_1 a_2 \ldots 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.