# Expected hitting times for simple random walk on a hypercube

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

• An alternative way to compute this once you know that $t_1 = 2^n - 1$ and $t_2 = \frac{n(2^n - 2)}{n-1}$ is to write $t_2 = 1 + \frac{2}{n} t_1 + \frac{n-2}{n} t_3$ and solve for $t_3.$
– Roy
Commented Sep 5, 2023 at 12:01

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)$$
$$t_3= \frac{(n^2-2n+2)2^n-(6n-4)}{(n-1)(n-2)} - 3.$$