10
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ See OEIS A054879 $\endgroup$
    – Henry
    Nov 29, 2017 at 7:47
  • $\begingroup$ 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. $\endgroup$
    – Silverfish
    Nov 29, 2017 at 14:38

2 Answers 2

16
$\begingroup$

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.).

$\endgroup$
2
  • 1
    $\begingroup$ This is the same basic idea as Brian's solution, but reducing to a two-state Markov chain instead of a four-state one. $\endgroup$ Nov 29, 2017 at 8:00
  • 1
    $\begingroup$ I like that, that's sort of slick! $\endgroup$
    – Brian Tung
    Nov 29, 2017 at 8:00
13
$\begingroup$

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}} $$

$\endgroup$
1
  • $\begingroup$ Thanks to Henry for the edit. $\endgroup$
    – Brian Tung
    Nov 29, 2017 at 7:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .