Another week, another riddler. I really liked this one even if it was a bit linear. Ricky Jacobson’s problem reads:
You are given a fair, unweighted 10-sided die with sides labeled 0 to 9 and a sheet of paper to record your score. (If the very notion of a fair 10-sided die bothers you, and you need to know what sort of three-dimensional solid it is, then forget it — you have a random number generator that gives you an integer value from 0 to 9 with equal probability. Your loss — the die was a collector’s item.)
To start the game, you roll the die. Your current “score” is the number shown, divided by 10. For example, if you were to roll a 7, then your score would be 0.7. Then, you keep rolling the die over and over again. Each time you roll, if the digit shown by the die is less than or equal to the last digit of your score, then that roll becomes the new last digit of your score. Otherwise you just go ahead and roll again. The game ends when you roll a zero.
For example, suppose you roll the following: 6, 2, 5, 1, 8, 1, 0. After your first roll, your score would be 0.6, After the second, it’s 0.62. You ignore the third roll, since 5 is greater than the current last digit, 2. After the fourth roll, your score is 0.621. You ignore the fifth roll, since 8 is greater than the current last digit, 1. After the sixth roll, your score is 0.6211. And after the seventh roll, the game is over — 0.6211 is your final score.
What will be your average final score in this game?
This type of problem is fun because it relies on knowing expected values of lower rolls. Here is what a simple case looks like where you have a two sided die:
Value(2) #if you roll a 2 sided die:
0: (1/2) * 0
1: (1/2) * (1 + (1/10) * Value(2))
What does this mean? If you rolled a two sided die with these rules there are two possible outcomes and they each have an equal probability of coming up. The first is you roll a zero, in which case you get no additional points and the round is over. The second option is you roll a 1, in which you get one point and you get a tenth of the value of rolling another two sided die.
This is simple algebra and looks like this:
Extending it here is what the 3 sided die case looks like:
Value(3) #if you roll a 3 sided die:
0: (1/3) * 0
1: (1/3) * (1 + (1/10) * Value(2))
2: (1/3) * (2 + (1/10) * Value(3))
Now there are three options because we can roll a zero, one and two. Again, we use algebra:
This can be extended all the way to the ten sided die case:
Value(10) #if you roll a 10 sided die:
0: (1/10) * 0
1: (1/10) * (1 + (1/10) * Value(2))
2: (1/10) * (2 + (1/10) * Value(3))
3: (1/10) * (3 + (1/10) * Value(4))
4: (1/10) * (4 + (1/10) * Value(5))
5: (1/10) * (5 + (1/10) * Value(6))
6: (1/10) * (6 + (1/10) * Value(7))
7: (1/10) * (7 + (1/10) * Value(8))
8: (1/10) * (8 + (1/10) * Value(9))
9: (1/10) * (9 + (1/10) * Value(10))
This evaluates to V(10) = 100/19 = 4.7368