How often do we reject a superior value? 1214&selectfont;(Extended abstract)
Kamilla Oliver, Helmut Prodinger
Abstract
Words a1a2&dots;an with independent letters ak taken from the set of natural numbers, and a weight (probability) attached via the geometric distribution pqi-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.
Résumé. On considère des mots a1a2&dots;an formés de lettres à valeurs entières, tirées de façon indépendante avec une distribution géométrique pqi-1 (p+q=1). Un record k+1 est dit consécutif si la lettre précédente est k. la notion est motivée par des considérations algorithmiques. Les autres records sont rejetés. Nous étudions le nombre de records rejetés. Nous étudions aussi la probabilité qu'il y ait un seul maximum consécutif, et montrons qu'elle converge vers une constante, à certaines fluctuations près.
Résumé. On considère des mots a1a2&dots;an formés de lettres à valeurs entières, tirées de façon indépendante avec une distribution géométrique pqi-1 (p+q=1). Un record k+1 est dit consécutif si la lettre précédente est k. la notion est motivée par des considérations algorithmiques. Les autres records sont rejetés. Nous étudions le nombre de records rejetés. Nous étudions aussi la probabilité qu'il y ait un seul maximum consécutif, et montrons qu'elle converge vers une constante, à certaines fluctuations près.
Full Text: PostScript PDF