Keep rolling an n-sided fair die until you get a number that is less than or equal to a previously rolled number, at which point in time the game ends. On average, how many times do you roll before the game ends? What happens as n gets unboundedly large?
Solution:
It's easier to do this problem by generalizing it a bit. We are given an n-sided fair die, where n is, of course, a natural number. Now let k be an integer in the set {0, 1, 2, ..., n}. Let us generalize by saying that the game ends on the first roll if the rolled number is less than or equal to k. Thereafter, if the game does not end on the first roll, then the game ends upon rolling a number that is less than or equal to a previously rolled number.
Let E(k,n) denote the expectation of the number of rolls before the game ends. We are, of course, particularly interested in finding E(0,n).
We roll at least once. Suppose number j comes up. If j is in the set {1, 2, ..., k} , then the game ends. This happens with a probability of k/n. If j is in the set {k+1, K+2, ..., n}, then the game continues. The probability of j being any one of the numbers in the set {k+1, K+2, ..., n} is 1/n.
Imagine j is one of the numbers in the set {k+1, K+2, ..., n}. Before you roll again, you ask yourself "starting from this point in time, on average, how many times do I roll before the game ends?"
Well, the answer is E(j,n). This is so because if the new about-to-be-rolled number is less than or equal to j, then the game ends, otherwise it continues.
So, we can now express E(k,n) in terms of E(j,n)'s. Here's how:
E(k,n) = 1 + (k/n)*
[The first roll j<=k] + sigma{
[(1/n)*E(j,n)] as j runs from k+1 through n}.
Of course
[The first roll j<=k] tells us that in this event, there is no more rolls as the game has already ended. So,
(*1): E(k,n) = 1 + (1/n)*sigma{[E(j,n)] as j runs from k+1 through n}.
So,
(*2): sigma{[E(j,n)] as j runs from k+1 through n} = n*E(k,n) - n.
The preceding sum begins with j=k+1. So, writing a new sum in which j begins with k+2, we get:
(*3): sigma{[E(j,n)] as j runs from k+2 through n} = n*E(k+1,n) - n.
Now we will 'break up' (*1):
E(k,n) = 1 + (1/n)*(E(k+1,n) + sigma{[E(j,n)] as j runs from k+2 through n}), which in conjunction with (*3) becomes:
E(k,n) = 1 + (1/n)*( E(k+1,n) + (n*E(k+1,n) - n)), which, when simplified, becomes:`
E(k,n) = ((n+1)/n)*E(k+1,n).
O,r equivalently,
(4*): E(k,n) = (n/(n+1))*E(k-1,n).
Iterating (4*), gives us:
(5*):
E(k,n) = {(n/(n+1))^k}*E(0,n).
Now, recall that k can be any number in the set {0, 1, 2, ..., n}. So, for k=n, we do know already that E(n,n) =1. So, for k=n, (5*) gives us:
1 = E(n,n) ={(n/(n+1))^n}*E(0,n). From which we get
E(0,n) = (1+1/n)^n.
The rest is history! Cheers!
