Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose one has an alphabet of $K$ letters, from which we draw sequentially letters; assume that the $n$-th letter occurs with a fixed probability $p_n$ independently of the others and of the previous drawn letters and that $\sum_{n=1}^K p_n =1$; this model should be known in the literature as Bernoulli scheme.

Suppose moreover that the letters are not chosen uniformly at random, i.e. there exists a letter (without loss of generality the first one) whose corresponding probability $p_1$ satisfies the property $p_1 \geq p_n$ for all $2 \leq n \leq K$ and this inequality is strict for at least one letter.

We keep sampling letters according to this scheme until we create a string $s$ where all $K$ letters appear at least once.

How many occurrences of the first letter do one have on average in such string? If an exact result is impossible, can one bound this mean or say something its magnitude?

Any hint, partial solution or reference for this problem would be really appreciated.

share|improve this question
2  
this question belongs on math stackexchange - it's more a homework question than a research question –  Anthony Quas Mar 6 '12 at 17:54
2  
Actually it is a difficult question that might not have been answered in the literature. –  Brendan McKay Mar 7 '12 at 4:35

1 Answer 1

The magic words are "Coupon collector problem". For some generalizations, you can check out

The moment zeta function and applications Authors:
Rivin, Igor Publication:
eprint arXiv:math/0201109 Publication Date:
01/2002

share|improve this answer
    
Thanks Igor for your suggestions. Do you know whether my specific question was already answered somewhere in the literature? The reformulation of my question using the CCP terms is: what is the mean of the largest number of cupons of the same type, once that the collection is complete? –  Ale Zok Mar 6 '12 at 20:27
2  
@Ale: Yes, I understand your question: I believe that something very close to this is covered in "the coupon-collector problem revisited", by A Boneh et al (google finds the PDF). –  Igor Rivin Mar 6 '12 at 21:25
    
See the list on page 7 in the paper... –  Igor Rivin Mar 6 '12 at 21:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.