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$ Commented May 13, 2014 at 13:28

2 Answers 2

Reset to default
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$ Commented May 13, 2014 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$ Commented May 14, 2014 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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.