Solving Finite-Interval Hitting Problems

Hitting One Endpoint Before the Other

In a finite birth-death chain, the state records a level, population, or position, and each jump changes it by one. A natural question is whether the process reaches the top of a finite interval before it returns to the bottom. Continuous-time holding times affect when jumps occur, but the probability of choosing the next upward or downward jump is determined by the corresponding rates. This makes it possible to calculate the boundary-hitting probability through a recurrence.

Let $(X_t)_{t\ge0}$ be a continuous-time Markov chain on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with state space $S=\{0,1,\ldots,N\}$, where $N\ge1$, and natural filtration $(\mathcal{F}_t)_{t\ge0}$. For each interior state $i\in\{1,\ldots,N-1\}$, suppose the chain jumps from $i$ to $i+1$ at rate $\lambda_i>0$ and from $i$ to $i-1$ at rate $\mu_i>0$, with no other jumps from $i$. Treat 0 and $N$ as absorbing for this problem. Equivalently, stop the chain when it first reaches either endpoint; its behavior afterward does not affect which endpoint is reached first.

Definition: For $i\in S$, let $h_i=\mathbb{P}_i(X_T=N)$, where $T=\inf\{t\ge0:X_t\in\{0,N\}\}$ is the first time the chain reaches an endpoint. Thus $h_i$ is the probability of reaching $N$ before 0 when the chain starts at $i$. In particular, $h_0=0$ and $h_N=1$.

The holding time in an interior state $i$ is exponential with rate $\lambda_i+\mu_i$. At the end of that holding time, the next jump is upward with probability $\lambda_i/(\lambda_i+\mu_i)$ and downward with probability $\mu_i/(\lambda_i+\mu_i)$. Conditioning on this first jump gives a linear equation for $h_i$. The holding time itself does not appear in the equation: it changes the time of the jump, not which endpoint is reached first.

The Recurrence and Its Solution

Before using the recurrence, we check that one of the endpoints is reached with probability one. Consider the embedded jump chain, which records successive states at jump times. From every interior state, there is a positive probability of making consecutive downward jumps to 0 in at most $N-1$ jumps. There are finitely many interior states, so there is a common positive lower bound $\delta$ on the probability of reaching an endpoint within the next $N$ jumps, starting from any interior state. Consequently, the probability of avoiding both endpoints for $kN$ jumps is at most $(1-\delta)^k$, which tends to zero as $k$ tends to infinity. Each holding time in an interior state is finite almost surely, so the continuous-time chain also reaches an endpoint almost surely.

Theorem (Finite-interval hitting formula): Under the positive-rate assumptions above, the upper-endpoint hitting probabilities satisfy $h_0=0$, $h_N=1$, and $$ \lambda_i(h_{i+1}-h_i)=\mu_i(h_i-h_{i-1}),\qquad 1\le i\le N-1. $$ Define $w_1=1$ and, for $2\le k\le N$, define $w_k=\prod_{j=1}^{k-1}\frac{\mu_j}{\lambda_j}$. Then, for $0\le i\le N$, $$ h_i=\frac{\displaystyle\sum_{k=1}^{i} w_k}{\displaystyle\sum_{k=1}^{N} w_k}, $$ where a sum with no terms is zero.

