Discrete Mathematics & Theoretical Computer Science |

2949

- 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.

Source: HAL:hal-01215069v1

Volume: DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)

Section: Proceedings

Published on: January 1, 2011

Imported on: January 31, 2017

Keywords: $q$-series,combinatorics on words,records,generating functions,Rice's method,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 141 times.

This article's PDF has been downloaded 256 times.