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.
Answer
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$$
No comments:
Post a Comment