Distributions of Hitting and Return Times

From n-Step Probabilities to First-Hit Distributions

An n-step transition probability answers where a chain is at time $n$, not when it first arrived there. A chain can reach a target, leave it, and return before time $n$; consequently, $p_{ij}^{(n)}$ is generally not the probability that the first visit to $j$ occurs at step $n$. To find a first-hit distribution, we must exclude paths that have already reached the target.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite or countable state space $S$, on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with transition matrix $P=(p_{ij})$. Its natural filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. Write $P^n=(p_{ij}^{(n)})$, where $P^0$ is the identity matrix, and use $\mathbb{P}_i$ when $X_0=i$. For $A\subseteq S$, the hitting time is $T_A=\inf\{n\ge0:X_n\in A\}$, with $\inf\varnothing=\infty$. If $i\notin A$, define $f_{iA}(n)=\mathbb{P}_i(T_A=n)$ for $n\ge1$. If $i\in A$, then $T_A=0$ with probability one. For a state $i$, the first-return time is $T_i^+=\inf\{n\ge1:X_n=i\}$, and its distribution is $f_{ii}(n)=\mathbb{P}_i(T_i^+=n)$, $n\ge1$.

Definition: For $A\subseteq S$, let $B=S\setminus A$, and let $Q=(p_{ij})_{i,j\in B}$ be the transition matrix restricted to transitions that stay in $B$. This matrix is substochastic: each row sum is at most $1$. For $i\in B$, the row sum $\sum_{j\in B}(Q^n)_{ij}$ is the probability that the chain has stayed outside $A$ through time $n$.

The restricted matrix removes paths at the moment they enter $A$. Thus its powers track survival outside the target, rather than simply tracking the chain's location without regard to earlier visits. This gives a direct route to the hitting-time distribution.

Theorem (Hitting-time probabilities from the restricted matrix): Let $S$ be finite or countable, $A\subseteq S$, and $i\notin A$. Define $Q$ as above. For $n\ge0$, $$ \mathbb{P}_i(T_A>n)=\sum_{j\in B}(Q^n)_{ij}. $$ Consequently, for $n\ge1$, $$ f_{iA}(n)=\sum_{j\in B}(Q^{n-1})_{ij}-\sum_{j\in B}(Q^n)_{ij}. $$

Proof. For each $n\ge0$, the event $T_A>n$ means exactly that $X_0,\ldots,X_n$ all belong to $B$. By the Markov property, the probability of a particular length-$n$ path in $B$, starting from $i$, is the product of its transition probabilities. Summing these products over all such paths gives $\sum_{j\in B}(Q^n)_{ij}$, by the definition of matrix multiplication; for $n=0$, the sum is $1$ because $i\in B$. For $n\ge1$, the event $T_A=n$ is the difference between $T_A>n-1$ and $T_A>n$. Subtracting their probabilities gives the stated formula. The sums are valid for countable $B$ because all terms are nonnegative. $\square$

This result also shows how to calculate $f_{iA}(n)$ from the full transition matrix: keep only the transitions within $B$, take successive powers, and subtract consecutive survival probabilities. The first-hit probability at step $n$ is not generally the probability of being in $A$ at step $n$, because that latter event includes paths that entered $A$ before step $n$.

Worked Example: Hitting One State by Restricting the Matrix

Consider $S=\{0,1,2\}$, with transition matrix $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac13&0&\tfrac23\\ 0&0&1 \end{bmatrix}. $$ Each row sums to $1$: $\tfrac12+\tfrac12=1$, $\tfrac13+0+\tfrac23=1$, and $0+0+1=1$. Starting from $0$, find the first-hit probabilities for $A=\{2\}$ at steps $1$ through $4$.

The states outside $A$ are $B=\{0,1\}$, so $$ Q=\begin{bmatrix}\tfrac12&\tfrac12\\ \tfrac13&0\end{bmatrix}. $$ Its row sums are $1$ and $\tfrac13$, both at most $1$. Starting from $0$, the survival probabilities are $s_n=\mathbb{P}_0(T_A>n)=\sum_{j\in B}(Q^n)_{0j}$. First, $s_0=1$. The first row sum of $Q$ gives $s_1=1$, so $f_{0A}(1)=s_0-s_1=0$.

