3
$\begingroup$

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?

$\endgroup$
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$ 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 Chuh
    Feb 10, 2012 at 7:23

2 Answers 2

11
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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