Hitting Probabilities and Expected Hitting Times

Intuition Beginner

A Markov chain wanders among its states one step at a time. Two of the most natural questions you can ask are: starting from where I am now, will I ever reach a particular target set of states? And if I will, how long should I expect to wait? The first question is about a chance — the hitting probability. The second is about an average waiting time — the expected hitting time. Almost every concrete use of a Markov chain comes down to one of these two numbers.

Think of a token sitting on a row of squares numbered from $0$ to $10$, with a wall at each end. At each step the token moves one square left or right by chance. The squares $0$ and $10$ are the targets: the game ends the moment the token reaches either wall. Starting from square $7$, you might ask for the chance that the token reaches the right wall $10$ before the left wall $0$. That is a hitting probability for the target set "right wall". You might also ask how many steps, on average, until the token hits either wall and the game ends. That is an expected hitting time.

The tool that cracks both questions is the same simple idea, called first-step analysis. Stand on your current square and look one move ahead. The chance of eventually reaching the target from here is the average, over the possible next squares, of the chance of reaching the target from each of those. The expected time to reach the target from here is one step (for the move you are about to take) plus the average of the expected times from wherever you land. In each case you relate the unknown at your square to the unknowns at the neighboring squares, and you get one equation per square. Solving the whole system of equations gives every answer at once.

There is one wrinkle worth flagging early. Sometimes these equations have more than one solution, and only one of them is the true answer. The true hitting probability and the true expected time are always the smallest non-negative solution of their equations. Picking the smallest is how you avoid spurious answers that the bare equations would otherwise allow.

The one-sentence takeaway: to find the chance of reaching a target set and the average time to reach it, set up one first-step equation per state and take the smallest non-negative solution.

Visual Beginner

Picture the numbered squares from $0$ to $10$ with walls at both ends and a token in the middle.

The two walls are the targets: once the token lands on $0$ or $10$ the walk stops. For the hitting probability of the right wall, the boundary values are fixed — chance $1$ if you start on $10$, chance $0$ if you start on $0$ — and every interior square's value is the average of its two neighbors. For the expected time to reach a wall, the boundary values are both $0$ (you are already there) and every interior square's value is one plus the average of its neighbors. The "plus one" is the single extra step you always spend before landing somewhere new.

Worked example Beginner

Take the smaller walk on squares $\{0,1,2,3,4\}$ with walls at $0$ and $4$. From each interior square $1,2,3$ the token moves left or right with chance one half each. We find the chance of reaching the right wall $4$ before the left wall $0$, starting from each interior square.

Step 1. Name the unknowns. Let $h_1,h_2,h_3$ be the chances of hitting $4$ before $0$, starting from squares $1,2,3$. The boundary values are forced: $h_0=0$ (you start on the left wall, so you never reach the right one first) and $h_4=1$ (you start on the right wall).

Step 2. Write one first-step equation per interior square. From square $2$ the token goes to $1$ or $3$ with chance one half each, so $h_2=\frac{1}{2}{h}_1+\frac{1}{2}{h}_3$. Likewise $h_1=\frac{1}{2}{h}_0+\frac{1}{2}{h}_2=\frac{1}{2}{h}_2$ and $h_3=\frac{1}{2}{h}_2+\frac{1}{2}{h}_4=\frac{1}{2}{h}_2+\frac{1}{2}$.

Step 3. Solve. Substitute the expressions for $h_1$ and $h_3$ into the equation for $h_2$: $h_2=\frac{1}{2}(\frac{1}{2}{h}_2)+\frac{1}{2}(\frac{1}{2}{h}_2+\frac{1}{2})=\frac{1}{2}{h}_2+\frac{1}{4}$. So $\frac{1}{2}{h}_2=\frac{1}{4}$, giving $h_2=\frac{1}{2}$.

Step 4. Back-substitute. Then $h_1=\frac{1}{2}{h}_2=\frac{1}{4}$ and $h_3=\frac{1}{2}{h}_2+\frac{1}{2}=\frac{3}{4}$.

