First Entrance and the Information Available
A first-entry time records when a process first reaches a specified set. The key question is not whether the time is random, but whether deciding that entry has happened by time \(n\) requires only information available by time \(n\). This makes first-entry times a basic source of stopping times, including for processes that may later leave the set they have entered.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\) with a discrete-time filtration \((\mathcal{F}_n)_{n\ge0}\), an increasing family of sigma-fields. A process \((X_n)_{n\ge0}\) with values in a measurable state space \((S,\mathcal{S})\) is adapted to this filtration if \(X_n\) is \(\mathcal{F}_n\)-measurable for each \(n\). A random time \(\tau\), taking values in \(\{0,1,2,\ldots\}\cup\{\infty\}\), is a stopping time if \(\{\tau\le n\}\in\mathcal{F}_n\) for every \(n\ge0\).
Proof. For the state-set rule, adaptedness and measurability of \(A\) imply \(\{X_k\in A\}\in\mathcal{F}_k\). Since the filtration is increasing, \(\mathcal{F}_k\subseteq\mathcal{F}_n\) whenever \(k\le n\). By the definition of an infimum over integer times, \(T_A\le n\) holds exactly when \(X_k\in A\) for at least one \(k\in\{0,\ldots,n\}\). Thus \[ \{T_A\le n\}=\bigcup_{k=0}^{n}\{X_k\in A\}\in\mathcal{F}_n. \] This holds for every \(n\), so \(T_A\) is a stopping time. For the more general rule, \(\{\tau\le n\}=\bigcup_{k=0}^{n}C_k\); each \(C_k\in\mathcal{F}_k\subseteq\mathcal{F}_n\), so this finite union belongs to \(\mathcal{F}_n\). Hence \(\tau\) is a stopping time as well. These arguments also cover \(A=\varnothing\) or \(C_k=\varnothing\) for every \(k\): the relevant event is empty and belongs to every sigma-field. \(\square\)
The theorem applies to any adapted process with measurable state sets; it does not require the Markov property. In particular, it does not require that the process stay in \(A\) after entering. For finite or countable state spaces with all subsets measurable, every set of states is an eligible target. For a real-valued adapted process, sets such as \([a,\infty)\) are measurable, so first crossing a threshold is covered too.
Worked Applications
Worked Example: A Simple Random Walk Crossing a Level
Let \((\xi_n)_{n\ge1}\) be independent random variables with \(\mathbb{P}(\xi_n=1)=\mathbb{P}(\xi_n=-1)=\tfrac12\). On their probability space, let \(S_0=0\), \(S_n=\sum_{r=1}^{n}\xi_r\), and \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0\) trivial. Find the probability that \(T=\inf\{n\ge0:S_n\ge1\}\) is at most \(3\), and find the probability that \(T=3\).
The process is adapted because \(S_n\) is determined by \(\xi_1,\ldots,\xi_n\). The target set is \(A=\{1,2,\ldots\}\), so the first-entry theorem makes \(T\) a stopping time. The eight equally likely length-three increment sequences each have probability \((\tfrac12)^3=\tfrac18\). If the first increment is \(+1\), the walk has already entered \(A\), giving four sequences. If the first increment is \(-1\), it enters \(A\) by time \(3\) only for the sequence \((-1,+1,+1)\): its successive positions are \(-1,0,1\). Therefore \[ \mathbb{P}(T\le3)=\frac{4}{8}+\frac{1}{8}=\frac{5}{8}. \] For \(T=3\), the walk must not enter at time \(1\) or \(2\). The only length-three sequence that first reaches level \(1\) at time \(3\) is \((-1,+1,+1)\), so \(\mathbb{P}(T=3)=\tfrac18\).
Check: The paths first entering at time \(1\) have first increment \(+1\), so \(\mathbb{P}(T=1)=\tfrac12=\tfrac48\). There are no paths with \(T=2\), because the position at time \(2\) is even. Thus \(\mathbb{P}(T\le3)=\tfrac48+0+\tfrac18=\tfrac58\), as computed.
Worked Example: First Entry in a Finite-State Chain
Let \((X_n)_{n\ge0}\) be a Markov chain on \(S=\{0,1,2\}\), started at \(X_0=0\), with its natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). In state order \(0,1,2\), let \[ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac13&\tfrac23\\ 0&0&1 \end{bmatrix}. \] For the target \(A=\{2\}\), compute \(\mathbb{P}_0(T_A\le3)\) and \(\mathbb{P}_0(T_A=3)\).
Before using the transition matrix, check its rows: \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac13+\tfrac23=1\), and \(0+0+1=1\). The target is measurable, and the chain is adapted to its natural filtration, so the first-entry theorem applies. Since the chain starts at \(0\), it cannot enter \(A\) at time \(0\). It cannot enter at time \(1\) either, because \(p_{02}=0\).
To enter for the first time at time \(2\), the chain must follow \(0\to1\to2\). Its probability is \[ \mathbb{P}_0(T_A=2)=\tfrac12\cdot\tfrac23=\tfrac13. \] To enter for the first time at time \(3\), the path must be \(0\to0\to1\to2\) or \(0\to1\to1\to2\). These probabilities are \[ \tfrac12\cdot\tfrac12\cdot\tfrac23=\tfrac16,\qquad \tfrac12\cdot\tfrac13\cdot\tfrac23=\tfrac19. \] Their sum is \(\tfrac16+\tfrac19=\tfrac3{18}+\tfrac2{18}=\tfrac5{18}\). Consequently, \[ \mathbb{P}_0(T_A\le3)=\tfrac13+\tfrac5{18}=\tfrac6{18}+\tfrac5{18}=\tfrac{11}{18}. \]
Check: The probability of no entry by time \(3\) is \(\tfrac7{18}\). The surviving paths are \(0\to0\to0\to0\) and \(0\to0\to0\to1\), each with probability \(\tfrac18\); \(0\to0\to1\to1\), with probability \(\tfrac1{12}\); and \(0\to1\to1\to1\), with probability \(\tfrac1{18}\). Their total is \(\tfrac18+\tfrac18+\tfrac1{12}+\tfrac1{18}=\tfrac9{72}+\tfrac9{72}+\tfrac6{72}+\tfrac4{72}=\tfrac{28}{72}=\tfrac7{18}\). Thus the entry probability is \(1-\tfrac7{18}=\tfrac{11}{18}\), in agreement.
Worked Example: A Threshold for a Success Count
Let \((Z_n)_{n\ge1}\) be independent Bernoulli random variables with \(\mathbb{P}(Z_n=1)=\mathbb{P}(Z_n=0)=\tfrac12\). Define \(Y_0=0\), \(Y_n=\sum_{r=1}^{n}Z_r\), and \(\mathcal{F}_n=\sigma(Z_1,\ldots,Z_n)\). For \(T=\inf\{n\ge0:Y_n\ge2\}\), compute \(\mathbb{P}(T\le4)\), and the probabilities that \(T=2,3,4\).
Here \(Y_n\) is adapted, and \(T\) is the first entry into the measurable set \(\{2,3,\ldots\}\); hence \(T\) is a stopping time. Because \(Y_n\) never decreases, the event \(\{T\le n\}\) is exactly \(\{Y_n\ge2\}\). Among the \(2^4=16\) equally likely sequences of four Bernoulli outcomes, the number with at least two successes is \[ \binom42+\binom43+\binom44=6+4+1=11. \] Therefore \(\mathbb{P}(T\le4)=\tfrac{11}{16}\).
At time \(2\), entry occurs exactly when both outcomes are successes, so \(\mathbb{P}(T=2)=\tfrac14\). Among the eight equally likely sequences of length \(3\), \(\binom32+\binom33=3+1=4\) have at least two successes. Thus \(\mathbb{P}(T\le3)=\tfrac48=\tfrac12\), and \[ \mathbb{P}(T=3)=\mathbb{P}(T\le3)-\mathbb{P}(T\le2)=\tfrac12-\tfrac14=\tfrac14. \] Finally, \[ \mathbb{P}(T=4)=\mathbb{P}(T\le4)-\mathbb{P}(T\le3)=\tfrac{11}{16}-\tfrac12=\tfrac3{16}. \]
Check: The three probabilities sum to \(\tfrac4{16}+\tfrac4{16}+\tfrac3{16}=\tfrac{11}{16}\), the probability of entry by time \(4\). There is no possibility of entry at time \(0\) or \(1\), since at most one success can have occurred by time \(1\).
Why the First-Entry Form Matters
For a nondecreasing count such as \(Y_n\), testing whether the current value has crossed the threshold is enough: \(\{T\le n\}=\{Y_n\ge2\}\). That shortcut does not hold for a process that can leave the target set. In general, the correct event is the union over all observations so far, \(\bigcup_{k=0}^{n}\{X_k\in A\}\), not merely \(\{X_n\in A\}\).
Common mistake. In the random-walk example, using only the endpoint gives \(\mathbb{P}(S_3\ge1)=\tfrac12\): among eight paths, four have at least two \(+1\) increments. But this is not the probability of having crossed level \(1\) by time \(3\). The path \((+1,-1,-1)\) crosses at time \(1\) and ends at \(-1\). Counting it gives \(\mathbb{P}(T\le3)=\tfrac12+\tfrac18=\tfrac58\). The endpoint test misses a path that entered and then left the target.
A different error is to let a proposed “entry rule” use future information. For example, in the simple random walk with trivial \(\mathcal{F}_0\), define \(\tau=0\) if \(\xi_1=\xi_2=1\), and \(\tau=1\) otherwise. Then \(\{\tau\le0\}=\{\xi_1=\xi_2=1\}\), an event of probability \(\tfrac14\). A trivial sigma-field contains only events of probability \(0\) or \(1\), so this event is not in \(\mathcal{F}_0\); \(\tau\) is not a stopping time. A first-entry rule avoids this problem because the decision by time \(n\) is built only from events observable by time \(n\).
Check Your Understanding
Use the first-entry event identity and check each probability by counting paths or substituting into the relevant event.
- For an adapted process and measurable \(A\), write \(\{T_A\le n\}\) as a union of events. Why does each event in the union belong to \(\mathcal{F}_n\)?
- For the random walk in the example, what is the probability of first entering \(\{1,2,\ldots\}\) at time \(1\)?
- In the finite-state chain, what is the probability of first entering \(\{2\}\) at time \(2\)? Show the transition factors.
- For the Bernoulli success count, explain why \(\{T\le n\}=\{Y_n\ge2\}\), and calculate \(\mathbb{P}(T\le3)\).
- Give a reason why checking only \(X_n\in A\) can fail to determine whether \(T_A\le n\).