Expected Time to Hit a Target Set

From a Target Set to an Expected Time

Knowing the probability that a chain eventually reaches a target does not tell us how long reaching it typically takes. For a finite chain that reaches the target almost surely, expected time can be computed by focusing only on transitions among states outside the target. The calculation gives a separate expected time for each possible starting state; an initial distribution then determines the corresponding average across starting states.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite state space $S$, on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with transition matrix $P=(p_{ij})$. Let $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$ be its natural filtration. For a nonempty target set $A\subseteq S$, define $T_A=\inf\{n\ge0:X_n\in A\}$, with $\inf\varnothing=\infty$. Write $\mathbb{P}_i$ and $\mathbb{E}_i$ when the chain starts at $i$. In particular, $T_A=0$ if $i\in A$.

Definition: Make $A$ absorbing by replacing each row of $P$ indexed by $i\in A$ with a row that assigns probability $1$ to $i$ and $0$ to every other state. Leave the other rows unchanged. The resulting transition matrix is denoted $P^A$. In the ordering with states outside $A$ first, let $Q$ be the submatrix of $P^A$ whose rows and columns are indexed by $S\setminus A$. It records transitions that remain outside the target.

Every row of a transition matrix must sum to $1$. Accordingly, each unchanged row of $P^A$ still sums to $1$, and each replaced row sums to $1$ because it has exactly one entry equal to $1$. The rows of $Q$ can sum to less than $1$: the missing probability is the chance of moving into $A$.

Proposition (Absorbing transformation preserves the hitting time): Replacing the target states’ rows by absorbing rows leaves the distribution of $T_A$ unchanged from every starting state.

Proof. Fix an initial state. For any finite path that has not yet reached $A$, every transition used so far starts at a state outside $A$, and that row is unchanged in $P^A$. Thus the original chain and the chain with transition matrix $P^A$ assign the same probability to every path up to and including its first entrance into $A$. The event $T_A=n$ is determined by precisely those transitions: the states at times $0,\ldots,n-1$ are outside $A$, and the state at time $n$ is in $A$. Its probability is therefore the same under both matrices for every $n\ge0$. The probabilities of all finite values of $T_A$, and hence its distribution including any mass at infinity, agree. $\square$

Expected Time from the Transient Equations

Assume that $A$ is reached almost surely from every state outside $A$. This is the condition that makes the finite-state calculation below apply. If $S\setminus A$ is empty, every starting state is already in $A$ and every expected hitting time is zero. Otherwise, define the column vector $\mathbf{1}$ to have one entry equal to $1$ for each state outside $A$.

Theorem: Under the assumptions above, $Q^n$ tends to the zero matrix, the inverse $N=(I-Q)^{-1}$ exists, and the column vector $\mathbf{t}$ of expected hitting times from states outside $A$ is $$ \mathbf{t}=N\mathbf{1}=(I-Q)^{-1}\mathbf{1}. $$ Equivalently, $t_i=0$ for $i\in A$, and for $i\notin A$, $$ t_i=1+\sum_{j\notin A}p_{ij}t_j. $$

Proof. For $i\notin A$, let $k_i$ be the expected number of steps to hit $A$. First show that the expected time is finite. Almost-sure hitting means that for each such $i$, there is an integer $n_i\ge1$ for which $\mathbb{P}_i(T_A\le n_i)>0$: indeed, the events $\{T_A\le n\}$ increase to $\{T_A<\infty\}$, which has probability $1$. Since there are finitely many states outside $A$, set $M=\max_i n_i$ and $\delta=\min_i\mathbb{P}_i(T_A\le M)>0$. From any state outside $A$, the chance of avoiding $A$ for the next $M$ steps is at most $1-\delta$. By applying the Markov property at times $M,2M,\ldots$, the probability of avoiding $A$ for $rM$ steps is at most $(1-\delta)^r$. This geometric bound implies that the expected hitting time is finite.

For $n\ge0$, the probability from state $i\notin A$ of avoiding $A$ through time $n$ is the sum of row $i$ of $Q^n$. This follows by multiplying transition probabilities along all length-$n$ paths that stay outside $A$. In particular, $\mathbb{P}_i(T_A>n)=\sum_{j\notin A}(Q^n)_{ij}$. The geometric bound just proved makes the series $\sum_{n\ge0}Q^n$ converge entrywise. Its partial sums satisfy $$ (I-Q)\sum_{n=0}^{m}Q^n=I-Q^{m+1}. $$ The geometric bound gives $Q^{m+1}\to0$, so taking limits shows that the sum is an inverse of $I-Q$. The same multiplication in the reverse order gives a right inverse, hence $N=(I-Q)^{-1}=\sum_{n\ge0}Q^n$.

