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

Measure vertices by their Hamming distance from the target and let $h_k$ be the expected hitting time when that distance is $k$. We already know $h_1=2^n-1$. From distance one, one of the $n$ coordinate flips reaches the target and the other $n-1$ flips move to distance two. First-step analysis therefore givesFor $n\ge 2$,