538 Riddler: Who Gets The $100 Bill?
11 September ’16
I modelled this week's Riddler as an absorbing Markov chain. This MC has 5 transient states (representing the dollar bill sitting in front of someone) and 5 absorbing states (which represent someone winning). The transition probability matrix is the following:
From this transition matrix we can calculate the absorbing probabilities using the following formula:Q here represents the transient-to-transient transition matrix (top left 5x5 in above matrix), and R represents the transient-to-absorbing transition matrix (top right 5x5 in the above matrix). Calculating this out, the probability of winning if the game starts at you, next to you, or two spots away from you is , , and respectively.
# number of players n <- 5 # build Q Q <- matrix(0, n, n) tri <- lower.tri(matrix(nrow=n,ncol=n)) tri.inner <- cbind(rbind(FALSE, lower.tri(matrix(nrow=n-1,ncol=n-1))), FALSE) Q[tri] <- 1/3; Q[tri.inner] <- 0; Q[n,1] <- 1/3 Q[upper.tri(Q)] <- t(Q)[upper.tri(Q)] # build R R <- matrix(0, n, n) diag(R) <- 1/3 # calculate fundamental matrix N <- solve(diag(n) - Q) # calculate absorbing probabilities B <- N %*% R print(B)
[,1] [,2] [,3] [,4] [,5] [1,] 0.45454545 0.18181818 0.09090909 0.09090909 0.18181818 [2,] 0.18181818 0.45454545 0.18181818 0.09090909 0.09090909 [3,] 0.09090909 0.18181818 0.45454545 0.18181818 0.09090909 [4,] 0.09090909 0.09090909 0.18181818 0.45454545 0.18181818 [5,] 0.18181818 0.09090909 0.09090909 0.18181818 0.45454545
The only issue with this approach is that it is tough to derive from it an expression for the general N case, unless you're unusually gifted at finding matrix inverses, which I am not. A perhaps more intuitive approach is to set up a system of equations. Because the problem is symmetrical, we need to solve for just 3 variables, the probabilities of winning with the bill 0, 1, and 2 people away. And we can relate these probabilities to one another easily since each turn is independent. Equations for the N=5, N=6, and N=7 cases:
Here are the tediously-derived solutions to the N=2 through N=10 cases:
We can use the Fibonnaci numbers to come up with general expressions for the odd and even cases:
Using the simpler odd case and some knowledge about the Fibonnaci numbers, we can see what happens as N goes to infinity: