How often do we reject a superior value? (Extended abstract)
International audience 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 o...
Main Authors: | , |
---|---|
Other Authors: | , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://inria.hal.science/hal-01215069 https://inria.hal.science/hal-01215069/document https://inria.hal.science/hal-01215069/file/dmAO0165.pdf https://doi.org/10.46298/dmtcs.2949 |
Summary: | International audience 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. On considère des mots $a_1a_2 \ldots a_n$ formés de lettres à valeurs entières, tirées de façon indépendante avec une distribution géométrique $pq^{i-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. |
---|