For a nonnegative integer-valued hitting time, including one that might initially have been infinite, $\mathbb{E}_i[T_A]=\sum_{n\ge0}\mathbb{P}_i(T_A>n)$. Therefore the expected-time vector is $\sum_{n\ge0}Q^n\mathbf{1}=N\mathbf{1}$. Multiplying by $I-Q$ gives $(I-Q)\mathbf{t}=\mathbf{1}$, or $t_i=1+\sum_{j\notin A}p_{ij}t_j$. For $i\in A$, the definition gives $t_i=0$. Since $I-Q$ is invertible, this system has exactly one solution on the states outside $A$. $\square$

The equation counts the step just taken, which accounts for the $1$. A transition into $A$ contributes no remaining time, which is why the sum only involves states outside $A$. If the initial distribution is the row vector $\mu$, the expected hitting time is the weighted average $\sum_{i\notin A}\mu_i t_i$; initial probability already in $A$ contributes zero.

Worked Example: A Two-State Transient Block

Consider $S=\{1,2,3\}$, target $A=\{3\}$, and transition matrix $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac13&\tfrac23\\ \tfrac14&\tfrac14&\tfrac12 \end{bmatrix}. $$ Each row sums to $1$: the row sums are $\tfrac12+\tfrac12=1$, $0+\tfrac13+\tfrac23=1$, and $\tfrac14+\tfrac14+\tfrac12=1$. Replace the row for state $3$ by $(0,0,1)$, which also sums to $1$. The transient block, in state order $1,2$, is $$ Q=\begin{bmatrix}\tfrac12&\tfrac12\\0&\tfrac13\end{bmatrix}. $$

From state $2$, the first-step equation is $t_2=1+\tfrac13t_2$, since the remaining probability $\tfrac23$ enters the target. Thus $\tfrac23t_2=1$ and $t_2=\tfrac32$. From state $1$, $t_1=1+\tfrac12t_1+\tfrac12t_2$, so $\tfrac12t_1=1+\tfrac12\cdot\tfrac32=\tfrac74$, giving $t_1=\tfrac72$. The target value is $t_3=0$.

Check by the matrix formula: $I-Q=\begin{bmatrix}\tfrac12&-\tfrac12\\0&\tfrac23\end{bmatrix}$, whose inverse is $\begin{bmatrix}2&\tfrac32\\0&\tfrac32\end{bmatrix}$. Multiplying by $\mathbf{1}$ gives $(2+\tfrac32,\ 0+\tfrac32)=(\tfrac72,\tfrac32)$, agreeing with the equations. Substitution also checks the result: $1+\tfrac12\cdot\tfrac72+\tfrac12\cdot\tfrac32=\tfrac72$, and $1+\tfrac13\cdot\tfrac32=\tfrac32$.

Worked Example: A Target with Two States

Let $S=\{0,1,2,3\}$, with target $A=\{2,3\}$, and take $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0&0\\ \tfrac14&0&\tfrac34&0\\ 0&0&\tfrac12&\tfrac12\\ 0&0&0&1 \end{bmatrix}. $$ The row sums are respectively $\tfrac12+\tfrac12=1$, $\tfrac14+\tfrac34=1$, $\tfrac12+\tfrac12=1$, and $1$. Make states $2$ and $3$ absorbing by replacing their rows with $(0,0,1,0)$ and $(0,0,0,1)$; each replacement row sums to $1$. The transient block for states $0,1$ is $$ Q=\begin{bmatrix}\tfrac12&\tfrac12\\\tfrac14&0\end{bmatrix}. $$

The expected times satisfy $t_0=1+\tfrac12t_0+\tfrac12t_1$ and $t_1=1+\tfrac14t_0$. Rearranging the first equation gives $t_0=2+t_1$. Substituting into the second gives $t_1=1+\tfrac14(2+t_1)=\tfrac32+\tfrac14t_1$. Hence $\tfrac34t_1=\tfrac32$, so $t_1=2$, and $t_0=4$. From either target state, the hitting time is zero.

