6
$\begingroup$

Here I present an extension to the famous ant on a cube question:

Two ants, A and B, are placed on diametrically opposite corners of a cube. With every step, each ants move from one vertex to an adjacent vertex (with 1/3 probability of moving along each of the joining edges). What is i) the probability that A and B collide before either ant reaches the diametrically opposite corner; and ii) the expected number of steps before they collide?

I fully understand how the law of iterated expectations work for a single ant reaching the diametrically opposite corner, however I am unsure of how to extend it for this case. I read in a separate question (lost the link sadly, please edit if you find it) about two players meeting on a random walk, and how characteristic functions were involved, but I did not really understand it. Could someone provide some insight? Cheers!

Edit: second part makes more sense after drawing the Markov chain, could someone prod me in the right direction for constructing the Markov chain for the first part?

$\endgroup$
  • 4
    $\begingroup$ How are the ants travelling across the cube? How fast are they moving? $\endgroup$ – Parcly Taxel Feb 5 at 4:11
  • $\begingroup$ @ParclyTaxel updated! $\endgroup$ – user107224 Feb 5 at 12:20
  • 2
    $\begingroup$ Note that the cube is a bipartite graph so you can color the corners like a checker board. At the beginning the ants are on opposite colors and with each step they move to a corner of the opposite color. This means the ants can never be at the same corner at once. They can only collide if they start out at adjacent vertices and then try to switch positions. $\endgroup$ – quarague Feb 5 at 12:39
3
$\begingroup$

Great question. Here is an answer for ii) but I don't know what is the best way to approach i).

In light of quarague's comment, there are only two possible situations after each time step

A) The ants are on diametrically opposite corners of the cube

B) The ants are on opposite corners of the same edge.

Denoting the expected time to collision in both cases by $E_A$ and $E_B$ respectively we get the equations

$E_A = 3/9 * (1+E_A) + 6/9 * (1 + E_B)$

$E_B = 1/9*1 + 6/9 * (1 + E_B) + 2/9 * (1 + E_A)$

just by writing out the 9 possible movements of the ants in both situations.

Now we can solve these to get $E_A$ which is the answer to your question ii.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hi, shouldn’t the probabilities for the second equation be 1/5, 2/5 and 2/5? $\endgroup$ – user107224 Feb 5 at 18:30
  • $\begingroup$ I don't think so. Perhaps you forgot to count the two cases where ant 1 moves to the spot now occupied by ant 2 while at the same time ant 2 moves away from that spot but not along the same edge that ant 1 is moving so that at the end of the time step we are back in situation B (but on a different place)? And then of course there are two more possibilities where ant 2 moves to the place now occupied by ant 1 while ant 1 moves away $\endgroup$ – Vincent Feb 5 at 18:34
  • $\begingroup$ good point, thank you! I am attempting to construct a markov chain with your approach, could this work for the first part? $\endgroup$ – user107224 Feb 5 at 18:41
  • $\begingroup$ I think yes. But for the first state there is much less symmetry and hence much more different states to consider. $\endgroup$ – Vincent Feb 5 at 22:35
  • $\begingroup$ Sorry I meant: for the first question there are much more different states to consider. But it is doable if you have pen and paper $\endgroup$ – Vincent Feb 5 at 23:21

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.