Step 5. Sanity check. The answers $h_1=1/4$, $h_2=1/2$, $h_3=3/4$ are exactly the starting square divided by $4$. That matches the intuition that, in a fair walk, the chance of reaching the right wall first is proportional to how close you start to it.

What this tells us: by writing the chance at each square as the average of the chances at its neighbors and pinning the two boundary values, we turned a question about a random journey of unknown length into a small system of three equations. The hitting probability from square $i$ came out as $i/4$, a clean answer that no amount of step-by-step simulation would have handed us so cleanly.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $(X_n{)}_{n\ge 0}$ is a time-homogeneous Markov chain on a countable state space $I$ with stochastic transition matrix $P=(p_{ij})$, in the sense of 37.05.01, and ${\mathbb{P}}_i$, ${\mathbb{E}}_i$ denote probability and expectation for the chain started at $X_0=i$. The class structure of 37.05.02 organizes which targets are reachable.

Definition (hitting time). Let $A\subseteq I$ be a target set. The hitting time of $A$ is the random variable $$H^A:=\inf \{n\ge 0:X_n\in A\},$$ with the convention $\inf \varnothing =+\infty$, so $H^A=\infty$ on the event that the chain never enters $A$. It is a stopping time for the filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, since $\{H^A\le n\}={\bigcup }_{m\le n}\{X_m\in A\}\in {\mathcal{F}}_n$. When $A=\{j\}$ is a single state, write $H^j$. The first return time $T_j:=\inf \{n\ge 1:X_n=j\}$ differs from $H^j$ only by the lower index bound $n\ge 1$.

Definition (hitting probability). The hitting probability of $A$ from $i$ is $$h_i^A:={\mathbb{P}}_i(H^A<\infty )={\mathbb{P}}_i(X_n\in A\text{ for some }n\ge 0).$$ The vector $h^A=(h_i^A{)}_{i\in I}$ takes values in $[0,1]$ and satisfies $h_i^A=1$ for $i\in A$. For finite chains in which $A$ is reached with probability one from every state, $h^A\equiv 1$; the interesting case is when several disjoint targets compete, and $h_i^A$ is the absorption probability into $A$.

Definition (mean hitting time). The mean (expected) hitting time of $A$ from $i$ is $$k_i^A:={\mathbb{E}}_i[H^A]=\sum _{n\ge 0}n{\mathbb{P}}_i(H^A=n)+\infty \cdot {\mathbb{P}}_i(H^A=\infty ),$$ taking the value $+\infty$ whenever ${\mathbb{P}}_i(H^A=\infty )>0$, and otherwise the ordinary expectation of the integer-valued $H^A$. Then $k_i^A=0$ for $i\in A$.

Definition (first-step / hitting system). The hitting-probability system associated with $A$ is the set of linear constraints on a vector $x=(x_i{)}_{i\in I}$: $$x_i=1(i\in A),x_i=\sum _{j\in I}{p}_{ij}{x}_j(i\notin A).\text{\hspace{1em}(H)}$$ The mean-hitting-time system is $$x_i=0(i\in A),x_i=1+\sum _{j\notin A}{p}_{ij}{x}_j(i\notin A).\text{\hspace{1em}(K)}$$ A solution is non-negative if $x_i\ge 0$ for all $i$ (and, for (K), values in $[0,\infty ]$ are permitted). The central theorem identifies $h^A$ and $k^A$ as the minimal non-negative solutions of (H) and (K).

Counterexamples to common slips Intermediate+

• The first-step equations alone do not determine $h^A$. On the unrestricted random walk on ${\mathbb{Z}}_{\ge 0}$ with $p_{i,i+1}=p_{i,i-1}=1/2$ for $i\ge 1$ and $A=\{0\}$, the system (H) reads $x_i=\frac{1}{2}{x}_{i-1}+\frac{1}{2}{x}_{i+1}$, whose solutions are the affine functions $x_i=a+bi$. The constraint $x_0=1$ and $0\le x_i\le 1$ forces $b\le 0$; the genuine hitting probability is the minimal such, $x_i\equiv 1$ (recurrence), not the family $1-bi$. Minimality is what selects the right one.