Check: $1+\tfrac12\cdot4+\tfrac12\cdot2=4=t_0$, and $1+\tfrac14\cdot4=2=t_1$. If the initial distribution is $\mu=(\tfrac12,\tfrac12,0,0)$, then $\mathbb{E}_{\mu}[T_A]=\tfrac12\cdot4+\tfrac12\cdot2=3$. The individual answers remain $4$ and $2$; the value $3$ is the average for this particular starting distribution.

Worked Example: A Weighted Starting Distribution

Let $S=\{1,2,3,4\}$, target $A=\{4\}$, and $$ P=\begin{bmatrix} 0&1&0&0\\ \tfrac12&0&0&\tfrac12\\ 0&\tfrac13&0&\tfrac23\\ 1&0&0&0 \end{bmatrix}. $$ Every row sums to $1$: $1$, $\tfrac12+\tfrac12=1$, $\tfrac13+\tfrac23=1$, and $1$. Make state $4$ absorbing by replacing its row with $(0,0,0,1)$. The transient block, ordered $1,2,3$, is $$ Q=\begin{bmatrix} 0&1&0\\ \tfrac12&0&0\\ 0&\tfrac13&0 \end{bmatrix}. $$

The equations give $t_1=1+t_2$, $t_2=1+\tfrac12t_1$, and $t_3=1+\tfrac13t_2$. Substitution of $t_2=1+\tfrac12t_1$ into the first equation gives $t_1=2+\tfrac12t_1$, hence $t_1=4$. Then $t_2=1+\tfrac12\cdot4=3$, and $t_3=1+\tfrac13\cdot3=2$. Also $t_4=0$.

Suppose the initial distribution is $\mu=(\tfrac14,\tfrac14,\tfrac12,0)$. Its expected hitting time is $$ \mathbb{E}_{\mu}[T_A]=\tfrac14\cdot4+\tfrac14\cdot3+\tfrac12\cdot2=1+\tfrac34+1=\tfrac{11}{4}. $$ Check: the three first-step equations give $1+3=4$, $1+2=3$, and $1+1=2$, respectively. The initial-distribution calculation uses those state-specific values and its weights sum to $\tfrac14+\tfrac14+\tfrac12=1$.

What the Calculation Does—and Does Not—Say

Making $A$ absorbing is a device for calculating the time of first entrance, not a claim that the original chain stays in $A$. The replacement changes what happens after first arrival, but the proposition shows that it does not change $T_A$. The transient block $Q$ is not generally a transition matrix by itself: its row sums may be below $1$ because probability can leave the transient states and enter the target.

The almost-sure hitting assumption matters. It ensures that the transient block loses probability over time and that the inverse in the theorem exists. Without that assumption, the finite expected-time formula need not apply; do not treat an unsolvable or singular system as a finite answer. The calculation also distinguishes a starting state from an initial distribution: report $t_i$ when the start is specified as $i$, and take a weighted average only when a distribution over starting states is given.

Common mistake. In the first example, using the original row for state $3$ as though state $3$ were still transient would include transitions after the first hit. If one then treats all three states as transient, the matrix has row sums $1$ throughout, so $Q\mathbf{1}=\mathbf{1}$ and $(I-Q)\mathbf{1}=0$; $I-Q$ cannot be inverted. The correction is to make state $3$ absorbing and exclude it from the transient block. Then the relevant $Q$ is the two-by-two matrix shown above, and the expected time from state $1$ is $\tfrac72$, not a quantity counting time after entry into state $3$.

Check Your Understanding

For each question, distinguish the starting state from the target, and check any proposed expected times by substituting them into the transient-state equations.

Why does replacing the transition rows for target states leave the distribution of $T_A$ unchanged?
For a chain with transient block $Q=\begin{bmatrix}\tfrac12&\tfrac12\\0&0\end{bmatrix}$, write the two equations for expected hitting times and solve them.
In the two-target-state example, what is the expected hitting time if the chain starts at state $1$? What if it starts in state $2$?
Given state-specific expected times $t_i$ and an initial distribution $\mu$, how do you compute $\mathbb{E}_{\mu}[T_A]$? Why does initial mass on $A$ contribute zero?
What role does almost-sure hitting play in the existence of $(I-Q)^{-1}$ in the theorem?

Expected Time to Hit a Target Set

What You'll Learn