Inspired by Alan Yan

Let's make the coordinates of the vertices all 0's and 1's, for simplicity, and let's say that Markov is at A(0,0,0) initially. Since the number of 1's changes by one each time he moves along an edge, after an even number of moves he will be at one of the points $A(0,0,0),B(1,1,0),C(1,0,1)$ and $D(0,1,1)$ .

Let $p_{2n}$ be the probability that he is at $A$ after $2n$ moves and $q_{2n}=1-p_{2n}$ the probability that he is at one of the points $B,C$ or $D$ . The rules of the game and the geometry of the cube imply that $p_{2n+2}=\frac{1}{3}p_{2n}+\frac{2}{9}q_{2n}=\frac{1}{9}p_{2n}+\frac{2}{9}$

If we write the probability as a deviation from the equilibrium, $p_n=\frac{1}{4}+d_n$ , we find that $d_{n+2}=\frac{1}{9}d_n$ and $p_{2n}=\frac{1}{4}\left(1+\frac{1}{3^{2n-1}}\right)$

For $n=5$ we have $p_{10}=\frac{(3^9+1)/4}{3^9}=\frac{\boxed{4921}}{3^9}$

Interesting to represent computationally.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from collections import defaultdict
from itertools import chain
from fractions import Fraction

A,B,C,D,E,F,G,H=range(1,9)

edges=[ [1,2], [1,7], [1,3], [2,4], [2,8], [8,6], [8,7], [7,5], [3,4], [3,5], [4,6], [6,5] ]

initialLength=len(edges)
for i,j in edges[:initialLength]:
    edges.append([j,i])

choices=defaultdict(list)
for i,j in edges:
    choices[i].append(j)

sequence=[1]
numberMoves=10
for moveNumber in range(1,1+numberMoves):
    sequence = list(chain(*[choices[s] for s in sequence]))

probability=Fraction(sequence.count(1),len(sequence))
print probability