2
$\begingroup$

Suppose I roll an $n$-sided die once. Now you repeatedly roll the die until you roll a number at least as large as I rolled. What is the expected number of rolls you have to make?

I know the answer to this problem, but I'm curious about possible solutions people might post.

$\endgroup$
1
$\begingroup$

If you roll a $k$, then there are $n-k+1$ possible numbers out of $n$ that will be greater than or equal to $k$. This gives rise to a geometric distribution, and so the expected number of rolls required after rolling a $k$ is $\frac{n}{n-k+1}$. Averaging over all $k$, the expected number of rolls will be $$\mathbb{E}=\frac{1}{n}\sum_{k=1}^n \frac{n}{n-k+1}=H_{n}$$ where $H_n$ is the $n^{th}$ harmonic series.

$\endgroup$
  • $\begingroup$ Could you explain why the expected number of rolls required is n/n-k+1? $\endgroup$ – harekuin Apr 25 '17 at 3:18
  • $\begingroup$ This is a fundamental result about geometric distributions. If you have $k$ chance of success on a given roll, the expected number of rolls for success is $\frac 1k$ $\endgroup$ – Ross Millikan Apr 25 '17 at 3:22
  • $\begingroup$ I understand that (as in E[x] = 1/p for a geometric distribution.) then what is the the sum for? i dont fully understand the answer :(. why is the expected being multiplied by 1/n and then the summation?? $\endgroup$ – harekuin Apr 25 '17 at 3:28
  • $\begingroup$ The sum is to cover the range of first rolls. If the die has seven sides and the first roll is $4$, the chance on each roll to at least match it is $\frac 47$ so the expected number of rolls is $\frac 74$. There are seven possible first rolls and we sum over them. $\endgroup$ – Ross Millikan Apr 25 '17 at 3:34
  • $\begingroup$ oh i see. just a general question: the question asks for for the average roll we have to make. Do we NEED to do all possible k's? $\endgroup$ – harekuin Apr 25 '17 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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