Proof. For an interior state $i$, the first jump goes to $i+1$ with probability $\lambda_i/(\lambda_i+\mu_i)$ and to $i-1$ with probability $\mu_i/(\lambda_i+\mu_i)$. Since an endpoint is reached almost surely, conditioning on that jump gives $$ h_i=\frac{\lambda_i}{\lambda_i+\mu_i}h_{i+1} +\frac{\mu_i}{\lambda_i+\mu_i}h_{i-1}. $$ Multiplying by $\lambda_i+\mu_i$ and rearranging gives the stated recurrence. To solve it, set $\Delta_i=h_i-h_{i-1}$ for $1\le i\le N$. The recurrence becomes $\lambda_i\Delta_{i+1}=\mu_i\Delta_i$, so $\Delta_{i+1}=(\mu_i/\lambda_i)\Delta_i$. Repeated substitution yields $\Delta_k=\Delta_1w_k$ for $1\le k\le N$, including $k=1$ because $w_1=1$. Summing increments gives $h_i=\sum_{k=1}^{i}\Delta_k=\Delta_1\sum_{k=1}^{i}w_k$. The boundary condition $h_N=1$ implies $1=\Delta_1\sum_{k=1}^{N}w_k$. Every $w_k$ is positive, so the denominator is nonzero and $\Delta_1$ is its reciprocal. This proves the formula, including $i=0$ and $i=N$. Finally, the recurrence and boundary values determine at most one solution: any solution must have increments proportional to the same positive sequence $w_1,\ldots,w_N$, and its endpoint condition fixes that proportionality constant. Thus the formula is the hitting probability. $\square$

The formula is a normalized sum of positive weights. The ratio $w_{k+1}/w_k=\mu_k/\lambda_k$ compares the downward and upward rates at state $k$. If the rates are equal at every interior state, all weights are equal. If downward rates dominate, the weights tend to grow with $k$, changing how the boundary condition is accumulated across the interval.

Worked Example: Equal Birth and Death Rates

Consider states $0,1,2,3,4$, with absorbing endpoints and $\lambda_i=\mu_i=1$ for each interior state. The generator, with states in the order $0,1,2,3,4$, is $$ Q=\begin{bmatrix} 0&0&0&0&0\\ 1&-2&1&0&0\\ 0&1&-2&1&0\\ 0&0&1&-2&1\\ 0&0&0&0&0 \end{bmatrix}. $$ The endpoint rows sum to $0$, and each interior row sums to $1-2+1=0$. The upward and downward rates are positive at each interior state.

For $k=1,2,3,4$, the weights are $w_1=1$, $w_2=1$, $w_3=1$, and $w_4=1$, since each ratio $\mu_i/\lambda_i$ equals $1$. Their total is $4$. The formula therefore gives $h_i=i/4$, so $h_1=1/4$, $h_2=1/2$, $h_3=3/4$, along with $h_0=0$ and $h_4=1$.

Check by substitution. The successive differences are $\Delta_1=1/4$, $\Delta_2=1/4$, $\Delta_3=1/4$, and $\Delta_4=1/4$. At each interior state, $\lambda_i\Delta_{i+1}=1\cdot1/4=1/4$ and $\mu_i\Delta_i=1\cdot1/4=1/4$. The recurrence holds, and the values at the endpoints are $0$ and $1$.

Worked Example: A Constant Upward Bias

Now use the same interval $\{0,1,2,3,4\}$, with $\lambda_i=2$ and $\mu_i=1$ at each interior state, again making both endpoints absorbing. The generator is $$ Q=\begin{bmatrix} 0&0&0&0&0\\ 1&-3&2&0&0\\ 0&1&-3&2&0\\ 0&0&1&-3&2\\ 0&0&0&0&0 \end{bmatrix}. $$ Each endpoint row sums to $0$, and each interior row sums to $1-3+2=0$; the specified rates are positive.

Here $\mu_i/\lambda_i=1/2$ for $i=1,2,3$. Thus $w_1=1$, $w_2=1/2$, $w_3=1/4$, and $w_4=1/8$. The denominator is $1+1/2+1/4+1/8=15/8$. For a start at state 2, the numerator is $w_1+w_2=1+1/2=3/2$, so $h_2=(3/2)/(15/8)=4/5$. The full values are $h_0=0$, $h_1=8/15$, $h_2=12/15=4/5$, $h_3=14/15$, and $h_4=1$.

