Here's a question for everyone: Let's suppose you roll 1dX, where X is some positive integer. If you roll a 1, you stop. Otherwise, you repeat, but replace X with whatever number you roll.
What's the expected number of dice rolls before you roll a 1?
My mathematician intuition says the way to construct the answer is by induction in some way, but I dunno. Haven't really thought about it yet.
Here's a derivation without using the recursion.
First, we'll do a simple reformulation. For simplicity, include X as one of the rolled values when we start the game. We'll roll a 1dX at each step but only count it if either:
- It's equal to the previous minimum roll, and that wasn't 1.
- OR it's greater than the previous minimum roll.
We stop once every number in 1,2,...,X has been rolled at least once. (Observe that if you strip out the rolls we don't count, then the rolls remaining correspond exactly to rolls in the original problem.)
Let M be the total number of counted rolls made. For k=1,...,X-1, let M_k be the number of counted rolls made after having k distinct roll values so far until (and including) rolling a new value. By linearity of expectation, E[M] = E[M_1] + E[M_2] + ... + E[M_{X-1}]. Write M_k = S_k + G_k where S_k is the count of rolls corresponding to type 1 above and G_k is the count of rolls corresponding to type 2 above.
Deriving S_k: Given that k distinct roll values have been made so far, the probability of 1 NOT being among them is (X-1-k)/(X-1), since there are X-1-k values we haven't rolled yet. In any case, the number of rolls we expect to make equal to the previous minimum before rolling a new distinct value is 1/(X-k) + (1/(X-k))^2 + ... = 1 / (X-1-k). Multiplying, we get E[S_k] = 1/(X-1).
Deriving G_k: Given that k distinct roll values have been made so far, once we roll a new distinct value, there are k+1 distinct values. Since any permutation of those k+1 values where X is the first value is equally likely, the probability that the new value is the minimum is 1/k. So E[G_k] = 1/k.
Thus, E[M] = (X-1)(1/(X-1)) + (1/1 + 1/2 + 1/3 + ... + 1/(X-1)) = 1 + H_{X-1}.
