Expected Times To Hit A Boundary

Expected Time Is Not the Number of Jumps

For a continuous-time birth-death chain, the expected time to reach a boundary depends on two ingredients: which direction the next jump takes, and how long the chain waits before that jump. First-step equations account for both. On a finite interval, those equations reduce to a recurrence for differences of expected hitting times, which can be solved from the reflecting endpoint toward the target.

Let $(X_t)_{t\ge0}$ be a continuous-time Markov chain on $S=\{0,1,\ldots,N\}$, defined on a probability space $(\Omega,\mathcal F,\mathbb P)$, with its natural filtration $(\mathcal F_t)_{t\ge0}$. At state $i$, the chain jumps to $i+1$ at rate $\lambda_i$ and to $i-1$ at rate $\mu_i$, when those states are in $S$. Consider first the time to reach the upper boundary $N$. Assume $N\ge1$, $\lambda_i>0$ for $0\le i<N$, and $\mu_i>0$ for $1\le i<N$, with all rates finite. At 0 there is no downward jump; at $N$ the process can be stopped when it is reached. Write $\mathbb P_i$ and $\mathbb E_i$ for probability and expectation given $X_0=i$, and set $T_N=\inf\{t\ge0:X_t=N\}$.

Definition: The generator acts on a function $f:S\to\mathbb R$ by $(Qf)(i)=\sum_{j\ne i}q_{ij}(f(j)-f(i))$. For a birth-death chain at an interior state $i$, this is $(Qf)(i)=\lambda_i(f(i+1)-f(i))+\mu_i(f(i-1)-f(i))$. At 0 it is $(Qf)(0)=\lambda_0(f(1)-f(0))$.

The expected time $t_i=\mathbb E_i[T_N]$, when finite, must satisfy $t_N=0$ and $(Qt)(i)=-1$ at every state below $N$. The right-hand side is $-1$, not a jump probability: elapsed time accumulates continuously, including during each holding time.

First-Step Equations and Their Solution

Theorem: Under the finite-state and positive-rate assumptions above, $T_N$ has finite expectation from every state. Its expectations $t_i=\mathbb E_i[T_N]$ are the unique finite solution of $$ t_N=0,\qquad \lambda_0(t_1-t_0)=-1, $$ and, for $1\le i<N$, $$ \lambda_i(t_{i+1}-t_i)+\mu_i(t_{i-1}-t_i)=-1. $$ Equivalently, set $\Delta_i=t_i-t_{i+1}$. Then $$ \Delta_0=\frac1{\lambda_0},\qquad \Delta_i=\frac{1+\mu_i\Delta_{i-1}}{\lambda_i}\quad(1\le i<N), \qquad t_i=\sum_{k=i}^{N-1}\Delta_k. $$

Proof. First we establish finiteness so that taking expectations in a first-step decomposition is justified. Consider the embedded jump chain, which records the states visited at jumps. From any state $i<N$, the route $i,i+1,\ldots,N$ reaches $N$ in at most $N$ jumps. At each state $k<N$, the probability that the next jump is upward is $\lambda_k/(\lambda_k+\mu_k)$, where $\mu_0=0$. Thus the probability of following the upward route from $i$ is a product of finitely many strictly positive factors. Since there are finitely many starting states, the minimum $\delta$ of these route probabilities is strictly positive. Conditional on not yet hitting $N$, the chance to hit it within the next $N$ jumps is therefore at least $\delta$. Consequently, the probability that more than $mN$ jumps are needed is at most $(1-\delta)^m$, and the expected number of jumps is finite.

At each state below $N$, the total jump rate $q_i=\lambda_i+\mu_i$ (with $\mu_0=0$) is positive. The expected holding time there is $1/q_i$, which is at most $C=\max_{i<N}1/q_i<\infty$. If $J$ is the number of jumps before reaching $N$, summing the conditional expected holding times over the visits before absorption gives $\mathbb E_i[T_N]\le C\mathbb E_i[J]<\infty$.

Now condition on the first holding time and jump. At state $i<N$, the holding time has mean $1/q_i$, and the next state is $i+1$ with probability $\lambda_i/q_i$ and $i-1$ with probability $\mu_i/q_i$, omitting the downward option at 0. The Markov property gives, for $1\le i<N$, $$ t_i=\frac1{q_i}+\frac{\lambda_i}{q_i}t_{i+1}+\frac{\mu_i}{q_i}t_{i-1}. $$ Multiplying by $q_i$ and rearranging gives the stated generator equation. At 0 the same argument gives $t_0=1/\lambda_0+t_1$, hence $\lambda_0(t_1-t_0)=-1$. Also $t_N=0$ because the hitting time is zero when starting at $N$.

