2

In a interview i had something similar to this question Random walk on the edges of a cube. But this time there is only a ant, it takes one minute to go through a single edge. The ant can use the same edge several times in a row. The question was : on average, how long it would take for the ant to come back to the initial corner ?

TmSmth
  • 359
  • 2
  • 5
  • The referenced question already did the work: it tells you, from any position on the cube, the expected time to return to the original corner. The ant takes one minute to advance to one of those positions, so *read off the answer and add one to it.* – whuber Feb 21 '19 at 00:08
  • "the ant takes one minute to advance to one of those positions" : is it an average time ? For example if the ant goes to the opposite corner it would take 3 minutes on top of the 10 found in the reference question – TmSmth Feb 21 '19 at 09:10
  • 1
    All that matters is the first step, which takes one minute. At that point the ant is on a different vertex and solving this problem thereby comes down to the expected time to reach the starting vertex from that one--and the answer is given in the referenced thread. – whuber Feb 21 '19 at 12:59

1 Answers1

3

Here's a simple approach:

Imagine the ant performing its random walk on the cube for a long time (ignoring for a moment that you are interested in the time until the return to the origin point).

By symmetry the expected proportion of time the ant will be at each corner is $1/8.$ So on average the time between visits to the origin must therefore be 8 steps.

Since it's one minute per step, the expected time until the return to the origin is 8 minutes.

soakley
  • 4,341
  • 3
  • 16
  • 27
  • Could you explain this please : "By symmetry the expected proportion of time the ant will be at each corner is 1/8" ? Is it just the fact that the ant walks at a constant speed and at some point it will visit the 8 corners ? – TmSmth Feb 24 '19 at 15:29
  • 1
    It's similar to a coin flip. If you flip a fair coin repeatedly, the long-term proportion of heads is 50 percent. So the expected time until I flip a head is 2 flips. For the cube problem, you could approach it more formally and set it up as a Markov chain and construct the transition matrix over the corners. You will find that the transition matrix is doubly stochastic, which implies the chain is at each corner an equal proportion of time. – soakley Feb 25 '19 at 19:15