DonaldRauscher.com

A Blog About D4T4 & M47H

538 Riddler: A Variation of the Drunkard's Walk ... In a Bar

14 July ’16

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")