538 Riddler: 100-Sided Die
14 January ’17
This week's Riddler involves a game played with a 100-sided die (I seriously want one). I started by thinking about the problem as an absorbing Markov Chain with 101 states, 1 state representing the end of the game and 100 states for each potential previous roll. The transition matrix is the following:
We break this transition matrix into three components: transient-to-transient (Q), transient-to-absorbing (R), and absorbing-to-absorbing (the identity matrix by definition). Q here is simply the above matrix minus the last row and the last column (since we have just 1 absorbing state). The expected number of rolls before being absorbed when starting at each transient state is the following vector:
The expected number of rolls for the game is simply the average of the values in this vector plus 1, since we're equally likely to start at any one of these initial rolls. A little R code gives us the answer:
Q <- matrix(0, ncol=100, nrow=100) Q[upper.tri(Q,diag=TRUE)] <- 1/100 N <- solve(diag(100) - Q) t <- N %*% matrix(1, nrow=100, ncol=1) mean(t)+1
Though this gets us to the answer, it's tough to extend this approach to the general N case. Let represent the expected number of rolls until the game ends given that the previous roll was . We can develop some recurrence relations starting with and working backwards. Iterative substitution gives us an expression for :
This is analagous to the vector that we computed above. Thus, the average of through plus 1 gives us the expected number of rolls for the game. And our answer here is consistent with the absorbing Markov Chain approach above. We can also extend this logic to derive an expression for the N case. Interestingly, as N goes to infinity, the expected number of rolls converges on e!