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. 
 A: 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.).
A: 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}}
$$
