Expected Steps to Reach Opposite Corner of a 3D Cube

Scenario

A particle performs a simple random walk on the vertices of a 3-dimensional cube $\{0, 1\}^3$. Starting at origin $(0, 0, 0)$, at each step the particle chooses one of the 3 adjacent vertices uniformly at random (each with probability $1/3$).

Your Task

1. By exploiting vertex symmetry, reduce the 8-vertex state space to 4 distance equivalence classes based on Hamming distance $d \in \{0, 1, 2, 3\}$ to the target $(1, 1, 1)$ or start $(0, 0, 0)$.
2. Formulate the system of first-step expected hitting time equations.
3. Solve the system to determine the exact expected number of steps required to reach the diagonally opposite vertex $(1, 1, 1)$ for the first time.

Constraints

• Symmetric 3-regular graph walk.
• Target vertex $(1, 1, 1)$ is absorbing.

Examples From distance 2, 2 of 3 moves stay at distance 1 or 2, and 1 move reaches the target.