2
$\begingroup$

I saw this might have been duplicated in places here -- I think this might be a variation on the coupon collector problem -- but I wanted to be sure and understand how to do the calculation.

I have an n-sided die. I want to know what the average number of rolls between the appearance of a number on the die, k is.

I thought that the binomial distribution would be appropriate here. The way I originally approached it was to say that we have a 1/n chance of getting a number. The chance of getting any other number is (n-1)/n. I know that if I wanted to know the odds of getting the same number several times in a row is $\left(\frac{1}{n}\right)^m$ with m being the number of rolls. But beyond that I was a bit stumped. I know that there's a binomial distribution or a Harmonic number involved somehow, and I read the coupon collector's problem but honestly that explanation seemed to make things less clear rather than more.

Anyhow, if someone could point me to either a duplicate question or a better explanation that would be much appreciated.

$\endgroup$
1
  • $\begingroup$ Look up the geometric distribution. $\endgroup$
    – soakley
    May 13 '14 at 13:28
2
$\begingroup$

Let n denote any face number other than k. At the outset or after a $k$ has turned up, we roll the die until a $k$ reappears. The possibilities are:

$$k, nk, nnk, nnnk, ...$$

If $p$ is the probability of $k$ and $q = (1-p)$ is the probability of $n$, then the expected waiting time is

$$E(N) = \sum_{j=1}^{\infty} jq^{j-1}p = p \frac{d}{dq} \sum_{j=0}^{\infty} q^j = \frac{p}{(1-q)^2} = \frac{1}{p}$$

$\endgroup$
2
  • $\begingroup$ thanks to you both! I figured was making this more complicated than it had to be. $\endgroup$
    – Jesse
    May 13 '14 at 14:18
  • $\begingroup$ That had more to do with the way my screen showed the answers as anything else :-) . Both were equally good. $\endgroup$
    – Jesse
    May 14 '14 at 2:37
1
$\begingroup$

The probability of that the desired side appears in the $k$th try (and not before) is: $$\left(\frac{n-1}n\right)^{k-1}\frac 1n=\frac{(n-1)^{k-1}}{n^k}$$ so the average is $$\sum_{k=1}^\infty\frac{k(n-1)^{k-1}}{n^k}$$ or, if you let $p=1/n$, $q=1-p$, we can define $$f(q)=p\sum_{k=1}^\infty kq^{k-1}=(1-q)\sum_{k=1}^\infty kq^{k-1}$$ Then, integrating by parts and having in mind the geometric series $\sum\limits_{k=1}^\infty q^k=\frac q{1-q}$, $$\int_0^qf(t)dt=\frac q{1-q}(1-q)+\int_0^q\frac t{1-t}dt=q-q-\ln(1-q)$$ And then, $$f(q)=\frac1{1-q}=\frac 1p=n$$

$\endgroup$

Your Answer

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

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