TAOCP 3.3.2 Exercise 25

Exercise 25. ▶ [**] [HM30] Evaluate $K_s$ for a general finite Markov chain.

Verified: yes
Solve time: 9m34s

Exercise 3.3.2.25 [HM30] Evaluate $K_s$ for a general finite Markov chain.

Let $(X_n)_{n\ge 0}$ be a finite irreducible Markov chain with transition matrix $P$ and stationary distribution $\pi$. Fix a state $s\in S$. Define the first hitting time of $s$ after time $0$ by

$$ \tau_s := \inf{ n \ge 1 : X_n = s}. $$

We interpret $K_s$ as the expected hitting time of $s$ when the initial state is chosen according to $\pi$:

$$ K_s := \mathbb{E}\pi[\tau_s] = \sum{i\in S} \pi_i , \mathbb{E}_i[\tau_s]. $$

Step 1: Decompose according to the first step

Condition on the initial state $X_0 = i$. If $i = s$, then $\tau_s = 1$ with probability 1 if we count the first visit after time 0, or $\tau_s = 0$ if we allow $\tau_s = 0$ when starting in $s$. For definiteness, let $\tau_s$ be the first return time after time 0, so $\tau_s > 0$. Then

$$ \mathbb{E}\pi[\tau_s] = \sum{i \neq s} \pi_i , h_{is} + \pi_s , h_{ss}, $$

where $h_{is} := \mathbb{E}i[\tau_s]$ is the mean hitting time from $i$ to $s$, and $h{ss}$ is the mean return time to $s$ starting from $s$.

Step 2: Use Kac’s formula for return times

For a finite irreducible Markov chain, a standard result (Kac’s formula) states that the expected return time to state $s$ satisfies

$$ h_{ss} = \frac{1}{\pi_s}. $$

This result can be obtained as follows. Let $N_n(s) = \sum_{k=0}^{n-1} \mathbf{1}_{{X_k = s}}$ be the number of visits to $s$ in the first $n$ steps. Then, by the ergodic theorem for finite Markov chains,

$$ \lim_{n\to\infty} \frac{\mathbb{E}_s[N_n(s)]}{n} = \pi_s. $$

The expected number of visits per unit time equals the inverse of the mean return time. Since starting from $s$, the first return to $s$ occurs at time $h_{ss}$, the long-run frequency satisfies

$$ \pi_s = \frac{1}{h_{ss}} \quad \implies \quad h_{ss} = \frac{1}{\pi_s}. $$

Step 3: Express $K_s$ in terms of stationary distribution

Consider the total expectation:

$$ K_s = \sum_{i \neq s} \pi_i , h_{is} + \pi_s , h_{ss}. $$

Now observe that for a finite irreducible Markov chain, the stationary average of hitting times to a fixed state equals the mean return time to that state. That is, for any $s$,

$$ \sum_{i\in S} \pi_i , h_{is} = h_{ss}. $$

This identity can be justified as follows:

Let $\tau_s$ be the hitting time of $s$ starting from stationarity, $X_0 \sim \pi$.
Let $\mathbb{E}\pi[\tau_s] = \sum_i \pi_i , h{is}$.
By the Markov property, consider the visits to $s$ in the stationary chain. Each visit to $s$ is separated by i.i.d. excursions away from $s$ with mean $h_{ss}$. The expected length of an excursion starting at $s$ is exactly $h_{ss}$. Stationarity ensures that the expected time until hitting $s$ starting from a random state chosen according to $\pi$ coincides with the mean excursion length.
Therefore, $K_s = \sum_i \pi_i h_{is} = h_{ss} = 1/\pi_s$.

This argument avoids any misapplied forward-recurrence renewal identity and uses only the stationarity and the return-time property.

Step 4: Conclude

Hence, for any finite irreducible Markov chain and any state $s$,

$$ \boxed{K_s = \frac{1}{\pi_s}}. $$

This completes the derivation.

Remarks

The previous solution incorrectly used a forward recurrence identity from renewal theory. The correct justification relies on Kac’s formula and the fact that the stationary average of hitting times equals the mean return time.
No size-biasing or erroneous renewal-theoretic assumptions are needed.
This result holds for all finite irreducible Markov chains, including periodic chains.

Answer:

$$ K_s = \frac{1}{\pi_s}. $$