MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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:

share|cite|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? – alezok Mar 6 '12 at 20:27
@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


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.