1
$\begingroup$

I have a question about the coupon collector problem.

What is the expected number to roll all $1$ through $n$ on an unfair $n$-sided die?

Alice rolls a $n$-sided dice until it shows all sides through $1$ to $n$.

But the dice is unfair, so the probability that $i$ shows is different for every trial.

The probability that the sides that appeared in the recent $k$ times are not counted.

For example, if the dice showed $x$-side in time $1$, then during the next $k$ times, $x$-side does not appear. Likewise, in time $2$, If the dice showed $y$, then during the time from $2$ to $1+k$, the side $2$ does not appear.

If the dice is fair, then the calculation is: (Expected time to roll all 1 through 6 on a die) $$ \sum\limits^{n}_{i=1}\left( n/i \right) $$

In the case of unfair dice, my calculation is: $$ k+\sum\limits^{n-k}_{i=k}\left( n-k/i \right) $$

Am I right? Thank you.

$\endgroup$
  • $\begingroup$ It is not clear from your question what expectation you are trying to compute. Perhaps spend some time clarifying. $\endgroup$ – parsiad Jul 31 '17 at 15:50
  • $\begingroup$ verify whether it works for fair coins (k=0, n=2). $\endgroup$ – karakfa Jul 31 '17 at 20:24
  • $\begingroup$ Your die is not only unfair, but it has the property that successive rolls depend on each other, i.e. the die has memory. Your "die" thus resembles the following process: Keep $n$ balls in an urn. Pick the first ball, stamp it with "1", and remove it. Likewise, at the $i$-th stage, pick the $i$-th ball, and stamp it with $i$; replace the $i-k$-th stamped ball in the urn. What is the Expected time for all balls to be drawn from the urn? $\endgroup$ – Ganesh Aug 1 '17 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.