9
$\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$
  • $\begingroup$ See OEIS A054879 $\endgroup$ – Henry Nov 29 '17 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 '17 at 14:38
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$
  • 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$ – Lord Shark the Unknown Nov 29 '17 at 8:00
  • 1
    $\begingroup$ I like that, that's sort of slick! $\endgroup$ – Brian Tung Nov 29 '17 at 8:00
12
$\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$
  • $\begingroup$ Thanks to Henry for the edit. $\endgroup$ – Brian Tung Nov 29 '17 at 7:47

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.