First-passage time
Topic of Random walks and first passage, part of Stochastic processes · Also in Discrete-time Markov chains
First-passage time
| Type | Topic |
| Taught in | Random walks and first passage · Discrete-time Markov chains |
| Part | Stochastic processes |
The first time T_A=\inf\{n\ge0:X_n\in A\} that a process enters a set A, with T_A=\infty if it never does. Its law depends on the whole path, not on the state at one fixed time. Gambler’s ruin and hitting probabilities are questions about it.
In Random walks and first passage
Drift accumulates like n. Typical fluctuations are of order \sqrt{n}. Neither statement is a first-passage probability. A first-passage event depends on the whole path, not on the single variable S_n. The four modes of the arrow \xrightarrow{d}, and the conditions under which a limit of distributions controls an expectation, are on Expectation and convergence.
In Discrete-time Markov chains
The first-step analysis on Random walks and first passage extends from a path graph to any transition matrix. For a target set A\subset S, let T_A=\inf\{n\ge 0: X_n\in A\}. For disjoint targets A and B, write h_i=\mathbb{P}_i(T_A<T_B). Conditioning on the first step gives
h_i=\sum_j p_{ij} h_j \quad(i\notin A\cup B), \qquad h_i=1\ (i\in A), \qquad h_i=0\ (i\in B).
If the mean hitting time of A is finite, e_i=\mathbb{E}_i T_A solves
e_i=1+\sum_j p_{ij} e_j \quad(i\notin A), \qquad e_i=0\ (i\in A).
The 1 is the step just taken. The sum is the expected remaining time from the next state. On a finite state space these are linear equations, one unknown per state outside the target.
Used in
See also
Gambler’s ruin · Hitting probabilities · Drift and scale of a random walk · Expected duration of a random walk · Solving the recurrences from scratch · Why the boundary problem is well posed