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 |
id |
ftccsdartic:oai:HAL:hal-01215069v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-01215069v1 2023-11-12T04:19:20+01:00 How often do we reject a superior value? (Extended abstract) Oliver, Kamilla Prodinger, Helmut 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 Reykjavik, Iceland 2011 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 en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2949 hal-01215069 https://inria.hal.science/hal-01215069 https://inria.hal.science/hal-01215069/document https://inria.hal.science/hal-01215069/file/dmAO0165.pdf doi:10.46298/dmtcs.2949 info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://inria.hal.science/hal-01215069 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.741-752, ⟨10.46298/dmtcs.2949⟩ 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] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftccsdartic https://doi.org/10.46298/dmtcs.2949 2023-10-14T23:35:36Z 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. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
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] |
spellingShingle |
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] Oliver, Kamilla Prodinger, Helmut How often do we reject a superior value? (Extended abstract) |
topic_facet |
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] |
description |
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. |
author2 |
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 |
author |
Oliver, Kamilla Prodinger, Helmut |
author_facet |
Oliver, Kamilla Prodinger, Helmut |
author_sort |
Oliver, Kamilla |
title |
How often do we reject a superior value? (Extended abstract) |
title_short |
How often do we reject a superior value? (Extended abstract) |
title_full |
How often do we reject a superior value? (Extended abstract) |
title_fullStr |
How often do we reject a superior value? (Extended abstract) |
title_full_unstemmed |
How often do we reject a superior value? (Extended abstract) |
title_sort |
how often do we reject a superior value? (extended abstract) |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
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 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://inria.hal.science/hal-01215069 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.741-752, ⟨10.46298/dmtcs.2949⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2949 hal-01215069 https://inria.hal.science/hal-01215069 https://inria.hal.science/hal-01215069/document https://inria.hal.science/hal-01215069/file/dmAO0165.pdf doi:10.46298/dmtcs.2949 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.46298/dmtcs.2949 |
_version_ |
1782335797312094208 |