Check by substitution. The successive differences are $8/15,4/15,2/15,1/15$. At state 1, $\lambda_1\Delta_2=2(4/15)=8/15=\mu_1\Delta_1$. At state 2, $\lambda_2\Delta_3=2(2/15)=4/15=\mu_2\Delta_2$. At state 3, $\lambda_3\Delta_4=2(1/15)=2/15=\mu_3\Delta_3$. The endpoint values also hold, verifying the answer at every state.

Worked Example: Rates That Vary Across the Interval

Consider states $0,1,2,3$, with absorbing endpoints. Let $(\lambda_1,\mu_1)=(2,1)$ and $(\lambda_2,\mu_2)=(1,2)$. The generator is $$ Q=\begin{bmatrix} 0&0&0&0\\ 1&-3&2&0\\ 0&2&-3&1\\ 0&0&0&0 \end{bmatrix}. $$ The endpoint rows sum to $0$, and each interior row sums to $1-3+2=0$; both rates are positive at states 1 and 2.

The weights are $w_1=1$, $w_2=\mu_1/\lambda_1=1/2$, and $w_3=(\mu_1/\lambda_1)(\mu_2/\lambda_2)=(1/2)(2)=1$. Their total is $1+1/2+1=5/2$. Consequently, $h_1=1/(5/2)=2/5$ and $h_2=(1+1/2)/(5/2)=3/5$, with $h_0=0$ and $h_3=1$.

Check by substitution. The differences are $\Delta_1=2/5$, $\Delta_2=1/5$, and $\Delta_3=2/5$. At state 1, $\lambda_1\Delta_2=2(1/5)=2/5=\mu_1\Delta_1$. At state 2, $\lambda_2\Delta_3=1(2/5)=2/5=\mu_2\Delta_2$. Thus both recurrence equations hold, and the boundary values are $0$ and $1$.

Interpreting the Calculation

The first-jump equations use the rates through their relative sizes, not as if $\lambda_i$ and $\mu_i$ were themselves probabilities. For example, the probability of an upward jump from state $i$ is $\lambda_i/(\lambda_i+\mu_i)$, not $\lambda_i$. Dividing the rates by their sum produces the jump probabilities, and multiplying the recurrence by that same sum gives the rate form used in the proof.

Common mistake: reversing the rate ratio. In the constant-rate example with $\lambda_i=2$ and $\mu_i=1$, using $\lambda_i/\mu_i=2$ as the multiplier for successive differences would produce the incorrect weights $1,2,4,8$. That calculation gives $h_2=(1+2)/(1+2+4+8)=3/15=1/5$, instead of the correct $4/5$. The recurrence fixes the direction: $\lambda_i\Delta_{i+1}=\mu_i\Delta_i$, hence $\Delta_{i+1}/\Delta_i=\mu_i/\lambda_i=1/2$. Substituting the correct differences into the recurrence verifies the direction of the ratio.

The endpoint conditions matter just as much as the rates. Starting at 0 gives probability zero of reaching $N$ before 0, because the chain has already reached 0; starting at $N$ gives probability one. For an interior start, the positive-rate assumptions ensure both possible first jumps are defined, and the finite interval ensures an endpoint is eventually reached. The formula then provides the probability of the upper endpoint for every starting state without calculating the distribution of the hitting time.

Check Your Understanding

Use the first-jump recurrence and the boundary values to answer the following questions.

For $N=3$ with $\lambda_i=\mu_i=1$ at both interior states, what is the probability of reaching 3 before 0 from state 1?
For $N=3$ with $\lambda_i=2$ and $\mu_i=1$ at both interior states, calculate $h_1$ and $h_2$ using the weights.
For a chain with $N=2$, $\lambda_1=3$, and $\mu_1=1$, write the first-jump equation and solve for $h_1$.
Explain why the weight ratio $w_{i+1}/w_i$ is $\mu_i/\lambda_i$, rather than $\lambda_i/\mu_i$.
Why does the hitting formula require positive upward and downward rates at every interior state?

Solving Finite-Interval Hitting Problems

What You'll Learn