First Passage Times in Discrete-Time Markov Chains

First Passage as a Distribution

A Markov chain can enter a target set after several different paths, and it may also avoid that set forever. A first-passage distribution records both when the chain enters for the first time and the possibility that no such time exists. Keeping that last possibility matters: the probabilities at finite times need not sum to one.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite or countable state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Its transition matrix is $P=(p_{ij})$, where $p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$, and each row sums to $1$. Use the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. For $A\subseteq S$, define the first-passage time to $A$ by

T_A=\inf\{n\ge0:X_n\in A\},\qquad \inf\varnothing=\infty.

For a chain started at $i$, write $\mathbb{P}_i$ for its probability law and set $f_i(n)=\mathbb{P}_i(T_A=n)$ for finite $n\ge0$. If $i\in A$, then $f_i(0)=1$, since the chain starts in the target. If $i\notin A$, then $f_i(0)=0$. In either case, $\mathbb{P}_i(T_A=\infty)$ is a separate part of the distribution. First passage uses $n\ge0$; it is not the first return convention, which requires at least one step.

Definition: The first-passage distribution from $i$ to $A$ consists of the probabilities $f_i(n)=\mathbb{P}_i(T_A=n)$, $n\ge0$, together with the possible mass $\mathbb{P}_i(T_A=\infty)$. These masses satisfy $\sum_{n=0}^{\infty}f_i(n)+\mathbb{P}_i(T_A=\infty)=1$.

To compute the distribution, separate the states outside the target from those inside it. Let $B=S\setminus A$. For $i,j\in B$, write $Q=(p_{ij})_{i,j\in B}$, the transition matrix restricted to moves that stay outside $A$. It is generally substochastic: each row sum is at most $1$, with the missing probability being the chance of moving into $A$. Define $r_i=\sum_{a\in A}p_{ia}$ for $i\in B$, the one-step probability of entering $A$ from $i$.

Theorem (Path formula): If $A$ is nonempty and $i\in B$, then, for every integer $n\ge1$, $$ f_i(n)=\sum_{x_1,\ldots,x_{n-1}\in B}p_{ix_1}p_{x_1x_2}\cdots p_{x_{n-2}x_{n-1}}r_{x_{n-1}} =(Q^{n-1}r)_i. $$ For $n=1$, the sum over intermediate states is absent and the formula means $f_i(1)=r_i$. Also, for $n\ge0$, $$ \mathbb{P}_i(T_A>n)=\sum_{j\in B}(Q^n)_{ij}. $$

Proof. Fix $i\in B$. For $T_A=n$, the chain must be outside $A$ at times $0,\ldots,n-1$, and in $A$ at time $n$. For a particular path $i,x_1,\ldots,x_{n-1},a$, with each $x_k\in B$ and $a\in A$, the Markov property gives its probability as $p_{ix_1}\cdots p_{x_{n-2}x_{n-1}}p_{x_{n-1}a}$. These paths are disjoint, so summing over them and then over $a\in A$ gives the displayed path sum. By the definition of matrix multiplication, summing over the intermediate states is exactly $(Q^{n-1}r)_i$; when $n=1$, it is $r_i$. For the survival identity, $T_A>n$ holds exactly when $X_0,\ldots,X_n\in B$. Summing the probabilities of all such paths ending at each $j\in B$ gives $(Q^n)_{ij}$ for endpoint $j$, and summing over $j$ proves the formula. $\square$

The formula gives a useful way to obtain the probability of never reaching the target. The events $\{T_A>n\}$ decrease as $n$ grows, and their intersection is $\{T_A=\infty\}$. Continuity of probability for decreasing events therefore gives the limit below. This conclusion does not require the chain to be finite.

Corollary: For $i\in B$, $$ \mathbb{P}_i(T_A=\infty) =\lim_{n\to\infty}\mathbb{P}_i(T_A>n) =1-\sum_{n=1}^{\infty}f_i(n). $$ The finite-time probabilities can sum to less than $1$; the difference is the probability of never entering $A$.

Proof. The event $\{T_A>n\}$ means that no visit to $A$ has occurred by time $n$. Their intersection over all $n\ge0$ is exactly $\{T_A=\infty\}$, so continuity of probability from above gives the limit. Also, for every $N\ge1$, the disjoint events $\{T_A=n\}$, $1\le n\le N$, have union $\{T_A\le N\}$, since $i\in B$. Thus $\mathbb{P}_i(T_A\le N)=\sum_{n=1}^N f_i(n)$. Taking $N$ to infinity and using $\{T_A\le N\}$ increasing to $\{T_A<\infty\}$ gives $\mathbb{P}_i(T_A<\infty)=\sum_{n=1}^{\infty}f_i(n)$. The finite-time event and the event of never hitting are disjoint and together have probability $1$, proving the result. $\square$

