Hitting probabilities
Section of Discrete-time Markov chains, part of Stochastic processes
Hitting probabilities
| Type | Section |
| Taught in | Discrete-time Markov chains |
| Part | Stochastic processes |
| Questions using it | 2 |
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
- Taught in Discrete-time Markov chains
- Also used in Random walks and first passage
- Questions that use it (2) — A fair walk between 0 and 8 (answer) · A biased walk on four steps (answer)
- All 3 questions on Discrete-time Markov chains
See also
First-passage time · Discrete-time Markov chain · Stationary distribution · Transition matrix · Spectral view for two states · Markov assumption as a chosen state · Stationarity and the law from one start · Doubly stochastic matrix