Random walk over a cube:Probability of returning back

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

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