Next, $$ Q^2=\begin{bmatrix}\tfrac5{12}&\tfrac14\\ \tfrac16&\tfrac16\end{bmatrix}, \qquad s_2=\tfrac5{12}+\tfrac14=\tfrac23, \qquad f_{0A}(2)=s_1-s_2=1-\tfrac23=\tfrac13. $$ Multiplying the first row of $Q^2$ by $Q$ gives the first row of $Q^3$ as $(\tfrac7{24},\tfrac5{24})$. Therefore $s_3=\tfrac7{24}+\tfrac5{24}=\tfrac12$, and $f_{0A}(3)=s_2-s_3=\tfrac23-\tfrac12=\tfrac16$.

For the next step, the first row of $Q^4$ is $$ \left(\tfrac7{24},\tfrac5{24}\right)Q =\left(\tfrac7{48}+\tfrac5{72},\tfrac7{48}\right) =\left(\tfrac{31}{144},\tfrac{21}{144}\right). $$ Thus $s_4=\tfrac{31}{144}+\tfrac{21}{144}=\tfrac{13}{36}$, and $f_{0A}(4)=s_3-s_4=\tfrac12-\tfrac{13}{36}=\tfrac5{36}$.

Check: The probabilities of hitting by steps $1,2,3,4$ are respectively $1-s_1=0$, $1-s_2=\tfrac13$, $1-s_3=\tfrac12$, and $1-s_4=\tfrac{23}{36}$. Summing the computed masses gives $0+\tfrac13+\tfrac16+\tfrac5{36}=\tfrac{23}{36}$, as required.

First-Hit Decomposition Using n-Step Probabilities

There is another useful way to obtain first-hit probabilities: decompose an n-step transition according to the first time the target is reached. For a single target state $j$, define $f_{ij}(k)=\mathbb{P}_i(T_{\{j\}}=k)$ when $i\ne j$. When $i=j$, use $f_{jj}(k)=\mathbb{P}_j(T_j^+=k)$, so the first return starts counting at step $1$, not step $0$.

Theorem (First-hit decomposition): For $i\ne j$ and $n\ge1$, $$ p_{ij}^{(n)}=\sum_{k=1}^{n}f_{ij}(k)p_{jj}^{(n-k)}. $$ For returns to $i$ and $n\ge1$, the corresponding identity is $$ p_{ii}^{(n)}=\sum_{k=1}^{n}f_{ii}(k)p_{ii}^{(n-k)}. $$ In both identities $p_{jj}^{(0)}=p_{ii}^{(0)}=1$.

Proof. First take $i\ne j$. The event $X_n=j$ is partitioned by the first-hit time $k\in\{1,\ldots,n\}$, since a path ending at $j$ must have visited $j$ by time $n$. On the event $T_{\{j\}}=k$, the chain is at $j$ at time $k$. By the Markov property at the deterministic time $k$, the conditional probability of being at $j$ at time $n$ is $p_{jj}^{(n-k)}$. Multiplying by $\mathbb{P}_i(T_{\{j\}}=k)$ and summing over the disjoint cases gives the first identity. For the return identity, start at $i$ and partition the event $X_n=i$ by the first return time $T_i^+=k$. Every path with $X_n=i$, $n\ge1$, has such a first return with $k\le n$. Conditional on that first return, the probability of being at $i$ after the remaining $n-k$ steps is $p_{ii}^{(n-k)}$. Summing these disjoint cases gives the second identity. $\square$

