Setup
In an $n$-dimensional hypercube $C_n = \{0,1\}^n$, we define the Hamming distance of two vertices $d(A,B)$ to be the number of coordinates in which they differ. (e.g. $d((0,0,1), (1,0,1)) = 2$.)
A simple random walk on the vertices of $C_n$ has $1/n$ chance of moving to each of the $n$ adjacent vertices.
Problem
I am trying to find some expected hitting times $t_d$, where
A and B are given (fixed) vertices of $C_n$,
$d = d(A, B)$, and
$$t_d = \mathbb{E}(\text{time to hit B starting from A}).$$
For example, $t_0$ is the expected return time.
My attempts
Using the inverse of the invariant distribution, we get
$$t_0 = 2^n.$$
To find $t_1$, we try to express $t_0$ in another way, by conditioning on the first step:
$$t_0 = \underbrace{\frac1n \times (1+t_1) + \ldots + \frac1n \times (1+t_1)}_{n\text{ terms}} $$
$$ \Rightarrow t_1 = 2^n – 1.$$
Similarly, we can find $t_2$. Note that the only outcomes after two steps are i) returning, and ii) being $d = 2$ away from the start.
$$t_0 = \frac1n \times 2 + \frac{n-1}n \times (2+t_2) $$
$$\Rightarrow t_2 = \frac{n2^n-2}{n-1}-2 = \frac{n(2^n – 2)}{n-1}.$$
Why do I need help
To find $t_3$, I try to do the same trick. However, I suspect I have made a mistake.
$$t_0 = \frac1n \times 2 + \frac{n-1}{n}\frac1n \times (3+t_1) + \frac{n-1}{n}\frac{n-1}{n}\times (3+t_3)$$
This gives $t_3 = 8.5$ when $n = 3$ (a cube), contradicting this question, which says that $t_3 = 10$ in this case.
Best Answer
Suppose you’re at distance 2 at 2nd step. Then, there’s two (not one) way of getting to a vertex at distance 1. (Distances are relative to the starting vertex).
Now, $$t_0 = \frac1n \times 2 + \frac{n-1}{n}\frac2n \times (3+t_1) + \frac{n-1}{n}\frac{n-2}{n}\times (3+t_3)$$
which gives
$$t_3= \frac{(n^2-2n+2)2^n-(6n-4)}{(n-1)(n-2)} - 3.$$