Past exam of the mathematics course of the University of Cambridge / 2018 / ib / Paper 2 / 20H / ii / Solution

Let $h$ be the expected hitting time from any neighbour of the origin back to the origin. After the first step, the return-time calculation from part (i) givesso $h=2^n-1$. Translation by the target vertex is a graph automorphism of the hypercube that exchanges the origin and that adjacent vertex, so the reverse expected hitting time is the same. Hence