How often do we reject a superior value? (Extended abstract)

• Main Authors: Oliver, Kamilla, Prodinger, Helmut
• Other Authors: Department Mathematik Erlangen, Friedrich-Alexander Universität Erlangen-Nürnberg = University of Erlangen-Nuremberg (FAU), Department of Mathematical Sciences Matieland, Stellenbosch Uni. (DMS), Stellenbosch University, Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2011
• Subjects: combinatorics on words; records; generating functions; Rice's method; $q$-series; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; Iceland
• 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

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.