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