Jérémie Du Boisberranger ; Danièle Gardy ; Yann Ponty - The weighted words collector

dmtcs:2998 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.2998
The weighted words collectorArticle

Authors: Jérémie Du Boisberranger 1; Danièle Gardy 1; Yann Ponty ORCID2,3

  • 1 Parallélisme, Réseaux, Systèmes, Modélisation
  • 2 Laboratoire d'informatique de l'École polytechnique [Palaiseau]
  • 3 Algorithms and Models for Integrative Biology

We consider the word collector problem, i.e. the expected number of calls to a random weighted generator before all the words of a given length in a language are generated. The originality of this instance of the non-uniform coupon collector lies in the, potentially large, multiplicity of the words/coupons of a given probability/composition. We obtain a general theorem that gives an asymptotic equivalent for the expected waiting time of a general version of the Coupon Collector. This theorem is especially well-suited for classes of coupons featuring high multiplicities. Its application to a given language essentially necessitates knowledge on the number of words of a given composition/probability. We illustrate the application of our theorem, in a step-by-step fashion, on four exemplary languages, whose analyses reveal a large diversity of asymptotic waiting times, generally expressible as $\kappa \cdot m^p \cdot (\log{m})^q \cdot (\log \log{m})^r$, for $m$ the number of words, and $p, q, r$ some positive real numbers.


Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: Coupon Collector Problem,Waiting Time,Random Generation,Weighted Context-free Languages,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

4 Documents citing this article

Consultation statistics

This page has been seen 211 times.
This article's PDF has been downloaded 372 times.