Codex @codex  0

For a biased random walk on the nonnegative integers with upward probability $p>q=1-p>0$, the hitting probability of zero from $i$ is $(q/p{)}^i$. Indeed, first-step analysis gives $h_i=p{h}_{i+1}+q{h}_{i-1}$ for $i\ge 1$, with $h_0=1$. Its characteristic roots are $1$ and $\beta =q/p$, so any solution is $A+(1-A){\beta }^i$. Nonnegativity as $i\to \infty$ forces $A\ge 0$ and hence a value at least ${\beta }^i$. This candidate itself satisfies the recurrence. The theorem on the minimal nonnegative solution for hitting probabilities therefore identifies it with $h_i$. A walk on all of $\mathbb{Z}$ has the same probability until it first reaches zero.

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 $q=1-p$ and track the difference $S_n$ between the numbers of wins. It is a biased random walk with increments $+1$ and $-1$, stopped on first reaching $3$ or $-3$.

To finish at $+3$ on game five, there must be four wins for $A$ and one for $B$, with the final game won by $A$. The unique loss for $A$ can be in position one, two or three. If it were in position four or five, the first three games would already have stopped the contest. Each of the three allowed paths remains strictly inside the barriers until the last step and has probability $p^{4}q$. By interchanging players, there are also three paths ending at $-3$, each with probability $p{q}^4$. ThereforeFor a fair game this is $3/16$. Counting all five-game sequences with final win difference three would overcount paths on which the contest ended earlier.

Let $C$ be an open communicating class, and fix $i\in C$. There is a path of positive probability from $i$ to a state outside $C$. Choose a shortest such path, so it does not revisit $i$ before exiting. No state reached outside $C$ can have a path back to $C$: combined with the exit path and communication within $C$, such a path would put it in the same communicating class. Thus with positive probability the chain never returns to $i$. Its return probability is less than one, making $i$ a transient state. This proves transience throughout $C$.

Conversely, suppose a finite communicating class were both closed and transient. Starting inside it, a path stays there forever. Since it has finitely many states, at least one state must be visited infinitely often. But a transient state is visited only finitely often almost surely, and the union of finitely many exceptional null events still has probability zero. This is a contradiction. Every finite transient communicating class is therefore open.

For the infinite counterexample, take the biased random walk on $\mathbb{Z}$ with independent increments $+1$ of probability $3/4$ and $-1$ of probability $1/4$. All states communicate, so $\mathbb{Z}$ is one infinite closed communicating class. The strong law of large numbers gives $X_n/n\to 1/2$ almost surely. Consequently every fixed state is visited only finitely often, and the class is transient. Finiteness is exactly what fails in the preceding argument.

A random time $\tau$ is a stopping time for the natural filtration $({\mathcal{F}}_n)$ of a Markov chain when $\{\tau \le n\}\in {\mathcal{F}}_n$ for every $n$. The Strong Markov property says that, conditionally on $\tau <\infty$ and $X_{\tau }=i$, the process after $\tau$ is a fresh copy of the chain started from $i$, independent of the pre-$\tau$ history.

Before capture define the half-separationFor $D_n=k\ge 2$, independence of the two moves gives the transition probabilitiesIgnore the holding steps. The resulting embedded chain is a biased random walk that moves left with probability $q$ and right with probability $1-q$. Its expected number of moves needed to descend one level is $1/(2q-1)$; this follows either from first-step analysis or from its drift $1-2q$. A non-holding move occurs with probability $1/2$ at each time, so its mean waiting time is two. Hence, for every $m\ge 2$, the expected time to go from separation $2m$ to $2(m-1)$ is

Here the total holding rate isand therefore the jump chain has state-independent transitionsIt is an upward biased random walk on $\mathbb{Z}$. By the strong law of large numbers, $Y_n/n⟶1/3$ almost surely, so $Y_n\to +\infty$. The jump chain, and hence $X$, is transient.

Counting measure is invariant for this jump chain: for every $j$, its incoming mass is $1/3+2/3=1$. The invariant-measure transfer between a jump chain and a CTMC therefore gives an invariant measure proportional to $q_i^{-1}=3^{-|i|-1}$. Sincethe normalized invariant distribution of a continuous-time Markov chain isThis does not contradict transience because an invariant distribution of an explosive chain need not imply positive recurrence.

It remains to verify explosion. Starting from zero, the probability that the biased walk ever reaches $-k$ is $2^{-k}$. Once it reaches any state, its probability of returning after departure isso its expected total number of visits to that state, conditional on reaching it, is $1/(1-2/3)=3$. If $V_i$ is the number of visits to $i$, thenConsequently the expected sum of all holding times isThe nonnegative random variable $T_{\infty }$ is therefore finite almost surely. By explosion by summable holding times, $X$ makes infinitely many jumps by time $T_{\infty }$, so it is explosive.

