Hitting a Set: The Basic Question
In a discrete-time Markov chain, a boundary event is often described by asking when the chain first enters a designated set of states. The definition must account for a chain that starts in the set, one that reaches it later, and one that never reaches it. These cases are different: in particular, a hitting time is allowed to be infinite.
Let \((X_n)_{n\ge0}\) be a Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Use its natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\), which records the states observed through time \(n\). For a starting state \(i\), write \(\mathbb{P}_i\) for probabilities when \(X_0=i\). For any set \(A\subseteq S\), define
The infimum is over integer times beginning at zero. Thus, if \(X_0\in A\), then \(T_A=0\). If the chain never visits \(A\), then the set inside the infimum is empty and \(T_A=\infty\). In particular, \(T_{\varnothing}=\infty\) on every sample path, while \(T_S=0\) on every sample path.
For a single state \(i\), the hitting time \(T_{\{i\}}\) includes time zero. The first return time instead starts the search at time one:
When \(X_0=i\), \(T_{\{i\}}=0\), whether or not the chain ever visits \(i\) again. By contrast, \(T_i^+\) records the first return after the initial visit and can be infinite. For a set of designated absorbing states \(C\), the absorption time is commonly defined as \(T_C\). If the chain starts in \(C\), that time is zero. The word “absorption” refers to the chain entering the designated absorbing states; it does not change the definition of a hitting time.
Two Properties of Hitting Times
Proof. Fix \(n\ge0\). The event that the first visit to \(A\) has occurred by time \(n\) is exactly the event that at least one of \(X_0,\ldots,X_n\) belongs to \(A\). Therefore \(\{T_A\le n\}=\bigcup_{m=0}^n\{X_m\in A\}\). Each event \(\{X_m\in A\}\) belongs to \(\mathcal{F}_m\), and \(\mathcal{F}_m\subseteq\mathcal{F}_n\) for \(m\le n\). A finite union of events in \(\mathcal{F}_n\) is in \(\mathcal{F}_n\), proving the stopping-time condition. This also covers \(A=\varnothing\), when the union is empty, and \(A=S\), when it is the whole sample space. \(\square\)
Proof. Consider any sample path. If \(T_A=\infty\), the claimed inequality holds because \(T_B\le\infty\). If \(T_A=m<\infty\), then \(X_m\in A\subseteq B\). Thus the chain has entered \(B\) by time \(m\), so the first time it enters \(B\) satisfies \(T_B\le m=T_A\). This includes the case \(m=0\) and the case \(A=\varnothing\), for which only the first case applies. \(\square\)
The set-inclusion property is useful when the target is a boundary set. For example, if \(A\) is one particular boundary state and \(B\) is the set of all boundary states, then reaching either boundary cannot take longer than reaching that particular boundary on the same path. This is a pathwise comparison; it does not require a Markov-chain calculation.
Worked Examples
Worked Example: Hitting, Returning, and Absorption
Consider a chain on \(S=\{0,1,2\}\) with transition matrix
Each row sums to \(1\): the row sums are \(0+1+0=1\), \(0+0+1=1\), and \(0+0+1=1\). Starting from state \(0\), the path is \(0,1,2,2,\ldots\). For \(A=\{2\}\), the first index \(n\ge0\) with \(X_n\in A\) is \(n=2\), so \(T_A=2\). For \(B=\{1,2\}\), the first such index is \(n=1\), so \(T_B=1\). This verifies \(T_B\le T_A\) because \(A\subseteq B\).
Now start the chain at state \(2\). Since \(2\in A\), the hitting time \(T_A\) is \(0\). But \(2\) is absorbing, so \(X_n=2\) for all \(n\ge0\), and the first return time is \(T_2^+=1\). If \(C=\{2\}\) is the designated absorbing set, the absorption time from state \(0\) is \(T_C=2\), and from state \(2\) it is \(T_C=0\).
Check: The path from \(0\) is \(X_0=0\), \(X_1=1\), and \(X_2=2\), so \(T_{\{2\}}=2\) directly from the definition. Starting at \(2\), \(X_0=2\) gives \(T_{\{2\}}=0\), while \(X_1=2\) gives \(T_2^+=1\). The difference comes from the time indices in the two definitions.
Worked Example: Positive Probability of Never Hitting
Consider a chain on \(S=\{0,1,2\}\) with transition matrix
The row sums are \(\tfrac12+\tfrac12=1\), \(0+1+0=1\), and \(0+0+1=1\), so the rows are probability distributions. Start at \(0\) and take \(A=\{2\}\). From \(0\), the chain moves to \(2\) with probability \(\tfrac12\), in which case \(T_A=1\). It moves to \(1\) with probability \(\tfrac12\), in which case it stays at \(1\) forever and \(T_A=\infty\). Consequently, \(\mathbb{P}_0(T_A=1)=\tfrac12\), \(\mathbb{P}_0(T_A=\infty)=\tfrac12\), and \(\mathbb{P}_0(T_A<\infty)=\tfrac12\).
For this nonnegative extended-valued random variable, its expectation is infinite. Indeed, for every positive integer \(M\), \(T_A\ge M\mathbf{1}_{\{T_A=\infty\}}\), so \(\mathbb{E}_0[T_A]\ge M\mathbb{P}_0(T_A=\infty)=M/2\). Since this lower bound holds for every \(M\), the expectation cannot be finite. Notice that there is a one-step path from \(0\) to \(2\), but that does not guarantee the chain takes that path.
For a different target, \(B=\{1,2\}\), both possible moves from \(0\) enter the target at time one. Thus \(T_B=1\) with probability \(1\). The same chain can therefore have a finite hitting time for one target and a positive probability of an infinite hitting time for another.
Check: The only two possible first moves from \(0\) have probabilities \(\tfrac12\) and \(\tfrac12\), whose sum is \(1\). After the move to \(1\), the transition \(p_{11}=1\) prevents any later visit to \(2\); after the move to \(2\), the first visit to \(A\) has already occurred at time \(1\).
Worked Example: A Boundary Set and a Boundary Return
Let \(S=\{0,1,2\}\), with boundary states \(0\) and \(2\). From state \(1\), the chain moves to \(0\) or \(2\) with probability \(\tfrac12\) each; both boundary states are absorbing. In the order \(0,1,2\), the transition matrix is
The row sums are \(1+0+0=1\), \(\tfrac12+0+\tfrac12=1\), and \(0+0+1=1\). Let \(C=\{0,2\}\) be the boundary set. Starting at \(1\), the next state is in \(C\) with probability \(\tfrac12+\tfrac12=1\), so \(T_C=1\) with probability \(1\). Starting at \(0\), however, \(T_C=0\), because the chain is already in the target. Its first return time to \(0\) is \(T_0^+=1\), because \(p_{00}=1\).
If the target is the single boundary state \(A=\{2\}\) and the chain starts at \(1\), then \(T_A=1\) with probability \(\tfrac12\), and \(T_A=\infty\) with probability \(\tfrac12\): a move to \(0\) leaves the chain at \(0\) forever. Thus “hit the boundary” and “hit a specified boundary point” are different events.
Check: The probability of entering \(C\) on the first step from \(1\) is \(p_{10}+p_{12}=\tfrac12+\tfrac12=1\). The probability of entering \(A=\{2\}\) on that step is \(p_{12}=\tfrac12\); the remaining probability \(p_{10}=\tfrac12\) leads to the absorbing state \(0\), which is not in \(A\).
Reading Infinite Values Correctly
An equality \(T_A=\infty\) on a sample path has a precise meaning: for every integer \(n\ge0\), \(X_n\notin A\). It does not mean that the chain is “taking a very long time” on that path; it means there is no finite visit at all. In probability statements, distinguish \(\mathbb{P}_i(T_A<\infty)=1\), which says the target is eventually reached almost surely, from a guarantee of reaching it on every possible path. In the second worked example, the target is reachable in one step, but the probability of eventual hitting is only \(\tfrac12\).
The definition also identifies the relevant boundary convention. A hitting time uses \(n\ge0\), so starting inside the target gives time zero. A return time uses \(n\ge1\), so the initial occurrence does not count as a return. When an absorbing set is the target, its entry time is zero for a chain already in that set; an absorption-time question must therefore state the initial state or initial distribution.
Common mistake. A frequent error is to define the hitting time as \(\inf\{n\ge1:X_n\in A\}\) even when asking for the first hit, and then to report \(T_A=1\) for a chain that starts in \(A\). That calculation uses the return-time convention, not the hitting-time convention. For example, in the first worked example started at \(2\), the correct first hitting time of \(\{2\}\) is \(0\), while the first return time to \(2\) is \(1\). The correction is to use \(n\ge0\) for first hitting and \(n\ge1\) for first return.
Check Your Understanding
Use the definitions directly, and state whether each time is finite or infinite on the paths in question.
- If \(X_0\in A\), what is \(T_A\)? How does the answer differ for \(T_i^+\) when \(X_0=i\)?
- For the second worked example, find \(\mathbb{P}_0(T_{\{1,2\}}=1)\) and \(\mathbb{P}_0(T_{\{2\}}=\infty)\).
- If \(A\subseteq B\), which hitting time is no larger on each sample path, \(T_A\) or \(T_B\)? Explain using the definition.
- In the boundary example, starting at \(1\), compare the probability of hitting \(\{0,2\}\) at time \(1\) with the probability of hitting \(\{2\}\) at time \(1\).
- Why is a positive-probability path from the initial state to a target not enough to conclude that the target is reached almost surely?