Expected Hitting Time of a Birth-Death Chain
A Markov chain has states $1, 2, \ldots, n$. From state $i$, the chain moves to $i+1$ with probability $p$, to $i-1$ with probability $q$, and stays at $i$ with probability $1 - p - q$. State 1 has a reflecting boundary (a leftward step from state 1 keeps you at state 1).
Let $h_i$ denote the expected number of steps to reach state $n$ starting from state $i$.
- Set up and solve the recurrence for $h_i$ in terms of $p$ and $q$ (with $p \ne q$).
- Solve the symmetric case $p = q = 1/2$ and express $h_1$ as a closed-form function of $n$.
- How does the "stay" probability $1 - p - q$ affect the answer?
Hints
- Write the one-step recurrence $h_i = 1 + p \cdot h_{i+1} + q \cdot h_{i-1} + (1 - p - q) \cdot h_i$ and notice what cancels.
- Define the differences $d_i = h_i - h_{i+1}$. The recurrence becomes first-order: $d_i = (q/p) \cdot d_{i-1} + 1/p$. For $p = q$, this is just $d_i = d_{i-1} + 2$.
- The reflecting boundary at state 1 gives you the initial condition $d_1 = 1/p$. Sum $d_1 + d_2 + \cdots + d_{n-1}$ to get $h_1$.
Worked Solution
How to Think About It: This is a classic birth-death chain / gambler's ruin hitting-time problem. Before doing any algebra, think about the physics. You are doing a random walk on $\{1, \ldots, n\}$ and need to reach the far end. In the symmetric case ($p = q$), there is no drift, so you are wandering aimlessly -- the hitting time should grow like $n^2$ (diffusive scaling). In the biased case ($p > q$), you have a net rightward drift of $p - q$ per step, so the hitting time should be roughly $(n-1)/(p-q)$ (ballistic scaling). The "stay" probability just wastes time without changing direction, so it slows you down but the algebra will absorb it naturally.
Quick Estimate: Take $n = 10$, $p = q = 0.5$. The answer should scale as $n^2$, so roughly $10 \times 9 = 90$ steps. For a biased walk with $p = 0.6$, $q = 0.3$, the drift is $0.3$ per step, so roughly $(10-1)/0.3 = 30$ steps. These ballpark numbers will help us sanity-check the exact formulas.
Approach: Let $h_i = E[T_n \mid X_0 = i]$. Write the one-step recurrence, simplify, and solve as a first-order recurrence in the differences $d_i = h_i - h_{i+1}$.
Formal Solution:
*Step 1: Recurrence.* For $2 \le i \le n - 1$:
$$h_i = 1 + p \cdot h_{i+1} + q \cdot h_{i-1} + (1 - p - q) \cdot h_i$$
The $(1 - p - q) \cdot h_i$ on the right cancels part of the left side:
$$(p + q) \cdot h_i = 1 + p \cdot h_{i+1} + q \cdot h_{i-1}$$
Rearranging:
$$p(h_{i+1} - h_i) - q(h_i - h_{i-1}) = -1$$
*Step 2: Boundary conditions.* At state $n$: $h_n = 0$. At state 1 (reflecting): a leftward move keeps you at 1, so
$$h_1 = 1 + p \cdot h_2 + (1 - p) \cdot h_1$$
which gives $p(h_1 - h_2) = 1$, i.e., $d_1 = 1/p$ where $d_i = h_i - h_{i+1}$.
*Step 3: Solve the differences.* Define $d_i = h_i - h_{i+1}$. The recurrence becomes $-p \cdot d_i + q \cdot d_{i-1} = -1$, or
$$d_i = \frac{q}{p} \cdot d_{i-1} + \frac{1}{p}$$
Let $r = q/p$. Iterating from $d_1 = 1/p$:
$$d_i = \frac{1}{p} \cdot \frac{r^i - 1}{r - 1} \quad \text{for } r \ne 1$$
Verification: $d_1 = \frac{1}{p} \cdot \frac{r - 1}{r - 1} = \frac{1}{p}$. Check.
*Step 4: Sum to get $h_1$.* Since $h_1 = \sum_{i=1}^{n-1} d_i$:
$$h_1 = \frac{1}{p(r - 1)} \sum_{i=1}^{n-1} (r^i - 1) = \frac{1}{p(r - 1)} \left[ \frac{r(r^{n-1} - 1)}{r - 1} - (n - 1) \right]$$
Substituting $r = q/p$ and $p(r - 1) = q - p$:
$$h_1 = \frac{n - 1}{p - q} - \frac{q\left[1 - (q/p)^{n-1}\right]}{(p - q)^2} \quad \text{for } p > q$$
and similarly for $p < q$ (with sign adjustments).
*Step 5: Symmetric case $p = q = 1/2$.* When $r = 1$, the difference recurrence becomes $d_i = d_{i-1} + 2$, giving $d_i = 2i$. Therefore:
$$h_1 = \sum_{i=1}^{n-1} 2i = 2 \cdot \frac{(n-1)n}{2} = n(n - 1)$$
*Step 6: Role of the stay probability.* The probability $1 - p - q$ of staying put drops out of the recurrence entirely. It does not appear in the final answer. This makes sense: staying in place adds one step but does not change your position, and the recurrence already accounts for the expected number of steps. Formally, the $(1 - p - q) h_i$ terms cancel when you move them to the left side. The expected hitting time depends only on $p$ and $q$ (or equivalently, on their ratio $q/p$ and their sum $p + q$).
Answer: For $p = q = 1/2$, the expected hitting time from state 1 to state $n$ is
$$h_1 = n(n - 1)$$
For general $p \ne q$:
$$h_1 = \frac{n - 1}{p - q} - \frac{q\left[1 - (q/p)^{n-1}\right]}{(p - q)^2}$$
The stay probability $1 - p - q$ does not affect the answer.
Intuition
This problem illustrates the dramatic difference between diffusive and ballistic transport. A symmetric random walk has no drift, so reaching a target $n-1$ steps away takes $O(n^2)$ time -- the walker keeps backtracking and revisiting old ground. Add even a tiny rightward bias ($p > q$) and the hitting time drops to $O(n)$, scaling like $(n-1)/(p-q)$. This is the same principle behind why a market maker with a small edge accumulates P&L linearly over time, while a fair game (zero edge) produces P&L that grows only as $\sqrt{T}$.
The surprising detail is that the stay probability $1 - p - q$ has zero effect on the expected hitting time. Intuitively, staying in place wastes a step but contributes exactly one step to the expectation each time it happens, and the recurrence already prices that in. What matters is the ratio of rightward to leftward jumps, not how often you pause. This is analogous to how a trader's long-run performance depends on win rate versus loss rate, not on how many days the market is closed.