• Hitting probability and return probability differ. $h_j^j=1$ always (you start in $A=\{j\}$), whereas the return probability ${\mathbb{P}}_j(T_j<\infty )$ can be less than one. The lower index bound $n\ge 0$ versus $n\ge 1$ is the whole distinction; conflating $H^j$ with $T_j$ misstates recurrence.

• A finite expected hitting time is strictly stronger than hitting with probability one. On the symmetric walk on $\mathbb{Z}$, the origin is hit from any start with probability one ($h=1$), yet the mean hitting time is $+\infty$. Solving (K) and obtaining a finite number presupposes the minimal solution is finite, which can fail even when (H) gives $h\equiv 1$.

• The sum in (K) runs over $j\notin A$, not all $j$. Once the chain enters $A$ it stops; the future steps from inside $A$ contribute nothing to $H^A$. Writing ${\sum }_{j\in I}$ instead of ${\sum }_{j\notin A}$ double-counts the terminal step and corrupts the system.

Key theorem with proof Intermediate+

Theorem (hitting probabilities are the minimal non-negative solution). The vector of hitting probabilities $h^A=(h_i^A{)}_{i\in I}$ is the minimal non-negative solution of the system (H): it solves (H), and if $x=(x_i)$ is any non-negative solution of (H), then $x_i\ge h_i^A$ for all $i$ ^{[Norris 1997 §1.3]}.

Proof. We first show $h^A$ solves (H), then prove minimality by an iterated-substitution argument.

Step 1 ($h^A$ solves (H)). For $i\in A$, $H^A=0$ under ${\mathbb{P}}_i$, so $h_i^A=1$. Fix $i\notin A$. Then $X_0=i\notin A$ forces $H^A\ge 1$, and conditioning on the first step $X_1=j$, $$h_i^A={\mathbb{P}}_i(H^A<\infty )=\sum _{j\in I}{\mathbb{P}}_i(X_1=j){\mathbb{P}}_i(H^A<\infty \mid X_1=j).$$ By the Markov property of 37.05.01, conditionally on $X_1=j$ the post-time-$1$ chain is $\mathrm{Markov}({\delta }_j,P)$ and independent of $X_0$, and the event $\{H^A<\infty \}$ from time $1$ onward is the event that this restarted chain hits $A$. Hence ${\mathbb{P}}_i(H^A<\infty \mid X_1=j)=h_j^A$, and since ${\mathbb{P}}_i(X_1=j)=p_{ij}$, $$h_i^A=\sum _{j\in I}{p}_{ij}{h}_j^A(i\notin A).$$ Thus $h^A$ satisfies (H).

Step 2 (minimality). Let $x\ge 0$ solve (H). On $A$, $x_i=1=h_i^A$. Fix $i\notin A$ and unfold (H) repeatedly. Since $x_j=1$ for $j\in A$, $$x_i=\sum _j{p}_{ij}{x}_j=\sum _{j\in A}{p}_{ij}+\sum _{j\notin A}{p}_{ij}{x}_j={\mathbb{P}}_i(X_1\in A)+\sum _{j\notin A}{p}_{ij}{x}_j.$$ Substitute the same expansion for each $x_j$ with $j\notin A$: $$x_i={\mathbb{P}}_i(X_1\in A)+\sum _{j\notin A}{p}_{ij}({\mathbb{P}}_j(X_1\in A)+\sum _{k\notin A}{p}_{jk}{x}_k)={\mathbb{P}}_i(X_1\in A)+{\mathbb{P}}_i(X_1\notin A,X_2\in A)+\sum _{j,k\notin A}{p}_{ij}{p}_{jk}{x}_k,$$ using the finite-dimensional law of 37.05.01 to recognize ${\sum }_{j\notin A}{p}_{ij}{\mathbb{P}}_j(X_1\in A)={\mathbb{P}}_i(X_1\notin A,X_2\in A)$. Iterating $n$ times, $$x_i=\sum _{m=1}^n{\mathbb{P}}_i(X_1\notin A,\dots ,X_{m-1}\notin A,X_m\in A)+\sum _{j_1,\dots ,j_n\notin A}{p}_{i{j}_1}{p}_{j_1{j}_2}\cdots p_{j_{n-1}{j}_n}{x}_{j_n}.$$ The first sum is exactly ${\mathbb{P}}_i(H^A\le n)$, and the second (remainder) term is non-negative because $x\ge 0$ and all $p$ are non-negative. Therefore $$x_i\ge {\mathbb{P}}_i(H^A\le n)\text{for every }n.$$ Letting $n\to \infty$, ${\mathbb{P}}_i(H^A\le n)\uparrow {\mathbb{P}}_i(H^A<\infty )=h_i^A$ by continuity of measure along the increasing events $\{H^A\le n\}$. Hence $x_i\ge h_i^A$. As $i$ was arbitrary, $x\ge h^A$ pointwise, which is minimality. $\square$