To solve, put $\Delta_i=t_i-t_{i+1}$. The equation at 0 gives $\lambda_0\Delta_0=1$. At an interior state, $t_{i+1}-t_i=-\Delta_i$ and $t_{i-1}-t_i=\Delta_{i-1}$, so its equation becomes $-\lambda_i\Delta_i+\mu_i\Delta_{i-1}=-1$. This is exactly the recurrence in the theorem. Finally, since $t_N=0$, telescoping gives $t_i=\sum_{k=i}^{N-1}\Delta_k$.

For uniqueness, suppose two finite solutions exist and let $h_i$ be their difference. Then $h_N=0$, $\lambda_0(h_1-h_0)=0$, and the interior homogeneous equations hold. Define $D_i=h_i-h_{i+1}$. The equation at 0 gives $D_0=0$. At each interior state the homogeneous equation gives $\lambda_iD_i=\mu_iD_{i-1}$. Since $\lambda_i>0$, induction from $D_0=0$ yields $D_i=0$ for every $i<N$. Thus all $h_i$ are equal, and $h_N=0$ forces each $h_i=0$. This proves uniqueness. $\square$

Corollary: The successive differences have the explicit form $$ \Delta_i=\sum_{k=0}^{i}\frac1{\lambda_k}\prod_{r=k+1}^{i}\frac{\mu_r}{\lambda_r}, $$ where an empty product is 1. Therefore $t_i=\sum_{\ell=i}^{N-1}\sum_{k=0}^{\ell}\frac1{\lambda_k}\prod_{r=k+1}^{\ell}\frac{\mu_r}{\lambda_r}$.

Proof. For $i=0$, the expression is $1/\lambda_0$, as required. Suppose it holds for $i-1$. Substituting into $\Delta_i=1/\lambda_i+(\mu_i/\lambda_i)\Delta_{i-1}$ gives the term $1/\lambda_i$, corresponding to $k=i$, plus each term indexed $0\le k<i$ multiplied by $\mu_i/\lambda_i$. These are precisely the terms in the displayed sum for $\Delta_i$. Induction proves the formula, and summing the differences from $i$ to $N-1$ gives the expression for $t_i$. $\square$

Worked Examples

Worked Example: A Three-State Interval with Unequal Rates

Take $S=\{0,1,2\}$, with target $N=2$, $\lambda_0=2$, $\lambda_1=3$, and $\mu_1=1$. Find the expected time to reach 2 from states 0 and 1. The stopped-chain generator, with states ordered $0,1,2$, is $$ Q=\begin{bmatrix} -2&2&0\\ 1&-4&3\\ 0&0&0 \end{bmatrix}. $$ The row sums are $-2+2+0=0$, $1-4+3=0$, and $0+0+0=0$, so each generator row sums to zero.

Use the difference recurrence. First, $\Delta_0=1/\lambda_0=1/2$. Next, $$ \Delta_1=\frac{1+\mu_1\Delta_0}{\lambda_1} =\frac{1+1\cdot(1/2)}{3} =\frac{3/2}{3} =\frac12. $$ Since $t_2=0$, $t_1=\Delta_1=1/2$ and $t_0=\Delta_0+\Delta_1=1$.

Check by substitution. At state 0, $2(t_1-t_0)=2(1/2-1)=-1$. At state 1, $3(t_2-t_1)+1(t_0-t_1)=3(0-1/2)+(1-1/2)=-3/2+1/2=-1$. Both equations hold. The birth and death rates here are unequal; the solution uses the specified rates rather than an equal-rate shortcut.

Worked Example: A Four-State Interval

Let $S=\{0,1,2,3\}$, target $N=3$, and rates $\lambda_0=2$, $\lambda_1=2$, $\mu_1=1$, $\lambda_2=1$, and $\mu_2=2$. The stopped-chain generator is $$ Q=\begin{bmatrix} -2&2&0&0\\ 1&-3&2&0\\ 0&2&-3&1\\ 0&0&0&0 \end{bmatrix}. $$ The row sums are $-2+2=0$, $1-3+2=0$, $2-3+1=0$, and $0$, as required.

