Danièle Gardy

  1. The weighted words collector.

    Authors: Yann Ponty, Jérémie Du Boisberranger, Danièle Gardy
    Subjects: Discrete Mathematics
    Abstract

    Motivated by applications in bioinformatics, we consider the word collector
    problem, i.e. the expected number of calls to a random weighted generator of
    words of length $n$ before the full collection is obtained. 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.

RSS-материал