Biased random walk hitting probability Created 2026-09-24 Updated 2026-11-05
For a biased random walk on the nonnegative integers with upward probability , the hitting probability of zero from is . Indeed, first-step analysis gives for , with . Its characteristic roots are and , so any solution is . Nonnegativity as forces and hence a value at least . This candidate itself satisfies the recurrence. The theorem on the minimal nonnegative solution for hitting probabilities therefore identifies it with . A walk on all of has the same probability until it first reaches zero.
Communicating class Created 2026-09-24 Updated 2026-10-14
In a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix , write when is accessible from , meaning for some . States communicate, written , when both and . Communication is an equivalence relation, and a communicating class is an entire equivalence class
Thus communicating classes form a partition of the state space; a smaller mutually communicating subset is not itself a class. See Maria Cameron's Markov Chains notes, section 1.2.
The allowance of zero steps matters: , the identity matrix, makes true even for a state with no possible positive-time return. Symmetry is built into communication. For transitivity, concatenate a positive-probability path from to with one from to , and do the same in reverse. These observations prove the equivalence relation directly. One-way accessibility alone is not symmetric and does not define the classes; see Accessible state of a Markov chain.
A closed communicating class satisfies for every and . Once entered, it cannot be left. A singleton class is an absorbing state exactly when it is closed. An open communicating class has an outgoing transition; after a path leaves it, it cannot return, since that would make the visited outside states communicate with it. The internal motion of a closed class can nevertheless continue forever.
Figure 1.
A constructed chain has three communicating classes: an open singleton, a closed alternating pair, and a closed absorbing singleton; dashed outlines group states into classes.
Details.
For this constructed example, in state order , the transition matrix is
There are exactly three communicating classes: , , and . Only the first is open. The second is closed but neither of its states is an absorbing state; they alternate deterministically. Although via , the reverse accessibility fails. A direct matrix power check gives and .
Starting at , let be the first hitting time of either closed class. Staying at for steps has probability , so and . The two eventual destination classes each have probability . Hence the hitting probability of the absorbing state is only , and its unconditional expected hitting time from is infinite: on half the paths it is never hit. In particular, entering a closed class with certainty does not imply entering an absorbing state with certainty.
Classifying the state space separates two questions: which closed region will eventually be entered, and how does the Markov chain move inside that region? In this example the restriction to is an irreducible Markov chain with period two; the restriction to is a one-state irreducible Markov chain with period one. The whole Markov chain is reducible. The absorbing state example illustrates a different possibility: every closed class is a singleton, so eventual class selection is also terminal outcome selection.
First-passage Laplace transform for Brownian motion with drift Created 2026-10-07 Updated 2026-11-05
For , , and ,
where . The diffusion generator is . Its bounded eigenfunction on the positive half-line with boundary value one is , giving the formula through the discounted boundary-hitting representation. The zero-discount limit is the Hitting probability .
Take a birth-death chain on . At each interior state, move up one state with probability and down one state with probability . The endpoints are absorbing states: . This is a small gambler's ruin model in which the state can represent capital, and reaching is success.
Figure 1.
Five states with fair interior transitions and absorbing endpoints; each displayed value is the probability of reaching 4 before 0.
Details.
Let be the hitting time of endpoint , and let be the first endpoint hitting time. The desired hitting probability is . First-step analysis and the Markov property give
The interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values and , so
For example, from state the hitting probability is , and its one-step average is . 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 counts steps, including the transition that first reaches an endpoint. First-step analysis gives
This is a discrete Poisson equation, in the interior. The extra counts the step just taken. The quadratic values
satisfy the equations; from state , 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 upward and downward, keep the same absorbing states. The interior harmonic equation becomes . Using biased gambler's ruin probability with these boundary values gives
The three interior hitting probabilities are approximately , , and . Thus starting at now succeeds about of the time. A direct check is . The curved profile reflects the unequal transition weights: its successive increments shrink by the factor . The formula, with the endpoint denoted there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.
Figure 2.
Hitting 4 before 0 for fair and upward-biased walks, compared with the fair walk's expected number of steps to either endpoint; lines join discrete state values.
Details.
Why does harmonic averaging produce the correct hitting probability? With the natural filtration , the Markov property gives the conditional expectation identity
For a function harmonic everywhere, this makes a martingale whenever it is integrable. For a function harmonic only in the interior, is a stopped martingale. In either five-state example, . Also, from any interior state at most three consecutive upward steps reach , with probability at least . Repeated three-step blocks give , so is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at and then the bounded convergence theorem gives
The 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
Harmonic function for a Markov chain Created 2026-10-14 Updated 2026-10-20
A harmonic function assigns a value to each state of a Markov chain such that one transition leaves its expected value unchanged. This turns a question about many possible future sample paths, such as which endpoint is reached first, into a local averaging rule. For a transition matrix , a real-valued function is harmonic at state when
Here means expected value conditional on starting at ; on a countable state space the sum must be absolutely convergent. If this holds at every state, write . At an absorbing state the equation is automatic, so prescribed boundary conditions supply information that the averaging rule cannot.
For a finite Markov chain, choose a boundary set that can be reached from every state, and assign boundary values . If is its first hitting time, the harmonic extension is
Choosing to be the indicator function of one target within gives a hitting probability. This is a discrete Dirichlet problem: enforce the averaging rule outside and fix the values on . See Hao Wu's MIT lecture 8, harmonic extension, slide 5. The construction extends the mean-value idea of a harmonic function; for a random walk on a graph it is a discrete harmonic function.
Hitting probabilities for a velocity-switching Markov ladder Created 2026-10-14 Updated 2026-11-05
Consider states for integer levels and strictly positive rates . From the chain moves to at rate and to at rate . From , , it moves to at rate or to at rate . At the reflecting boundary there is only the switch to ; no negative level is allowed. All rates are bounded, so the chain is nonexplosive.
Let be the probability of hitting , with . First-step equations are
with the first equation also valid at . Put . If , then and
Substitution verifies both equations and the boundary. Eliminating the variables gives a second-order recurrence with modes . The displayed decaying solution is the minimal nonnegative harmonic solution and hence the Hitting probability.
When , the growing mode is excluded by boundedness; at equality the second mode is linear and is likewise excluded. The only bounded solution with the boundary value is one, proving almost-sure hitting. Since the specified reflected chain is irreducible, these cases classify it as recurrent or transient respectively. Specifying the boundary rule is essential for that recurrence statement; making absorbing would be a different chain.
Hitting probability Created 2026-09-24 Updated 2026-11-05
A Hitting probability describes reaching a target, possibly before a competing target. For a Markov chain and disjoint sets , let and define
Its boundary values are on and on . Outside , first-step analysis gives the discrete harmonic equation . If the finite chain hits almost surely from every state, these equations determine uniquely: stop at the boundary or use the maximum principle for the difference of two solutions.
For a symmetric nearest-neighbour random walk on absorbed at its endpoints, the Probability of hitting before zero is . It has the correct endpoint values and equals the average of its two neighbours; for example, starting at two on gives Probability .
On an infinite state space, boundary values and harmonicity need not imply uniqueness. The Hitting probability is the minimal nonnegative solution, obtained as the increasing limit of finite-horizon hitting probabilities. Taking empty gives the Probability of ever hitting , with paths that never hit contributing zero. A Hitting probability concerns an entire sample path; it differs from the Probability of occupying the target at a specified time.
Hitting probability is the minimal nonnegative harmonic extension Created 2026-10-06 Updated 2026-11-05
The hitting probability of a set is one on that set and transition-harmonic elsewhere by the Markov property. Finite-horizon hitting probabilities begin at the boundary indicator and increase through the same positive transition recursion. Any nonnegative solution dominates every iterate; monotone passage to infinite time shows that it dominates the Hitting probability. This proves minimality without requiring almost-sure hitting.
Maximum occupation is not a hitting probability Created 2026-10-14 Updated 2026-11-05
For with and standard Brownian motion, the one-time occupation Probability is . It is maximized at , giving . The actual hitting probability is . To derive it, solve on with , , obtaining , and let . A path that reached the level and returned contributes to the latter event but not to a given one-time tail.
Nonnegative superharmonic function for a Markov chain Created 2026-10-14 Updated 2026-11-05
For a transition matrix , a finite-valued function on its state space is nonnegative superharmonic when . Thus and its expected value cannot increase after one step. Replacing transitions on a target set by identity rows preserves . Iterating this inequality gives , a useful bound for hitting probabilities without a separate optional-stopping theorem.
Read the arrows in the original diagram as follows: moves to with probability one; from an unprimed , probability leads to and probability leads to ; from the corresponding destinations are and . This is the two-lane Markov chain with a deterministic restart. It is irreducible: every state can reach zero by a finite path of transitions, and zero can reach every primed state by outward transitions and then every unprimed state by a transition. Thus all states have the same recurrence classification.
Let and be the hitting probabilities of zero starting from and , with . First-step conditioning gives
Subtracting yields . Eliminating gives
Its characteristic roots are and . Put , so precisely when .
For , the general solution is . The bound and force , and then gives . For , the general solution is ; boundedness again gives . In both cases, the return probability from zero is , so the Markov chain is recurrent.
For , , and the pair
is a nonnegative bounded solution of the first-step equations. To identify it as the actual hitting probability, use that hitting probability is the minimal nonnegative harmonic extension. This fact follows directly by iteration: a nonnegative solution with boundary value one at zero dominates the probability of hitting zero within steps, for every . The actual bounded solution has form , where nonnegativity as requires . Minimality bounds it above by , while this form bounds it below by . Hence it is exactly the displayed solution. Starting at zero, the first return time has finite-return probability . The Markov chain is therefore transient.
It remains to distinguish positive and null recurrence. Write and for invariant probabilities. Balance at zero and at gives and . For the finite cut consisting of zero and both lanes up to level , invariance equates its outward and inward probability fluxes:
Balance at the unprimed state also gives . Combining these identities yields
Therefore every invariant probability distribution would necessarily have and . Conversely, these weights satisfy all individual balance equations, including , so their summability is the only remaining condition.
When , , and normalization gives
An irreducible Markov chain has an invariant probability distribution exactly when it is positive recurrent; equivalently its mean return time is finite and is its reciprocal. Thus this case is positive recurrent. At , and the nonzero invariant weights cannot be summed to one. Irreducibility would force in any invariant probability distribution. Since recurrence was already proved but no such distribution exists, this case is null recurrent.
The complete classification is therefore transient for , null recurrent at , and positive recurrent for . A drift argument using only the unprimed arrows would miss the primed lane and give the wrong threshold.
Subtract the boundary slope from the Brownian motion: . Then is the first-passage time of to the fixed level . The zero-drift Brownian reflection principle gives
Here is the standard normal distribution function. To change the drift to , use the Girsanov theorem on each finite horizon, with density . On , conditional expectation at the stopped time gives , because the density is a true martingale. Since , the drifted Brownian first-passage density is consequently
There may be additional mass at infinite hitting time; the displayed density only describes finite passage. With , apply the given zero-drift Brownian first-passage Laplace transform:
The zero-discount limit is for and for , so the hitting probability is less than one precisely when the line moves away with positive slope.
For a direct verification of the linear-boundary Brownian first-passage distribution, define
Both terms tend to zero as . Let be the standard normal density. The identity
follows by expanding the two squares. Differentiating the two normal probabilities then gives
Since this is the previously derived hitting density and both distribution functions start at zero,
This proof applies to every real , including the defective distribution when .
For the barrier digital put, use the dividend-free Black-Scholes model with constant interest rate and spot volatility . Under the risk-neutral measure,
Set and
Reaching the barrier is equivalent to reaching . The contingent claim pays one only on the survival event . Risk-neutral pricing therefore gives
This is a path-survival price, not the price of a terminal digital put option. Continuity of the stock paths and the absence of an atom in the finite-horizon maximum imply that alternative touching conventions change no price. As , the value tends to ; as , it tends to zero. Both checks agree with the survival interpretation.
Far from the inner edge of a steady Keplerian accretion disk, the inner angular-momentum flux is negligible compared with . Since , the viscous torque in an accretion disk becomes . The steady balance therefore gives . With the stated surface density of a disk,
Steady conservation of mass gives , and consequently
Both relations use the far-inner-edge approximation, rather than extrapolating the stress-free boundary profile to the inner edge.
For the trace passive scalar, put . Substitute this into the contaminant conservation equation and expand its advective flux:
The braces multiplying vanish by background conservation of mass. Hence the concentration satisfies
The small contaminant fraction ensures it does not alter the ambient disk dynamics. The surface-density model already averages vertically; an axisymmetric background and ring-like injection give . More generally, rapid differential orbital motion winds azimuthal structure and facilitates mixing, but radial-only dependence remains a symmetry or mixing assumption, not a property of every initial injection.
For the axisymmetric advection-diffusion equation, cylindrical geometry gives
Here and are independent of radius. Thus
Let , with any fixed reference length . Since and , this is the tracer diffusion in a power-law accretion disk equation
Assume , , and write , . The change turns this into the heat equation . The radial Dirac delta function must be transformed with its Jacobian:
Convolution with the Gaussian heat kernel gives
This full-line logarithmic solution extends the far-edge power-law model to . An actual finite inner boundary would require its own boundary condition and modified kernel.
The fraction must be computed with the contaminant mass measure, rather than with . Indeed
The total contaminant mass is the conserved quantity . Its normalized logarithmic radius is therefore a normal distribution with mean and variance . Integrating this tail gives, for ,
The complementary error function accounts for the one-time mass fraction outside the specified radius.
For an outward target , put . Since is decreasing, maximize by minimizing . Its derivative has the sign of , so the unique maximum occurs at . At this time . Thus the printed expression is correctly derived as the maximum instantaneous exterior fraction:
It is not, however, the probability of ever reaching the radius. A tracer can pass through the target and later return; its history is not counted by a one-time exterior fraction. The underlying logarithmic diffusion process is
where is standard Brownian motion. To compute its actual hitting probability, first put absorbing levels at and relative to . Conditioning on the first small time step gives the backward equation for the probability of reaching the upper level first, with , . Solving gives
Letting the lower level tend to exhausts all finite-time upward-hitting paths. Therefore the correct eventual probability in this idealized model is
For example, if , the maximum exterior fraction is , whereas the actual hitting probability is . This is an explicit counterexample to the last inference in the question and an instance of maximum occupation is not a hitting probability.
For , the target is the initial radius and the hitting probability is one, while with no attained maximum. For , the inward drift ensures eventual hitting with probability one, and as . The square-root expression involving is therefore only meaningful for the outward-target case, and even there it describes occupancy rather than first passage.
Condition on the first jump, putting . The hitting probabilities obey
The relevant characterization is that a hitting probability is the minimal nonnegative harmonic extension of its target-boundary value. Thus among nonnegative solutions of these equations with , choose the componentwise least one. Other harmonic solutions need not be probabilities. This also identifies the solution without imposing an unjustified boundary condition at infinity.
For , condition on the first step and use the Markov property. The hitting probability obeys
For , the hitting time is zero, so . Since , there. Hence everywhere, as required. This makes a nonnegative superharmonic function for a Markov chain, with an inequality rather than an equality on the boundary.
Starting at any state already in makes the hitting time . Therefore
Together with part (a), this verifies both boundary and superharmonic conditions for the hitting probability.
The modified transition matrix describes the original Markov chain until it hits , and then keeps it at the first state hit. Each state of is therefore an absorbing state, and
For a nonnegative superharmonic function for a Markov chain satisfying the boundary condition, part (c) and positivity of the transition matrix give by induction . Also . Consequently
Let to obtain . Since satisfies the conditions by parts (a),(b), is their pointwise minimal solution. This extends the hitting probability is the minimal nonnegative harmonic extension principle to the superharmonic inequality. Nonnegative sums justify the argument on a countable state space as well as a finite one.
Now suppose the Markov chain is irreducible and recurrent, and let satisfy condition (a). In such a chain every state is hit almost surely from every other state. To see this directly, recurrence gives infinitely many visits to a starting state . Irreducibility supplies a finite path from to any target with positive probability , chosen with no return to before reaching . At each successive return to , the Strong Markov property gives another trial with conditional success probability at least . The chance of avoiding through such trials is at most , which tends to zero.
Apply the absorbing modification at the singleton . Part (c) holds for arbitrary satisfying (a), so
Since and the probability tends to one, . Interchanging yields equality. Thus every nonnegative superharmonic function is constant on an irreducible recurrent Markov chain.
Conversely, if an irreducible Markov chain is not recurrent, choose a state with return probability . Its hitting probability for satisfies condition (a), and . The first-step formula for a return after time zero gives . Therefore cannot be constant: a constant function with value one at would have . This supplies a nonconstant nonnegative superharmonic solution. Hence
The admissible constant solutions are precisely the nonnegative constants. This is recurrence characterized by constant nonnegative superharmonic functions.
Put and . For , , so part (ii) gives . Since , taking differences gives
This is the geometric distribution of parameter on the failures-before-first-success convention, with support . Its expected value is , so the bound in part (b)(ii) is attained. This proves the maximum of a downward-biased random walk formula.
The time-zero convention is necessary here. If , then the first step can be and the walk may never return to zero. Using the same hitting probability calculation after that step gives . Also , while its tails at positive remain . Its masses are therefore
Thus the printed geometric conclusion is correct for the standard maximum that includes , and false for a supremum restricted to the positive times.
Let be the hitting probability of the right endpoint before the left endpoint, starting at . A surviving vase corresponds to that right-endpoint event. Conditioning on the first step of the simple symmetric random walk gives
The Markov property makes the remaining probability depend only on the position after that step. These absorbing endpoint values distinguish the event of interest from its complement.
The initial position is . Applying the gambler's ruin hitting probability and mean hitting time gives
For comparison, the original central starting position would give probability and mean time minutes.