Calculate each difference in order: $$ \Delta_0=\frac12,\qquad \Delta_1=\frac{1+1\cdot(1/2)}2=\frac34,\qquad \Delta_2=\frac{1+2\cdot(3/4)}1=\frac52. $$ Thus $t_3=0$, $t_2=\Delta_2=5/2$, $t_1=\Delta_1+\Delta_2=3/4+5/2=13/4$, and $t_0=\Delta_0+\Delta_1+\Delta_2=1/2+3/4+5/2=15/4$.

Check by substitution. At 0, $2(t_1-t_0)=2(13/4-15/4)=-1$. At 1, $2(t_2-t_1)+(t_0-t_1)=2(10/4-13/4)+(15/4-13/4)=-6/4+2/4=-1$. At 2, $(t_3-t_2)+2(t_1-t_2)=-10/4+2(13/4-10/4)=-10/4+6/4=-1$. All boundary and interior equations are satisfied.

Worked Example: Expected Time to Hit Either Endpoint

Now make both endpoints absorbing on $S=\{0,1,2,3\}$. Let $\lambda_1=2,\mu_1=1,\lambda_2=1,\mu_2=2$; states 0 and 3 have no outgoing jumps. The generator is $$ Q=\begin{bmatrix} 0&0&0&0\\ 1&-3&2&0\\ 0&2&-3&1\\ 0&0&0&0 \end{bmatrix}. $$ Its row sums are $0$, $1-3+2=0$, $2-3+1=0$, and $0$. Find the expected time $u_i$ to hit $\{0,3\}$, starting from 1 or 2.

Here $u_0=u_3=0$. First-step equations at the interior states are $$ 2(u_2-u_1)+(u_0-u_1)=-1,\qquad (u_3-u_2)+2(u_1-u_2)=-1. $$ Substituting the boundary values and collecting terms gives $3u_1-2u_2=1$ and $-2u_1+3u_2=1$. Adding the equations gives $u_1+u_2=2$; substituting $u_2=2-u_1$ into the first gives $3u_1-2(2-u_1)=1$, hence $5u_1=5$, $u_1=1$, and $u_2=1$.

Check. At state 1, $2(1-1)+(0-1)=-1$. At state 2, $(0-1)+2(1-1)=-1$. The boundary values are zero. This calculation uses equations for the specified target set $\{0,3\}$; the one-sided recurrence for hitting $N$ has a different boundary condition at 0.

Why the Assumptions and Units Matter

Strictly positive upward rates below $N$ ensure that the target is reachable from every state. If a required upward rate is zero, a state may be unable to reach the target, and its expected hitting time can be infinite. For example, on $\{0,1,2\}$, let $\lambda_0=1$, $\mu_1=1$, and $\lambda_1=0$, with state 2 the target. From state 1 the chain jumps to 0, and from 0 it returns to 1; it never reaches 2. Thus $\mathbb E_1[T_2]=\infty$, and the positive-rate theorem does not apply.

Common mistake: counting jumps as elapsed time. In the first example, replacing the holding time with one unit per jump gives the embedded-chain equations $k_0=1+k_1$ and $k_1=1+\tfrac14k_0$, where $k_i$ counts jumps to reach 2. Substitution gives $k_0=2+\tfrac14k_0$, so $k_0=8/3$ jumps. That is not the expected elapsed time. The continuous-time answer is $t_0=1$, because the holding rates differ across states. The correct equations weight each state by its actual rates, as in $Qt=-\mathbf 1$.

For a practical calculation, first write the boundary conditions and verify the generator rows sum to zero. Then form the first-step equations, solve for the differences in the direction allowed by the recurrence, and recover the expected times by summing. Substitution into every equation is an essential final check.

Check Your Understanding

For each question, identify the target and use continuous-time equations; distinguish elapsed time from jump count.

For the three-state example, what is $\Delta_0$, and why is it the mean holding time at state 0?
In the four-state example, verify the equation at state 2 using $t_1=13/4$, $t_2=5/2$, and $t_3=0$.
For a chain with target $N$, explain why the recurrence for $\Delta_i$ can be computed from $i=0$ upward.
What can fail if an upward rate below the target is zero?
In the two-endpoint example, why must the expected time equations use $u_0=u_3=0$?

Expected Times To Hit A Boundary

What You'll Learn