Bridge. This theorem builds toward the entire potential-theoretic and stationary theory of Markov chains, and the same minimal-solution principle appears again in the mean-hitting-time system (K), where $k^A$ is the minimal non-negative solution. The foundational reason both systems behave the same way is that first-step analysis is exactly the one-step conditioning afforded by the Markov property of 37.05.01: the unknown at a state is its target value plus a non-negative average over the next state, so iterating the equation reconstructs the chain's law up to time $n$ and leaves a non-negative remainder. This is exactly the discrete analogue of the boundary-value problem $Lh=0$ on the complement of $A$ with $h=1$ on $A$, with the discrete generator $P-I_d$ playing the role of the Laplacian; the minimal-solution selection generalises to the Perron-Wiener-Brelot solution of the Dirichlet problem in classical potential theory, and the dichotomy "$h^A\equiv 1$ versus $h^A<1$" is dual to the recurrence/transience split organized by the class structure of 37.05.02. The central insight is that absorption probabilities, recurrence, and expected costs are all minimal non-negative solutions of a linear system read off from $P$, and putting these together, hitting theory is the harmonic analysis of the operator $P$ relative to a boundary set $A$.

Exercises Intermediate+

Advanced results Master

Hitting theory is the discrete potential theory of the operator $P$ relative to a boundary set $A$. The minimal-solution principle, the probabilistic representation of solutions, and the reward generalization organize the subject; the gambler's ruin and birth–death chains instantiate each closed form.

Theorem 1 (mean hitting times as the minimal non-negative solution). The vector $k^A=(k_i^A{)}_{i\in I}$ of mean hitting times is the minimal non-negative solution in $[0,\infty ]$ of the system (K): $k_i^A=0$ for $i\in A$ and $k_i^A=1+{\sum }_{j\notin A}{p}_{ij}{k}_j^A$ for $i\notin A$. The proof parallels the hitting-probability case: first-step analysis shows $k^A$ solves (K), and for any non-negative solution $y$ of (K), iterated substitution yields $y_i\ge {\sum }_{m=1}^n{\mathbb{P}}_i(H^A\ge m)={\mathbb{E}}_i[H^A\wedge n]$ for every $n$, and letting $n\to \infty$ via monotone convergence gives $y_i\ge {\mathbb{E}}_i[H^A]=k_i^A$. The identity ${\mathbb{E}}_i[H^A]={\sum }_{m\ge 1}{\mathbb{P}}_i(H^A\ge m)$ (tail-sum formula for a non-negative integer variable) is what converts the iterated remainder into the mean.

Theorem 2 (probabilistic solution of the Dirichlet–Poisson problem). Let $A\subseteq I$ and suppose ${\mathbb{P}}_i(H^A<\infty )=1$ for all $i$. For a bounded boundary datum $f:A\to \mathbb{R}$ and a cost $g:I\setminus A\to {\mathbb{R}}_{\ge 0}$, the function $${\varphi }_i:={\mathbb{E}}_i\left[f(X_{H^A})+\sum _{n=0}^{H^A-1}g(X_n)\right]$$ is, when finite, the minimal non-negative-plus-bounded solution of the discrete Dirichlet–Poisson problem $${\varphi }_i=f(i)(i\in A),{\varphi }_i-\sum _j{p}_{ij}{\varphi }_j=g(i)(i\notin A),$$ i.e. $(I_d-P)\varphi =g$ off $A$ with $\varphi =f$ on $A$. The hitting probability $h^A$ is the case $f\equiv 1$ on $A$, $f\equiv 0$ "at infinity", $g\equiv 0$; the mean hitting time $k^A$ is the case $f\equiv 0$, $g\equiv 1$. The operator $I_d-P=-(P-I_d)$ is the discrete Laplacian, and $\varphi$ is its $g$-Green-potential plus the harmonic extension of $f$.