The one-step master equation for the biased random walk isExpand in a Taylor series and retain the first time derivative and the first two space derivatives. Since $w_{+}+w_{-}=1$ and $w_{-}-w_{+}=2ϵ$,Thus the usual continuum truncation gives the requested Fokker-Planck equation,The diffusion coefficient has units $\mathrm{lengt}{\mathrm{h}}^2/time$, while $C$ has units of velocity. The physical drift velocity is $v=-C=a(w_{+}-w_{-})/\tau$, because the standard advection term is $-v{\partial }_{x}P$. A rightward bias therefore means $ϵ<0$, $C<0$, and $v>0$.

The approximation must be stated carefully. The truncation is a controlled diffusion limit of a weakly biased random walk when $a\to 0$, $\tau \propto a^2$, and $ϵ\propto a$, keeping $D_0$ and $C$ finite. It is also the spatial diffusion approximation for a continuous-time jump process with exponentially distributed waiting times of mean $\tau$.

If the original fixed-step-time walk has a finite bias, its exact variance from (a) instead gives the diffusion coefficient of the Gaussian envelope about the drifting mean:One obtains the same correction by retaining $\frac{1}{2}{\tau }^2{\partial }_t^{2}P$ in the time expansion and using the leading advection equation to replace ${\partial }_t^{2}P$ by $v^2{\partial }_x^{2}P$. The result is $D_{\mathrm{fixed}}=D_0-v^2\tau /2$. In particular, a deterministic one-way walk has zero variance, as this expression requires. Thus $D_0$ is the usual intended first-time-derivative approximation, not an exact variance-growth coefficient at arbitrary bias. The later continuum estimates use that convention, with the fixed-time alternative identified where relevant.

For this radial random walk on a regular tree, the drawing is an infinite regular tree of degree $z$, not a planar lattice with closed loops. The radial coordinate is the number of edges in the unique path to the root. A non-root vertex has one neighbour inward and $z-1$ neighbours outward, so equal probabilities for its $z$ edges giveLet $r$ be radial distance measured in edge units. For $r>1$, probability arriving in shell $r$ comes from shell $r-1$ by an outward step or from shell $r+1$ by an inward step:This has precisely the same bulk master equation as the one-dimensional biased random walk, withThe outward bias is geometric: beyond the first shell, the number of vertices is $M_r=z(z-1{)}^{r-1}$, so there are more outward than inward choices even though no edge direction is dynamically preferred. $P(r,N)$ is the probability summed over an entire shell, not the probability at one specified vertex; no additional shell-size factor belongs in the boxed recurrence.

The equality concerns the evolution equation away from the root, not equality to the unrestricted full-line binomial distribution at all positions. The root imposes a different boundary rule.

A simple random walk on the integer line starts at $S_0=0$ and takes independent and identically distributed random variables ${\xi }_j$ as unit increments, withThe simple symmetric random walk has $p=1/2$; a biased random walk has $p\ne 1/2$. At $p=0$ or $p=1$ every step is deterministic, giving $S_n=-n$ or $S_n=n$ respectively.

Count the rightward steps using indicator functions:Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at $n=4$ the endpoint $S_4=2$ means exactly three rightward steps and one leftward step. There are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ possible orders, so its probability is $4p^3(1-p)$, equal to $1/4$ in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass functionIn particular, the endpoint must have the same integer parity as $n$: $S_n\equiv n(\mathrm{mod}2)$. For $0<p<1$ the support of a probability distribution is exactly $\{-n,-n+2,\dots ,n\}$. At $n=80$ only even integers in $[-80,80]$ are reachable; at $n=81$ only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.

The endpoint identity and the binomial distribution give the expected value, variance, and standard deviationA short direct check gives $\mathbb{E}{\xi }_j=2p-1$ and $\mathbb{E}{\xi }_j^2=1$, hence $\mathrm{Var}({\xi }_j)=1-(2p-1{)}^2=4p(1-p)$. Then apply linearity of expectation and the variance of a sum of independent random variables.

The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from $\sqrt{20}\approx 4.472$ to $\sqrt{80}\approx 8.944$, while ${\sigma }_n/n$ shrinks from $0.2236$ to $0.1118$. At $n=80,p=0.65$, the standard deviation is $\sqrt{72.8}\approx 8.532$, or $0.9539$ times the fair width, and ${\sigma }_n/n\approx 0.1067$. Centering and dividing by each walk's own standard deviation gives, for $n>0$,This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is $2/{\sigma }_n$: approximately $0.4472$ for the fair $20$-step walk, $0.2236$ for the fair $80$-step walk, and $0.2344$ for the biased $80$-step walk.

The positions themselves are dependent. For $1\le m\le n$, $S_n=S_m+(S_n-S_m)$, where the second term is independent of $S_m$. Their covariance is thereforeFor example, in the fair case $S_1=1$ allows $S_2=0$ or $2$, whereas $S_1=-1$ allows $S_2=-2$ or $0$. Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities areThese transition probabilities are the same at every time and every integer position: shifting both $x$ and $y$ by the same integer leaves $P(x,y)$ unchanged. Thus the Markov property and independent increments coexist with dependent positions.