Computer Science – Discrete Mathematics
Scientific paper
2012-02-04
AOFA - 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms - 2012
Computer Science
Discrete Mathematics
Scientific paper
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. This theorem is especially well-suited for classes of coupons featuring high multiplicities. Its application to a given language essentially necessitates some 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 three exemplary languages, revealing asymptotic regimes in $\Theta(\mu(n)\cdot n)$ and $\Theta(\mu(n)\cdot \log n)$, where $\mu(n)$ is the sum of weights over words of length $n$.
Boisberranger Jérémie Du
Gardy Danièle
Ponty Yann
No associations
LandOfFree
The weighted words collector does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The weighted words collector, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The weighted words collector will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-461396