Theorem 3 (gambler's ruin, complete solution). For the walk on $\{0,1,\dots ,N\}$ with absorbing endpoints, $p_{i,i+1}=p$, $p_{i,i-1}=q=1-p$, the probability of reaching $N$ before $0$ from $i$ is $$h_i=\{\begin{array}{ll}\frac{1-(q/p{)}^i}{1-(q/p{)}^N},& p\ne q,\\ \frac{i}{N},& p=q=\frac{1}{2},\end{array}$$ and the expected time to absorption at either wall is $$k_i=\{\begin{array}{ll}\frac{i}{q-p}-\frac{N}{q-p}\cdot \frac{(q/p{)}^i-1}{(q/p{)}^N-1},& p\ne q,\\ i(N-i),& p=q=\frac{1}{2}.\end{array}$$ Both are the minimal non-negative solutions of (H) and (K), here unique because the finite chain hits $\{0,N\}$ with probability one. Letting $N\to \infty$ with $i$ fixed gives the half-line ruin probability ${\mathbb{P}}_i(\text{hit }0)=1$ when $p\le q$ and $(q/p{)}^i$ when $p>q$, the recurrence/transience boundary at $p=1/2$.

Theorem 4 (birth–death recurrence and absorption). For a birth–death chain on ${\mathbb{Z}}_{\ge 0}$ with $p_{i,i+1}=p_i$, $p_{i,i-1}=q_i$, $q_i>0$, set ${\gamma }_i={\prod }_{m=1}^i(q_m/p_m)$, ${\gamma }_0=1$. The chain is recurrent (hits $0$ from every state with probability one) iff ${\sum }_{i\ge 0}{\gamma }_i=\infty$; when the sum is finite the absorption probability at $0$ from $i$ is $h_i=\left({\sum }_{m\ge i}{\gamma }_m\right)/\left({\sum }_{m\ge 0}{\gamma }_m\right)<1$ and escape to $+\infty$ has positive probability. The potential coefficients ${\gamma }_i$ are the discrete analogue of the scale function of a one-dimensional diffusion, and $\sum {\gamma }_i=\infty$ is the discrete analogue of an inaccessible boundary at infinity.

Synthesis. The foundational reason hitting probabilities and mean hitting times submit to the same method is that first-step analysis is the one-step conditioning of the Markov property of 37.05.01, so each unknown equals a boundary value plus a non-negative average of neighboring unknowns, and putting these together, iterating the equation reconstructs the law of the chain up to time $n$ with a non-negative remainder that is discarded only in the limit — which is exactly why the true answer is the minimal non-negative solution rather than any solution. This is exactly the discrete Dirichlet–Poisson problem $(I_d-P)\varphi =g$ off $A$ with $\varphi =f$ on $A$ (Theorem 2): $h^A$ is the harmonic function with boundary value $1$ on $A$, $k^A$ is the Green potential of the constant cost $1$, and the central insight is that absorption, recurrence, and expected cost are three readings of one linear system built from $P-I_d$, the discrete Laplacian dual to the diffusion generator of 02.15.03.

The gambler's ruin (Theorem 3) and birth–death chain (Theorem 4) are the solvable instances where the recurrence $p{h}_{i+1}-h_i+q{h}_{i-1}=0$ telescopes into a geometric series, and the potential coefficients ${\gamma }_i$ generalise the scale function of a diffusion — the recurrence criterion $\sum {\gamma }_i=\infty$ is dual to an inaccessible boundary, so the discrete and continuous theories are two faces of the same potential theory. The minimal-solution principle is the bridge from the combinatorial class structure of 37.05.02 — where $h^A\equiv 1$ on a recurrent class and $h^A<1$ when a competing closed class drains probability — to the analytic equilibrium theory of 37.05.04, where the same operator $P-I_d$ governs stationary distributions through $\pi (P-I_d)=0$.

Full proof set Master

Proposition 1 (hitting probability solves (H) and is minimal). $h^A$ satisfies (H), and any non-negative solution $x$ of (H) dominates it: $x\ge h^A$.

Proof. That $h^A$ solves (H) is Step 1 of the Key theorem (boundary value $1$ on $A$; first-step conditioning under the Markov property off $A$). For minimality, let $x\ge 0$ solve (H). Iterating (H) and splitting each sum at membership in $A$ gives, for $i\notin A$, $$x_i=\sum _{m=1}^n{\mathbb{P}}_i(X_1\notin A,\dots ,X_{m-1}\notin A,X_m\in A)+\sum _{j_1,\dots ,j_n\notin A}{p}_{i{j}_1}\cdots p_{j_{n-1}{j}_n}{x}_{j_n}\ge {\mathbb{P}}_i(H^A\le n),$$ the inequality because the remainder is a sum of non-negative terms. Continuity of measure along $\{H^A\le n\}\uparrow \{H^A<\infty \}$ gives $x_i\ge h_i^A$. $\square$

Proposition 2 (mean hitting time solves (K) and is minimal). $k^A$ satisfies (K), and any non-negative solution $y\in [0,\infty {]}^I$ of (K) dominates it: $y\ge k^A$.

Proof. First-step analysis (Exercise 3) gives $k_i^A=1+{\sum }_{j\notin A}{p}_{ij}{k}_j^A$ for $i\notin A$ and $k_i^A=0$ on $A$, so $k^A$ solves (K). For minimality, let $y\ge 0$ solve (K). For $i\notin A$, $y_i=1+{\sum }_{j\notin A}{p}_{ij}{y}_j\ge 1={\mathbb{P}}_i(H^A\ge 1)$. Substituting (K) into itself $n$ times, each step contributing a fresh ${\mathbb{P}}_i(H^A\ge m)$ and leaving a non-negative remainder, $$y_i\ge \sum _{m=1}^n{\mathbb{P}}_i(H^A\ge m)={\mathbb{E}}_i[H^A\wedge n],$$ using the tail-sum formula $\mathbb{E}[Z\wedge n]={\sum }_{m=1}^n\mathbb{P}(Z\ge m)$ for a non-negative integer variable $Z$. Monotone convergence as $n\to \infty$ gives $y_i\ge {\mathbb{E}}_i[H^A]=k_i^A$. $\square$

Proposition 3 (gambler's ruin probability). For the walk on $\{0,\dots ,N\}$ with $p_{i,i+1}=p$, $p_{i,i-1}=q$, $p\ne q$, the absorption probability at $N$ from $i$ is $h_i=(1-(q/p{)}^i)/(1-(q/p{)}^N)$.

Proof. (H) reads $h_i=p{h}_{i+1}+q{h}_{i-1}$, $h_0=0$, $h_N=1$. Writing $d_i=h_i-h_{i-1}$, the equation $p(h_{i+1}-h_i)=q(h_i-h_{i-1})$ gives $d_{i+1}=(q/p)d_i$, so $d_i=(q/p{)}^{i-1}{d}_1$. Then $h_i={\sum }_{m=1}^i{d}_m=d_1\frac{1-(q/p{)}^i}{1-(q/p)}$, and $h_N=1$ fixes $d_1\frac{1}{1-(q/p)}=1/(1-(q/p{)}^N)$, yielding the stated formula. It is the unique solution meeting both boundary conditions, hence minimal. $\square$

Proposition 4 (gambler's ruin expected duration). For the same walk with $p\ne q$, the expected time to absorption is $k_i=\frac{i}{q-p}-\frac{N}{q-p}\cdot \frac{(q/p{)}^i-1}{(q/p{)}^N-1}$.

Proof. (K) reads $k_i=1+p{k}_{i+1}+q{k}_{i-1}$, $k_0=k_N=0$. The particular solution $k_i^{\mathrm{p}}=i/(q-p)$ satisfies $1+p\frac{i+1}{q-p}-\frac{i}{q-p}+q\frac{i-1}{q-p}=1+\frac{(p+q-1)i+(p-q)}{q-p}=1+\frac{p-q}{q-p}=0$. The homogeneous equation $p{u}_{i+1}-u_i+q{u}_{i-1}=0$ has characteristic roots $1$ and $q/p$, so $k_i=\frac{i}{q-p}+A+B(q/p{)}^i$. Imposing $k_0=0$ ($A+B=0$) and $k_N=0$ gives $B=N/((q-p)((q/p{)}^N-1))$, $A=-B$, producing the stated closed form. $\square$

Proposition 5 (symmetric limits). As $p\to 1/2$ the gambler's ruin formulas tend to $h_i=i/N$ and $k_i=i(N-i)$.

Proof. Put $r=q/p\to 1$. By l'Hôpital in $r$ (or expanding $r=1+ϵ$), $\frac{1-r^i}{1-r^N}\to \frac{i}{N}$, giving $h_i\to i/N$. For $k_i$, write $q-p=-(1-2p)$ and expand $r^i=1+iϵ+\left(\genfrac{}{}{0ex}{}{i}{2}\right){ϵ}^2+O({ϵ}^3)$ with $ϵ=r-1$; the first-order terms cancel against $i/(q-p)$ and the second-order terms give $k_i\to \frac{1}{2}(Ni-i^2)\cdot 2=i(N-i)$ after collecting the $\left(\genfrac{}{}{0ex}{}{i}{2}\right),\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ contributions. Directly, $k_i=i(N-i)$ is checked to solve $k_i=1+\frac{1}{2}{k}_{i+1}+\frac{1}{2}{k}_{i-1}$ since $\frac{1}{2}[(i+1)(N-i-1)+(i-1)(N-i+1)]=i(N-i)-1$. $\square$

Proposition 6 (birth–death absorption formula). With ${\gamma }_i={\prod }_{m=1}^i(q_m/p_m)$, the finite-horizon absorption probability is $h_i^{(N)}=\left({\sum }_{m=i}^{N-1}{\gamma }_m\right)/\left({\sum }_{m=0}^{N-1}{\gamma }_m\right)$, and $h_i={\lim }_N{h}_i^{(N)}$.

Proof. (H) for $h_i^{(N)}={\mathbb{P}}_i(\text{hit }0\text{ before }N)$ is $h_i^{(N)}=p_i{h}_{i+1}^{(N)}+q_i{h}_{i-1}^{(N)}$, $h_0^{(N)}=1$, $h_N^{(N)}=0$. With $d_i=h_{i-1}^{(N)}-h_i^{(N)}\ge 0$, the relation $p_i(h_i^{(N)}-h_{i+1}^{(N)})=q_i(h_{i-1}^{(N)}-h_i^{(N)})$ gives $d_{i+1}=(q_i/p_i)d_i$, so $d_{i+1}={\gamma }_i{d}_1$. Summing $d_{i+1}+\cdots +d_N=h_i^{(N)}-h_N^{(N)}=h_i^{(N)}$ and $d_1+\cdots +d_N=1$ yields $h_i^{(N)}=({\sum }_{m=i}^{N-1}{\gamma }_m)/({\sum }_{m=0}^{N-1}{\gamma }_m)$. The events $\{\text{hit }0\text{ before }N\}$ increase to $\{\text{hit }0\}$ as $N\uparrow \infty$, so continuity of measure gives $h_i={\lim }_N{h}_i^{(N)}$; the limit is $1$ for all $i$ iff ${\sum }_m{\gamma }_m=\infty$. $\square$

Connections Master

• The Markov property, transition matrices, and Chapman–Kolmogorov 37.05.01 supply the engine of first-step analysis: conditioning on $X_1$ and restarting the chain is the one-step form of the Markov property, and the iterated-substitution proof of minimality is the finite-dimensional law ${\lambda }_{i_0}\prod p_{i_r{i}_{r+1}}$ summed over non-$A$ paths. The hitting time $H^A$ is a stopping time for the filtration built there, and the strong Markov property at $H^A$ underlies the regenerative reading of repeated hits.

• The class structure, irreducibility, and periodicity 37.05.02 determine the qualitative outcome of hitting theory: $h^A\equiv 1$ exactly when $A$ is reached from every state, which for a finite chain means $A$ meets every closed communicating class; when two closed classes compete, the absorption probabilities $h_i^A$ partition the unit mass among them, and the open (transient) classes are exactly where the mean hitting time can be finite. Recurrence of a class is the statement $h_i^{\{j\}}\equiv 1$ inside it.

• The stationary distribution and convergence theory of irreducible chains 37.05.04 reuses the same operator $P-I_d$: where hitting theory solves $(P-I_d)h=0$ off $A$ with a boundary condition, equilibrium theory solves the adjoint $\pi (P-I_d)=0$, and the Kac return-time formula ${\mathbb{E}}_i[T_i]=1/{\pi }_i$ ties the mean return time computed by (K) directly to the stationary probability; positive recurrence is finiteness of that mean hitting time.

• The continuous-state diffusion generator 02.15.03 is the analytic limit: the discrete Dirichlet–Poisson problem $(I_d-P)\varphi =g$ off $A$ becomes the boundary-value problem $-\mathcal{L}\varphi =g$ for the second-order generator $\mathcal{L}$, hitting probabilities become harmonic measure, mean hitting times become solutions of $\mathcal{L}u=-1$, and the birth–death potential coefficients ${\gamma }_i$ become the scale function whose finiteness criterion classifies boundary behavior at infinity.

Historical & philosophical context Master

The gambler's ruin problem is among the oldest in probability, posed in the correspondence of Blaise Pascal and Pierre de Fermat in 1656 and given its first printed treatment by Christiaan Huygens, who appended it as one of five problems to his 1657 tract De ratiociniis in ludo aleae ^{[Huygens 1657]}. Huygens computed, for the symmetric and the biased game, the probability that one of two players is ruined before the other, effectively solving system (H) for the finite walk centuries before the matrix formalism existed; Jacob Bernoulli and Abraham de Moivre extended the analysis, de Moivre obtaining the closed geometric form $(q/p{)}^i$ for the biased case in the Doctrine of Chances.

The recasting of these computations as the solution of a linear system indexed by the states — first-step analysis — and the recognition that the genuine hitting probability is the minimal non-negative solution belong to the twentieth-century theory of Markov chains, consolidated in the textbook treatments of Feller and, in the form followed here, of Norris ^{[Norris 1997]}, whose §1.3 isolates the minimality principle as the device that selects the probabilistic solution among the affine family the bare equations admit. The identification of hitting probabilities with harmonic functions and mean hitting times with Green potentials places the subject inside the discrete potential theory developed by Doob, Hunt, and Dynkin, where the Markov chain is the probabilistic counterpart of the Laplacian and the boundary-value problems of classical potential theory acquire a sample-path meaning.

Bibliography Master

@book{Norris1997,
  author    = {Norris, James R.},
  title     = {Markov Chains},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  publisher = {Cambridge University Press},
  year      = {1997}
}

@book{Huygens1657,
  author    = {Huygens, Christiaan},
  title     = {De ratiociniis in ludo aleae},
  publisher = {Elsevier (Leiden)},
  year      = {1657}
}

@book{Durrett2019mc,
  author    = {Durrett, Rick},
  title     = {Probability: Theory and Examples},
  edition   = {5},
  publisher = {Cambridge University Press},
  year      = {2019}
}

@book{LevinPeres2017,
  author    = {Levin, David A. and Peres, Yuval},
  title     = {Markov Chains and Mixing Times},
  edition   = {2},
  publisher = {American Mathematical Society},
  year      = {2017}
}

@book{GrimmettStirzaker2020,
  author    = {Grimmett, Geoffrey R. and Stirzaker, David R.},
  title     = {Probability and Random Processes},
  edition   = {4},
  publisher = {Oxford University Press},
  year      = {2020}
}

@book{Feller1968,
  author    = {Feller, William},
  title     = {An Introduction to Probability Theory and Its Applications, Vol. 1},
  edition   = {3},
  publisher = {Wiley},
  year      = {1968}
}