Suppose you roll an $n$ sided die (valued $1,\dots,n$) until the sum is at least $s\in\mathbb{N}$. Which of the integers $s, s+1, \dots, s+n-1$ are you most likely to end up with?
2
-
2$\begingroup$ some motivation would be nice . . . as well as some hint as to how much you have thought about the problem yourself $\endgroup$– John PardonCommented Feb 10, 2012 at 2:31
-
1$\begingroup$ Hi, sorry, perhaps I should mention that I came across this as a brainteaser whilst preparing for an interview. $\endgroup$– A ChuhCommented Feb 10, 2012 at 7:23
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Denote by $p(k)$ the probability that the cummulative sum is equal to $k$ at some point. If we denote by $f(i)$ the probability that the first sum $\geq s$ is equal to $s+i$ then observe that $$f(i)=\sum_{k=s+i-n}^{s-1} \frac{p(k)}{n},$$ in particular this implies that $f(0)\geq f(1)\geq \cdots \geq f(n-1)$.
answered Feb 10, 2012 at 2:43
$\begingroup$
$\endgroup$
To continue with the answer above, one might suspect that the probability $p(k)$ of seeing a particular number converges to a fixed value $v.$ If so, then the probability $f(i)$ that the first sum greater or equal to $s$ is equal to $s+i$ is $(1-\frac{i}{n})v=\frac{2(n-i)}{n(n+1)}.$ The last step justified by the fact that $v=\frac{2}{n+1}$ makes these sum to $1$. Since the average roll is $\frac{n+1}{2}$, that is to be expected. The convergence of $p(k)$ can be established fairly easily.
answered Feb 10, 2012 at 7:06