3
$\begingroup$

I got asked this as a programming interview question so the "correct" solution is via simulation, but I'm curious about the existence of an analytic solution.

Two ants start in opposing corners of an 8x8 grid and after each turn, pick a valid direction (N, S, E, W) to move uniformly randomly until they arrive on the same square. What is the expected number of moves?

It seems similar to a number of problems and looks simple enough that I feel there could be an analytic solution, but any approach that I come up with ends up having some flaw that I can't account for.

$\endgroup$
  • $\begingroup$ Did you get any answer by simulation? $\endgroup$ – gar Oct 9 '15 at 17:51
  • $\begingroup$ Yes, the solution via simulation is trivial, but not what I'm interested in. $\endgroup$ – kevmo314 Oct 10 '15 at 16:32
  • $\begingroup$ Okay, wanted to verify my simulation first before going with the analytic one. I am getting about 200 turns, is it what you get too? $\endgroup$ – gar Oct 10 '15 at 17:09
  • $\begingroup$ Ah, I got ~82 turns. I verified this was correct with someone else who wrote the simulation as well. I don't want to share my code since this is an interview question, but someone posted theirs on a similar question here: gist.github.com/dhalik/51a5c0dc621a43d3bb94 $\endgroup$ – kevmo314 Oct 10 '15 at 19:13
  • $\begingroup$ Hmm, then it's mistake with my code. Result of that code is close to my analytical answer for a 3x3 board ($\frac{234}{37} \approx 6.324$) $\endgroup$ – gar Oct 11 '15 at 3:02
1
$\begingroup$

In principle you can do this using a (rather large) Markov chain. You have $64^2$ states of the form $(i,j,k,l)$ indicating that the ants are at $(i,j)$ and $(k,l)$. If $A$ is the transition matrix then I think you'll need to look at $\frac{d}{dt}(I-tA)^{-1}$ at $t=0$. But $A$ is a $4096\times4096$ (sparse) matrix, so this is a challenge. It would make a great programming problem! 😀

$\endgroup$
  • $\begingroup$ It should have a simpler solution.. On the second thought, not very likely. $\endgroup$ – zhoraster Oct 8 '15 at 15:47
  • $\begingroup$ @zhoraster actually I think it does. The ways for ants to meet at time $t$ correspond to paths of length $2t$ from the lower left corner to the upper right. So you only need to consider $64$ states! I'll update when I get time. $\endgroup$ – Tad Oct 8 '15 at 19:23
  • $\begingroup$ But don't forget that these are very special paths, with certain self-avoidance. $\endgroup$ – zhoraster Oct 8 '15 at 19:25
  • $\begingroup$ @Tad how would you invert that matrix in a reasonable amount of time? An O(n^3) algorithm would be rather slow. I could see maybe doing it via Cholesky factorization though? $\endgroup$ – kevmo314 Oct 10 '15 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.