Computing the Distribution from Paths

Worked Example: A Geometric First-Passage Law

Let $S=\{0,1\}$, $A=\{1\}$, and use the transition matrix, with rows and columns ordered $0,1$,

P= \begin{bmatrix} \tfrac12&\tfrac12\\ 0&1 \end{bmatrix}.

Both row sums are $1$: $\tfrac12+\tfrac12=1$ and $0+1=1$. Starting from $0$, the chain must stay at $0$ for $n-1$ steps and then move to $1$ to have $T_A=n$. Therefore, for every $n\ge1$,

f_0(n)=\left(\tfrac12\right)^{n-1}\tfrac12=2^{-n}.

For instance, $f_0(1)=\tfrac12$, $f_0(2)=\tfrac14$, and $f_0(3)=\tfrac18$. The probabilities of not yet hitting by time $n$ are $\mathbb{P}_0(T_A>n)=2^{-n}$: the chain must stay at $0$ at each of the first $n$ transitions. Hence $\mathbb{P}_0(T_A=\infty)=\lim_{n\to\infty}2^{-n}=0$.

Check: The finite-time masses sum to $\sum_{n=1}^{\infty}2^{-n}=1$, so together with zero mass at infinity they form a probability distribution. At $n=2$, the path $0\to0\to1$ has probability $\tfrac12\cdot\tfrac12=\tfrac14$, agreeing with $f_0(2)$.

When there are several non-target states, the matrix $Q$ collects all paths that remain outside the target. The power $Q^{n-1}$ accounts for the first $n-1$ transitions that stay outside, and the vector $r$ accounts for the final transition into the target.

Worked Example: A Positive Probability of Never Hitting

Take $S=\{0,1,2,3\}$, $A=\{2\}$, and the transition matrix in the order $0,1,2,3$:

P= \begin{bmatrix} 0&\tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac14&\tfrac14\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}.

The row sums are, respectively, $0+\tfrac12+\tfrac12+0=1$, $0+\tfrac12+\tfrac14+\tfrac14=1$, $1$, and $1$. State $3$ is an absorbing state outside $A$, so a path can escape the target permanently by entering $3$. From $0$, the chain enters $A$ at time $1$ with probability $f_0(1)=\tfrac12$.

For $n\ge2$, the only path that first reaches $A$ at time $n$ is $0\to1$, followed by $n-2$ transitions $1\to1$, followed by $1\to2$. Its probability is

f_0(n)=\tfrac12\left(\tfrac12\right)^{n-2}\tfrac14 =\tfrac18\left(\tfrac12\right)^{n-2}.

The total finite-time mass is $$ \sum_{n=0}^{\infty}f_0(n) =\tfrac12+\sum_{n=2}^{\infty}\tfrac18\left(\tfrac12\right)^{n-2} =\tfrac12+\tfrac18\cdot\frac{1}{1-\tfrac12} =\tfrac34. $$ Thus $\mathbb{P}_0(T_A=\infty)=1-\tfrac34=\tfrac14$. This is the probability of the path $0\to1\to3$: its probability is $\tfrac12\cdot\tfrac14=\tfrac18$, but that is only the probability of entering $3$ on the first step after reaching $1$. More generally, the probability of eventually entering $3$ from $1$ is $\sum_{k=0}^{\infty}(\tfrac12)^k\tfrac14=\tfrac12$. Multiplying by $\mathbb{P}_0(X_1=1)=\tfrac12$ gives $\tfrac14$, as required.

Check using survival probabilities: For $n\ge1$, the paths still outside $A$ at time $n$ either stay at $1$ after the first step, or have moved from $1$ to $3$. Their total probability is $\tfrac12\cdot\tfrac12^{n-1}+\tfrac14(1-\tfrac12^{n-1})=\tfrac14+2^{-(n+1)}$. This tends to $\tfrac14$, matching the probability of never hitting $A$.

Targets with Multiple Entry States

A target can contain more than one state. In that case, all transitions into any state in $A$ count as first passage, and the final transition probability is $r_i=\sum_{a\in A}p_{ia}$. The path calculation still sums only paths whose intermediate states remain in $B$; paths that entered the target earlier must not be counted again.

Worked Example: First Passage to Either of Two States

Let $S=\{0,1,2,3\}$, $A=\{2,3\}$, and let

P= \begin{bmatrix} 0&\tfrac13&\tfrac23&0\\ \tfrac12&0&0&\tfrac12\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}.

