What are the odds of hitting exactly 100 rolling a fair die
I roll a fair die and sequentially sum the numbers the die shows. What are the odds the summation will hit exactly 100?
More generally, what are the odds of hitting an exact target number t while summing the results of numbers sequentially drawn uniformly from a set S.
I have experimentally tested this and the result is (warning - spoilers ahead):
1 over the expectation of the drawn numbers. In the case of the fair die 1/((1+2+3+4+5+6)/6) = 6/21 = 2/7
However I do not have a strong intuition, let alone a formal proof, why this is the case.
I'll be happy to get your thoughts!
Solution 1:
The probability of hitting $n$ on the nose is a function of $n$, call it $f(n)$. It satisfies the recurrence $$f(n)=\frac{f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)+f(n-6)}6$$ with boundary values $f(0)=1$ and $f(n)=0$ for $n\lt0$. I didn't try to solve the recurrence, but my numerical calculations agree with yours, it looks like $f(n)\to2/7$.
Solution 2:
The generating function $$H(x)=\sum\limits_{n=0}^\infty h_nx^n,$$ where $h_0=1$ and, for every $n\geqslant1$, $h_n$ is the probability to hit exactly $n$, solves the identity $$H(x)=1+P(x)H(x),\qquad P(x)=\frac16(x+x^2+\cdots+x^6),$$ hence $$H(x)=\frac1{1-P(x)}.$$ The limit of $h_n$ when $n\to\infty$ is $$\ell=\lim_{x\to1}(1-x)H(x)=\frac1{P'(1)},$$ that is, $$\ell=\frac6{1+2+\cdots+6}=\frac27.$$ This extends to every "die" producing any collection of numbers in any biased or unbiased way. If the "die" produces a random positive integer number $\xi$, the limit of $h_n$ becomes $$\ell=\frac1{E(\xi)}.$$ Assuming the limit $\ell$ exists, this can be understood intuitively as follows: by the law of large numbers, the sum of $n$ draws is about $k=nE(\xi)$ hence, after $n$ draws, $n$ large, one has hit $n$ values from roughly $k$. If each value has a chance roughly $\ell$ to be hit, one can expect that $\ell\approx n/k$, QED. Obvious counterexamples are when $\xi$ is, say, always a multiple of $3$, and these are essentially the only cases since $\ell$ exists if and only if the greatest common divisor of the support of $\xi$ is $1$.
Edit: To estimate the difference $h_n-\ell$ in the usual case, note that $$1-P(x)=(1-x)(1+x/a)(1-x/u)(1-x/\bar u)(1-x/v)(1-x/\bar v),$$ for some $a$ real positive and some complex numbers $u$ and $v$ with nonzero imaginary parts, hence $$H(x)=\frac{\ell}{1-x}+\frac{b}{1+x/a}+\frac{r}{1-x/u}+\frac{\bar r}{1-x/\bar u}+\frac{s}{1-x/v}+\frac{\bar s}{1-x/\bar v},$$ for some real number $b$ and some complex numbers $r$ and $s$ defined as $$b=-\frac1{aP'(-a)},\qquad r=\frac1{uP'(u)},\qquad s=\frac1{vP'(v)}.$$ Thus, for every $n$, $$h_n=\ell+b(-1)^na^{-n}+2\Re\left(r u^{-n}+s v^{-n}\right).$$ Numerically, $a\approx1.49$, and $|u|$ and $|v|$ are approximately $1.46$ and $1.37$, hence all this yields finally $$|h_n-\ell|=O(\kappa^{-n}),\qquad\kappa\approx1.37.$$ For $n=100$, $\kappa^{-n}\approx2\cdot10^{-14}$ hence one expects that $h_n$ coincides with $\ell$ at up to $13$ or $14$ decimal places.
Solution 3:
Some addition on the answer of @bof:
For $n\in\mathbb{Z}$ let $E_{n}$ denote the event that number $n$ shows up in the sequence.
This with $E_{n}=\emptyset$ if $n<0$ and $E_{0}=\Omega$ (we start the list with $0$).
Let $X$ denote the first number that appears.
Then $P\left(E_{n}\right)=\sum_{i=1}^{6}P\left(E_{n}\mid X=i\right)P\left(X=i\right)=\frac{1}{6}\sum_{i=1}^{6}P\left(E_{n-i}\right)$
Solution 4:
...oh I see my error, it's sides/(sum(1 to #sides). That matches. I forgot to change the numerator. I'll leave my comment as is here...
I was curious about the answer, and while I'm not very mathy, I did write a little simulation, to explore the result for dies with different number of sides
For 6 sided die, the answer agreed with the above: 2/7 (~0.28571) probability
but for other die, the answer wasn't 6/sum(1 to #sides)
sides: probability (success at hitting 100 when summing sequential rolls)
2 0.666666...
3 0.5
4 0.4
5 0.333333...
6 ~0.28571
7 0.25
8 0.222222..
9 0.2
10 0.181818..
which suggests the answer is always 2/(#sides+1)
If the answer 6/(sum(1 to #sides)) was used, it was only correct for the sides=6 case (comparing to simulation).
Does the limit for the equations above always work out to 2/(sides+1) for different sided die? (I think? my simulation is accurate)
I was thinking that if the equation was "right", it would be right for die of all sizes?
The 2 sided case suggests an interesting bar-bet that would make money on average (flipping a coin and summing with either 1 or 2, trying to hit 100)
-kevin
Solution 5:
Not a formal proof but an intuition -
let $k$ be the number showing on the face of the die when it reaches $100$ or above for the first; considering
- (a) this face has $\large{k \over \sum \text{Faces}}$ chances of appearing, and
- (b) when it appears there is a $1\over k$ chance that exactly $100$ was reached
... then there is a chance of $\large{1 \over \sum \text{Faces}}$ that the die stopped on face $k$ on exactly $100$, so a $\large{|\text{Faces}| \over \sum \text{Faces}}$ chance that exactly $100$ was reached.
Which for a fair die results in $\frac{6}{21} = \frac 27$.
(I think (b) is true, but I'm not sure about (a))