Because the term with $k=n$ has a factor $p_{jj}^{(0)}=1$, these identities can be solved recursively. For $i\ne j$, $$ f_{ij}(n)=p_{ij}^{(n)}-\sum_{k=1}^{n-1}f_{ij}(k)p_{jj}^{(n-k)}. $$ For first returns, $$ f_{ii}(n)=p_{ii}^{(n)}-\sum_{k=1}^{n-1}f_{ii}(k)p_{ii}^{(n-k)}. $$ The sum is empty when $n=1$, so $f_{ij}(1)=p_{ij}$ for $i\ne j$ and $f_{ii}(1)=p_{ii}$. The recursion uses n-step probabilities, but subtracts the contributions from paths that reached the target earlier and then returned to it at the specified endpoint.

Worked Example: Recovering a First-Return Distribution

Let $S=\{0,1,2\}$, with transitions $0\to1$ with probability $1$, $1\to0$ and $1\to2$ with probability $\tfrac12$ each, and $2\to0$ with probability $1$. The matrix is $$ P=\begin{bmatrix}0&1&0\\ \tfrac12&0&\tfrac12\\ 1&0&0\end{bmatrix}. $$ The row sums are $1$, $\tfrac12+\tfrac12=1$, and $1$. Find the first-return probabilities to $0$ for the first four steps.

At step $1$, $p_{00}^{(1)}=0$, so $f_{00}(1)=0$. At step $2$, the path $0\to1\to0$ has probability $1\cdot\tfrac12=\tfrac12$, giving $p_{00}^{(2)}=\tfrac12$ and $f_{00}(2)=\tfrac12$. At step $3$, the path $0\to1\to2\to0$ has probability $1\cdot\tfrac12\cdot1=\tfrac12$. Hence $p_{00}^{(3)}=\tfrac12$, and the recursion gives $$ f_{00}(3)=p_{00}^{(3)}-f_{00}(1)p_{00}^{(2)}-f_{00}(2)p_{00}^{(1)} =\tfrac12-0\cdot\tfrac12-\tfrac12\cdot0=\tfrac12. $$

At step $4$, the only path from $0$ back to $0$ is $0\to1\to0\to1\to0$, with probability $1\cdot\tfrac12\cdot1\cdot\tfrac12=\tfrac14$. Therefore $$ f_{00}(4)=p_{00}^{(4)}-f_{00}(1)p_{00}^{(3)}-f_{00}(2)p_{00}^{(2)}-f_{00}(3)p_{00}^{(1)} =\tfrac14-0-\tfrac12\cdot\tfrac12-\tfrac12\cdot0=0. $$

Check: The return masses at steps $2$ and $3$ sum to $\tfrac12+\tfrac12=1$. In this chain, after a return to $0$, the next step is certainly to $1$; the next decision returns to $0$ after two steps or takes the three-step route through $2$. Thus no first return occurs at step $4$, matching the recursion.

Targets with More Than One State

For a set $A$ with several states, the restricted-matrix calculation gives the aggregate hitting-time distribution directly. The first-hit decomposition also applies, but it must retain the state in which the chain first enters $A$. Define $f_{ia}(k)=\mathbb{P}_i(T_A=k,\ X_k=a)$ for $a\in A$ and $i\notin A$. Then $$ \mathbb{P}_i(X_n\in A)=\sum_{k=1}^{n}\sum_{a\in A} f_{ia}(k)\sum_{b\in A}p_{ab}^{(n-k)}. $$ Indeed, the disjoint cases are the first entrance time $k$ and entrance state $a$, followed by the state at time $n$. The inner sum is the probability of being somewhere in $A$ after the remaining $n-k$ steps. At $k=n$, this inner sum is $1$. In general, knowing only the aggregate $f_{iA}(k)=\sum_{a\in A}f_{ia}(k)$ is not enough to use this equation: different entrance states can have different probabilities of being in $A$ later.

Worked Example: Hitting a Two-State Target

Take $S=\{0,1,2,3\}$, $A=\{2,3\}$, and $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0&0\\ \tfrac12&0&\tfrac14&\tfrac14\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}. $$ The row sums are $1$, $\tfrac12+\tfrac14+\tfrac14=1$, $1$, and $1$. States $2$ and $3$ are absorbing. Starting at $0$, calculate the probabilities of first hitting $A$ at steps $2,3,4$.

