4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ this question belongs on math stackexchange - it's more a homework question than a research question $\endgroup$
    – Anthony Quas
    Commented Mar 6, 2012 at 17:54
  • 2
    $\begingroup$ Actually it is a difficult question that might not have been answered in the literature. $\endgroup$
    – Brendan McKay
    Commented Mar 7, 2012 at 4:35

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – alezok
    Commented Mar 6, 2012 at 20:27
  • 2
    $\begingroup$ @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). $\endgroup$
    – Igor Rivin
    Commented Mar 6, 2012 at 21:25
  • $\begingroup$ See the list on page 7 in the paper... $\endgroup$
    – Igor Rivin
    Commented Mar 6, 2012 at 21:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .