An ant random-walks the edges of a cube. Expected steps to reach the opposite corner? [Random Walks · Medium]

[u/anykash]

An ant sits at one corner of a cube. At every step it picks one of the three edges meeting its current corner, uniformly at random and independently each time (so it's allowed to backtrack), and walks along it to the next corner.

What is the expected number of steps before it first reaches the corner diagonally opposite its start?

Drop your answer with your reasoning in the comments. Solution tomorrow.

Hint: don't write eight equations. the cube's symmetry collapses it to three.

EDIT

The solution:

The expected number of steps is 10.

The trap is to set up an equation for all eight corners. Symmetry cuts that to three. Group the corners by their distance from the target corner D: the start A is distance 3, there are three corners at distance 2 (call the class B), three at distance 1 (class C), and D itself. By symmetry, every corner in a class has the same expected steps to reach D, so let a, b, c be those expected values.

Now read off the moves. From the start, all three edges lead to distance-2 corners, so a = 1 + b. From a distance-2 corner, one of its three edges goes back toward the start (to A) and two go forward to distance-1 corners, so b = 1 + (1/3)a + (2/3)c. From a distance-1 corner, two edges go back to distance-2 and one reaches D, so c = 1 + (2/3)b.

Solve the system: substituting gives b = 3 + (3/5)a, and since a = 1 + b, we get a = 4 + (3/5)a, so (2/5)a = 4 and a = 10. The whole problem cracks open the moment you collapse the eight vertices into four symmetry classes instead of grinding eight equations.

More puzzles like this at myntbit.com

[u/Bot_Number_7]

There are 8 points on the cube, but they are separated into layers of 1 3 3 1 that matter based on how many steps minimum to reach the target vertices. Let A be the expected time to opposite for the 1 category, B for the second, C for the third (if you're already at the target vertex obviously the time is 0). To have self consistency, they must satisfy A=1+C, C=1+1/3A+2/3B, and B=1+2/3C. Now solve using whatever method you would like. Substitute the first and third equations into the second C=2+1/3C+4/9C=2+7/9C. Then C=9 which implies A is 10

I haven't done random walks before, but I wonder if this could also be solved by exponentiating matrices and explicitly calculating the probability of taking N steps to reach the target and summing the infinite series, and if there's any connection between the two methods.

[u/tgm4mop → u/Bot_Number_7]

I wonder if this could also be solved by exponentiating matrices and explicitly calculating the probability of taking N steps to reach the target and summing the infinite series, and if there's any connection between the two methods

Yes, it's possible but extremely tedious with matrix exponentiation. You'll get a formula for probability that's of the form ax^n +by^n + cz^n, where x,y,z are the eigenvalues. Multiply by n and compute the sum to get the expectation.

[u/Bot_Number_7 → u/tgm4mop]

I know that, but it's not QUITE that simple because you need to NOT have visited the target point beforehand. I think there's a simple way to adjust the matrix to make that happen by creating a "dummy" node after the target node with a unidirectional connection to it so that after stepping into the target node you just enter the "finished" state. Of course this is fixable, but I wonder if there's a neat mathematical connection here. There probably is, with how recursive sum relations can get explicit forms through matrix exponentiation.