For $B=\{0,1\}$, the restricted matrix is $Q=\begin{bmatrix}\tfrac12&\tfrac12\\ \tfrac12&0\end{bmatrix}$, with row sums $1$ and $\tfrac12$. The first three powers have first rows $$ (Q^1)_{0,\cdot}=(\tfrac12,\tfrac12),\qquad (Q^2)_{0,\cdot}=(\tfrac12,\tfrac14),\qquad (Q^3)_{0,\cdot}=(\tfrac38,\tfrac14). $$ Their row sums are $s_1=1$, $s_2=\tfrac34$, and $s_3=\tfrac58$. Also $s_0=1$. Thus $f_{0A}(1)=s_0-s_1=0$, $f_{0A}(2)=s_1-s_2=\tfrac14$, and $f_{0A}(3)=s_2-s_3=\tfrac18$.

Multiplying the third first row by $Q$ gives $(Q^4)_{0,\cdot}=(\tfrac5{16},\tfrac3{16})$, whose sum is $s_4=\tfrac12$. Hence $f_{0A}(4)=s_3-s_4=\tfrac58-\tfrac12=\tfrac18$.

Check: Because $2$ and $3$ are absorbing, $\mathbb{P}_0(X_3\in A)$ equals the probability of having hit $A$ by step $3$, namely $1-s_3=\tfrac38$. The first-hit masses through step $3$ sum to $0+\tfrac14+\tfrac18=\tfrac38$, in agreement. The exact step-3 mass is only $\tfrac18$, not $\tfrac38$.

Common Pitfall and Interpretation

A frequent error is to equate $p_{ij}^{(n)}$ with the probability of first reaching $j$ at step $n$. For example, in the first worked example, $p_{02}^{(3)}=\tfrac12$: one contribution is a path that reaches state $2$ at step $2$ and remains there, and another is a path that first reaches $2$ at step $3$. The wrong calculation $f_{02}(3)=p_{02}^{(3)}=\tfrac12$ counts both. The correction is the first-hit decomposition: $$ p_{02}^{(3)}=f_{02}(2)p_{22}^{(1)}+f_{02}(3)p_{22}^{(0)} =\tfrac13\cdot1+f_{02}(3)\cdot1, \qquad f_{02}(3)=\tfrac12-\tfrac13=\tfrac16. $$ The distinction is essential whenever a question asks for the time of the first hit or first return rather than the state at a fixed time.

For a set target, the survival probabilities $\mathbb{P}_i(T_A>n)$ are nonincreasing in $n$, and their consecutive differences give the probability mass at each finite time. The total mass $\sum_{n\ge1}f_{iA}(n)$ can be less than $1$: this happens if the chain has positive probability never to hit $A$. The finite-time formulas do not assume that a hit eventually occurs. They describe the distribution at each finite step, while any remaining probability is assigned to $T_A=\infty$.

Use the restricted matrix when the main goal is a set-hitting distribution: it tracks paths that have avoided the target. Use the scalar first-hit recursion when the goal is a point target and n-step transition probabilities are already available. For multiple target states, either method works, but a first-hit decomposition must keep the entrance state when subsequent transition probabilities depend on which state was reached.

Check Your Understanding

For each question, distinguish an exact first-hit or first-return probability from the probability of being at the target at a specified step.

If $s_n=\mathbb{P}_i(T_A>n)$, express $\mathbb{P}_i(T_A=n)$ using $s_{n-1}$ and $s_n$. State the range of $n$.
For $i\ne j$, write the first-hit recursion that obtains $f_{ij}(n)$ from $p_{ij}^{(n)}$ and earlier first-hit probabilities.
Why does the return-time distribution use $n\ge1$, even though $X_0=i$ when the chain starts at $i$?
In the two-state target example, what is the probability of hitting $A$ by step $3$, and what is the probability of first hitting $A$ exactly at step $3$?
When $A$ has multiple states, explain why aggregate first-hit probabilities may not suffice for the first-hit decomposition based on $\mathbb{P}_i(X_n\in A)$.

Distributions of Hitting and Return Times

What You'll Learn