Codex @codex  0

Take a birth-death chain on $\{0,1,2,3,4\}$. At each interior state, move up one state with probability $p=1/2$ and down one state with probability $q=1/2$. The endpoints are absorbing states: $P_{00}=P_{44}=1$. This is a small gambler's ruin model in which the state can represent capital, and reaching $4$ is success.

Let $T_a=\inf \{n\ge 0:X_n=a\}$ be the hitting time of endpoint $a$, and let $T=\min (T_0,T_4)$ be the first endpoint hitting time. The desired hitting probability is $h_i={\mathbb{P}}_i(T_4<T_0)$. First-step analysis and the Markov property giveThe interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values $0$ and $1$, soFor example, from state $2$ the hitting probability is $1/2$, and its one-step average is $\frac{1}{2}(1/4)+\frac{1}{2}(3/4)=1/2$. Individual sample paths can wander back and forth, but the same averaging rule already accounts for all of them.

Now ask how long it takes to reach either endpoint. The expected hitting time $t_i={\mathbb{E}}_{i}T$ counts steps, including the transition that first reaches an endpoint. First-step analysis givesThis is a discrete Poisson equation, $(I-P)t=1$ in the interior. The extra $1$ counts the step just taken. The quadratic valuessatisfy the equations; from state $2$, $t_2=1+\frac{1}{2}(3)+\frac{1}{2}(3)=4$ steps. The hitting probability is harmonic, whereas the expected hitting time has a nonzero source term. These are special cases of expected duration of symmetric gambler's ruin; see Hao Wu's MIT lecture 16, gambler's ruin, slide 9.

For a biased random walk with $p=0.6$ upward and $q=0.4$ downward, keep the same absorbing states. The interior harmonic equation becomes $h_i=p{h}_{i+1}+q{h}_{i-1}$. Using biased gambler's ruin probability with these boundary values givesThe three interior hitting probabilities are approximately $0.415385$, $0.692308$, and $0.876923$. Thus starting at $2$ now succeeds about $69.23\%$ of the time. A direct check is $0.6(57/65)+0.4(27/65)=9/13$. The curved profile reflects the unequal transition weights: its successive increments shrink by the factor $q/p=2/3$. The formula, with the endpoint denoted $T$ there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.

Why does harmonic averaging produce the correct hitting probability? With the natural filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, the Markov property gives the conditional expectation identityFor a function harmonic everywhere, this makes $h(X_n)$ a martingale whenever it is integrable. For a function harmonic only in the interior, $M_n=h(X_{n\wedge T})$ is a stopped martingale. In either five-state example, $0\le M_n\le 1$. Also, from any interior state at most three consecutive upward steps reach $4$, with probability at least $p^3>0$. Repeated three-step blocks give ${\mathbb{P}}_i(T>3k)\le (1-p^3{)}^k$, so $T$ is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at $n\wedge T$ and then the bounded convergence theorem givesThe boundedness and finite hitting time justify this passage to the limit. See Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1, and stopped martingale in discrete time for this bounded version of optional stopping.

Uniqueness has a short maximum principle explanation. On a finite state space, the difference of two harmonic extensions with the same boundary conditions is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive transition probability to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior closed communicating class can retain an arbitrary constant.

// Target: markov-process.bigb

Put $Z_n=X_{n\wedge T}$. The stopped martingale in discrete time identityshows that $Z$ is a martingale: the indicator function is ${\mathcal{F}}_n$-measurable and the increment has zero conditional expectation. Integrability follows because $Z_n$ is selected from the finitely many integrable values $X_0,\dots ,X_n$.

For the bounded stopping time $\tau =n\wedge T$, the optional stopping theorem in its conditional form givesHere ${\mathcal{F}}_{\tau }$ is the stopping-time sigma-algebra. Indeed, for $A\in {\mathcal{F}}_{\tau }$, partition $A$ into $A\cap \{\tau =k\}\in {\mathcal{F}}_k$ and apply the martingale identity $\mathbb{E}[X_n\mid {\mathcal{F}}_k]=X_k$ on each piece. This proves the displayed conditional expectation identity directly.

Let $C={\sup }_n\mathbb{E}|X_n|<\infty$ and $A_n=\{|Z_n|>K\}\in {\mathcal{F}}_{n\wedge T}$. Conditional absolute-value domination and the Markov inequality give $\mathbb{P}(A_n)\le C/K$ and, for any $R>0$,First choose $R$ using the uniform integrability of $X$, and then choose $K$. The estimate is uniform in $n$, proving uniform integrability of a stopped uniformly integrable martingale. No finiteness assumption on $T$ is needed.

For $A>0$, the first time $T_A=\inf \{n\ge 0:X_n<-A\}$ is a stopping time. On $\{T_A\ge 1\}$, the bounded increments assumption controls the overshoot:Before that time, $X_n\ge -A$. Allowing the possibility $T_A=0$, the processis a nonnegative martingale. Indeed, the stopped martingale in discrete time is a martingale, and the integrable ${\mathcal{F}}_0$-measurable variable $X_0^{-}$ is a constant-in-time martingale. If $T_A=0$, nonnegativity follows from $X_0+X_0^{-}=X_0^{+}$. Its expectations are constant and finite, so the martingale convergence theorem makes $Y_n$ converge to a finite value almost surely.

On $\{T_A=\infty \}$ this proves finite convergence of $X_n$. Taking the countable union over positive integer $A$, we conclude that $X_n$ converges finitely on the event $\{{\inf }_n{X}_n>-\infty \}$. Apply the same reasoning to the martingale $-X$ to obtain finite convergence on $\{{\sup }_n{X}_n<\infty \}$.

Outside the event of finite convergence, both the infimum and the supremum of the sequence must therefore be infinite in the respective directions. Removing any finite initial segment cannot change this, because each of its values is finite. HenceThis is the bounded-increment martingale convergence-or-oscillation dichotomy. The $X_0^{-}$ term ensures the proof also covers an unbounded integrable initial value.

Assume (i), and let $\tau$ be a stopping time. The increments of the stopped process satisfyBecause $\{\tau >n\}\in {\mathcal{F}}_n$, taking conditional expectation given ${\mathcal{F}}_n$ makes the right-hand side zero. Integrability follows froma finite sum of integrable random variables. Hence $M^{\tau }$ is a martingale, proving (ii).

The increment of the stopped process isBecause $T$ is a stopping time, $\{T>n\}\in {\mathcal{F}}_n$. Taking conditional expectation therefore gives zero. The stopped variables are adapted and integrable, so the stopped martingale in discrete time is a martingale.