Section 15.1

Hitting and Return Times

Expected steps to reach or return to a state of a finite chain: walks on cube vertices, two-state chains, flipping matrix entries.

Toolkit

Hitting and return times are computed via first-step (one-step) analysis: condition on the outcome of the first transition and set up linear equations for the expected number of steps.

First-step equations: for hitting time $h_i=\mathbb{E}[\text{steps to target}\mid X_0=i]$ ,

h_i = 1+\sum_j p_{ij}h_j,\qquad h_{\text{target}}=0.

Exploit symmetry: lump states into equivalence classes (e.g. by distance to the target on a vertex-transitive graph) to shrink the system to a few unknowns.
Return time to a state $i$ satisfies $m_i = 1+\sum_j p_{ij}h_j$ , where $h_j$ is the hitting time from $j$ to $i$ ; for an irreducible chain with stationary distribution $\pi$ ,

m_i = \mathbb{E}[\text{return time to } i] = \frac{1}{\pi_i}.

For two-state chains with transition probabilities $p,q$ , return and hitting times solve directly from one equation each.

Problems