Every row sums to $1$: the row sums are $\tfrac13+\tfrac23=1$, $\tfrac12+\tfrac12=1$, $1$, and $1$. Starting at $0$, a first passage at time $1$ occurs by moving to $2$, so $f_0(1)=\tfrac23$. A first passage at time $2$ follows $0\to1\to3$, giving $f_0(2)=\tfrac13\cdot\tfrac12=\tfrac16$. At time $3$, the path is $0\to1\to0\to2$, giving $f_0(3)=\tfrac13\cdot\tfrac12\cdot\tfrac23=\tfrac19$.

Each two-step cycle $0\to1\to0$ has probability $\tfrac13\cdot\tfrac12=\tfrac16$. Consequently, for integers $k\ge0$,

f_0(2k+1)=\left(\tfrac16\right)^k\tfrac23, \qquad f_0(2k+2)=\left(\tfrac16\right)^k\tfrac16.

The first formula describes $k$ cycles followed by $0\to2$; the second describes $k$ cycles followed by $0\to1\to3$. Summing both sequences gives

\sum_{n=1}^{\infty}f_0(n) =\frac{\tfrac23}{1-\tfrac16}+\frac{\tfrac16}{1-\tfrac16} =\tfrac45+\tfrac15=1.

Thus $\mathbb{P}_0(T_A=\infty)=0$. As a check, the first four masses are $f_0(1)=\tfrac23$, $f_0(2)=\tfrac16$, $f_0(3)=\tfrac19$, and $f_0(4)=\tfrac1{36}$; the formulas give $f_0(3)=\tfrac16\cdot\tfrac23=\tfrac19$ and $f_0(4)=\tfrac16\cdot\tfrac16=\tfrac1{36}$.

Initial Distributions and a Common Pitfall

If the initial distribution is a row vector $\mu$, the first-passage distribution is obtained by averaging over the initial state. In particular, $\mathbb{P}_\mu(T_A=n)=\sum_{i\in S}\mu_i f_i(n)$. The mass at time zero is $\sum_{i\in A}\mu_i$, because the chain has already reached the target exactly when $X_0\in A$. This averaging includes states in the target and states outside it.

Worked Example: A Mixture with Mass at Time Zero

Let $S=\{0,1\}$, $A=\{1\}$, with $P=\begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix}$, whose row sums are $\tfrac12+\tfrac12=1$ and $0+1=1$. Suppose $\mu=(\tfrac12,\tfrac12)$, ordered $0,1$. Then $\mathbb{P}_\mu(T_A=0)=\mu_1=\tfrac12$. For $n\ge1$, only a chain starting at $0$ can first hit at time $n$, so

\mathbb{P}_\mu(T_A=n) =\mu_0 f_0(n) =\tfrac12\left(\tfrac12\right)^n =2^{-(n+1)}.

The finite-time probabilities sum to $\tfrac12+\sum_{n=1}^{\infty}2^{-(n+1)}=\tfrac12+\tfrac12=1$, with no mass at infinity. For example, the time-one mass is $\tfrac12\cdot\tfrac12=\tfrac14$, the probability of starting at $0$ and moving to $1$ immediately.

Check: The mass at time zero plus the time-one mass is $\tfrac12+\tfrac14=\tfrac34$. The remaining mass after time one is $\sum_{n=2}^{\infty}2^{-(n+1)}=\tfrac14$, so the total is $1$.

Common pitfall: confusing occupancy with first passage. The probability $\mathbb{P}_i(X_n\in A)$ is not generally $\mathbb{P}_i(T_A=n)$: the chain may have entered $A$ earlier and still be there at time $n$. For example, use the chain in the preceding example, start at $0$, and take $A=\{1\}$. At time $2$, $P^{(2)}_{01}=\tfrac34$, because the chain can enter $1$ at either step and then remain there. But the first-passage probability is only $f_0(2)=\tfrac14$, from the path $0\to0\to1$. The other $\tfrac12$ of the occupancy probability comes from hitting at time $1$ and staying at $1$. The path formula avoids this overcounting by requiring every intermediate state to lie outside $A$.

When applying these formulas, check whether the initial state is already in the target, whether the target can be missed forever, and whether the requested quantity is first passage or occupancy at a fixed time. For countable state spaces, the path sums may have infinitely many terms, but their terms are nonnegative probabilities; the formulas are interpreted as sums of nonnegative terms and remain valid.

Check Your Understanding

Use the first-passage definition and path formulas to answer these questions.

If $i\in A$, what is $\mathbb{P}_i(T_A=0)$, and what is $\mathbb{P}_i(T_A>0)$?
For a starting state $i\notin A$, explain why the intermediate states in the path formula for $f_i(n)$ must all lie in $S\setminus A$.
In the four-state example with a positive probability of never hitting, compute $f_0(2)$ and $f_0(3)$ directly from their paths.
What does the row sum of $Q^n$ represent when $i\notin A$?
Give a reason that $\sum_{n\ge0}f_i(n)$ may be less than $1$, and state what the missing mass represents.