This week’s Riddler is a variation on the well-known OR problem, the drunkard’s walk. We can model this problem as an absorbing Markov Chain with X+Y+1 states. The transition probability matrix is the following:
Once we compute the fundamental matrix (N), calculating the expected number of steps until absorption is fairly easy. Plugging in a few different values of X and Y, a trend emerges: the expected number of coin flips is simply XY. Beautiful.
X <- 4 Y <- 13 # build Q n_transient_state <- X + Y - 1 Q <- matrix(0.5, n_transient_state, n_transient_state) tri <- cbind(rbind(FALSE, lower.tri(matrix(nrow=n_transient_state-1,ncol=n_transient_state-1))), FALSE) Q[tri] <- 0; Q[t(tri)] <- 0; diag(Q) <- 0 # build R R <- matrix(data = 0, nrow = n_transient_state, ncol = 2) R[1,1] <- 0.5 R[n_transient_state,2] <- 0.5 # put together into P P <- rbind(cbind(Q, R), cbind(matrix(0, 2, n_transient_state), diag(2))) # fundamental matrix N <- solve(diag(n_transient_state) - Q) # expected number of steps to absorbtion t <- N %*% matrix(1, n_transient_state, 1) ggplot() + geom_line(aes(x=-(X-1):(Y-1), y=t)) + geom_point(aes(x=0, y=t[X]), colour="red", size=1) + geom_text(aes(x=0, y=t[X], label=t[X]), colour="red", nudge_y=2) + xlab("Starting Point") + ylab("Expected Game Length")