# Random walk over a cube:Probability of returning back

There is a cube and an ant is performing a random walk on the edges where it can select any of the 3 adjoining vertices with equal probability. What is the probability that ant is in the vertex it started with after N steps?

What I tried->

Breaking problem to simpler one where we see distance from start vertex. So out of 8 vertices, we have 1 with distance 0(our start), 3 with distance 1, 3 with distance 2 and 1 with distance 3.

Also, ant can only return back if N is even. So probability is 0 when N is odd.

• See OEIS A054879 – Henry Nov 29 '17 at 7:47
• Closely related to a question on Cross Validated: Random walk on the edges of a cube though that focuses on expected number of moves rather than probabilities, and on reaching the opposite rather than original corner. – Silverfish Nov 29 '17 at 14:38

The probability is zero if $N$ is odd.

After two steps, starting at the original vertex, the probability of returning there is $1/3$. Otherwise the walk moves to a vertex at distance $2$ from the original vertex.

Starting at a vertex at distance $2$ from the original vertex, after two steps the probability it returns to the original vertex is $2/9$. Otherwise it moves to a vertex at distance $2$ from the original vertex.

So the probability of return after $2n$ steps is the top left entry of the matrix $$\pmatrix{1/3&2/3\\2/9&7/9}^n.$$ You can compute this by any standard method (diagonalisation, generating functions, etc.).

• This is the same basic idea as Brian's solution, but reducing to a two-state Markov chain instead of a four-state one. – Lord Shark the Unknown Nov 29 '17 at 8:00
• I like that, that's sort of slick! – Brian Tung Nov 29 '17 at 8:00

Basic approach. I'd take advantage of some symmetries here. There are three vertices at distance $1$ from the start, three vertices at distance $2$ from the start, and one vertex at distance $3$ from the start. Show that the distance of the vertex from the start is represented by a four-state Markov chain with the following transition probabilities:

$$p_{01} = 1$$ $$p_{10} = \frac13, p_{12} = \frac23$$ $$p_{21} = \frac23, p_{23} = \frac13$$ $$p_{32} = 1$$

Represent this as the matrix $P$. Then if we denote the initial probability distribution as $\pi = [1 \quad 0 \quad 0\quad 0]^\text{T}$, then $P^N\pi$ represents the probability distribution of the system after $N$ steps, and the probability of being in the start position after $N$ steps can be read off as the first element of the resulting probability vector (i.e., the upper-left element of the matrix). As you correctly point out, the obvious parity argument shows that the answer must be $0$ for odd $N$.

Matrix exponentiation shows that the result is

$$\frac14+\frac{1}{4\times3^{N-1}}$$

• Thanks to Henry for the edit. – Brian Tung Nov 29 '17 at 7:47