Random Walk and Absorption Times on a Hypercube

Scenario In quantitative trading and quantitative research, candidates are frequently evaluated on probability modeling, specifically regarding Spectral Graph Theory / Markov Chains.

Your Task
A random walk starts at vertex $(0, 0, \dots, 0)$ of the $d$-dimensional hypercube $\{0, 1\}^d$. At each step, one of the $d$ coordinates is chosen uniformly at random and flipped. Let $\tau$ be the hitting time of the opposite vertex $(1, 1, \dots, 1)$. Compute the expected time $\mathbb{E}[\tau]$.

Constraints

• Transitions and increments satisfy the Markov or martingale property with respect to natural filtration.
• Stopping times are almost surely finite.