Absorption time 2026-10-25
For a discrete-time Markov chain and a set of absorbing states, its absorption time is the hitting time . It is zero when the initial state already lies in , and infinite on a sample path that never enters . Finiteness almost surely need not imply a finite expected value. For a finite-state model, a uniform positive probability of absorption within a fixed number of steps gives a geometric series bound on the survival probabilities and proves that the mean is finite. The mean absorption time of a lazy symmetric random walk is an explicit example.
Autocorrelation Created 2026-09-28 Updated 2026-10-14
The autocorrelation function of a real weakly stationary process with positive variance is its normalized autocovariance:It is dimensionless, with , , and by the Cauchy-Schwarz inequality. It is unchanged by replacing with for fixed . This makes autocorrelation useful when comparing records measured on different scales. The ACF is a property of the model; the sample autocorrelation function estimates it and will generally not reproduce theoretical zeros exactly.
An AR(1) with coefficient has autocorrelations at lags one through three. With these become : the same diminishing magnitude, alternating in sign. An MA(1) with instead has lag-one autocorrelation and zero at every higher lag. Equal numerical coefficients in an autoregressive model and a moving-average model do not mean equal dependence. See Bartlett, lecture 3: theoretical ACFs and prediction.
Theoretical autocorrelation: AR(1) with coefficients 0.7 and -0.7, compared with MA(1) with coefficient 0.7
. Details. The bars show exact model autocorrelations, not estimates from the illustrated sample paths in time series. The AR(1) retains a diminishing trace of a disturbance at arbitrarily large lags; the MA(1) stops sharing driving noise after lag one. A zero autocorrelation means uncorrelated random variables, and does not generally imply independent random variables. For a Gaussian process it does imply independence of the two coordinates.
There is a direct prediction interpretation. Among affine predictions based on just , the best linear predictor of is , with mean squared prediction error . Thus negative autocorrelation is also useful predictive information. A prediction using the whole observed past can do better; best linear prediction from a finite past describes that problem. Interpreting the affine prediction as a conditional expectation requires additional assumptions, such as a joint normal distribution.
Biased random walk Created 2026-09-24 Updated 2026-10-14
A biased random walk on the integer line takes unit steps right and left with unequal probabilities and , using independent and identically distributed random variables as increments. For , the expected value is : positive for and negative for . Changing to reverses the preferred direction. The exact endpoint probability mass function is given under simple random walk on the integer line.
For example, with each step has expected value and variance . After steps,The displacement of the expected value from zero is about standard deviations, yet individual sample paths still move left as well as right, as the figure under simple random walk illustrates. Bias lets this elementary stochastic process model an average directional tendency while retaining fluctuations. Boundary and return questions have their own treatments under gambler's ruin and the specialized children below.
Binary Markov source 2026-10-14
Take the alphabet , fair initial bit , and transition matrixThe stationary distribution is . Every emitted symbol is a fair bit, while the next symbol flips the previous one with probability . For , repeating the previous symbol is the better one-step prediction; for , predicting its opposite is better. The resulting minimum next-symbol error probability is , compared with when no history is used.
Given either state, the next-symbol information entropy is . ThusAt , the best next-symbol prediction succeeds with probability , and the entropy rate is about bits per symbol. The adjacent symbols share mutual information bits. This is useful structure even though the single-symbol counts reveal no bias.
At , the random initial bit is repeated forever; at , it alternates forever. Both have and zero entropy rate. At , the symbols are independent and identically distributed fair bits, giving entropy rate one. Zero rate therefore need not mean that the initial choice was deterministic.
Brownian motion Created 2026-09-24 Updated 2026-10-14
Standard one-dimensional Brownian motion is a real-valued stochastic process on a probability space with three defining properties: almost surely; its sample paths are continuous almost surely; and its Brownian increments over any finite collection of disjoint time intervals are independent, withHere denotes the normal distribution with expectation and variance . The alternative symbol denotes the same kind of stochastic process. Continuity is a simultaneous statement about an entire sample path, rather than a separate assertion at each fixed time. Relative to its natural Brownian filtration, a future Brownian increment is independent of all observations up to its starting time.
The normalization gives , so the standard deviation of a Brownian increment over duration is . For , , and , the corresponding standard deviations are , , and . Time becoming one hundred times shorter makes typical displacement ten times smaller. Brownian scaling expresses this rule for the whole stochastic process, while the Brownian covariance kernel describes how positions at different times remain related despite independent increments.
For a concrete probability calculation, let be the cumulative distribution function of . At time four, has that normal distribution, henceThese numbers can be reproduced using the error function: . In particular, zero expectation does not mean small displacement: , but the same fixed interval contains only about of the probability at time four.
The probability density function of , for , isIts partial derivatives satisfyThus the normal distribution spreads according to the heat equation. Starting at a fixed position replaces by . This is a useful bridge between individual random trajectories and the deterministic evolution of their probability density function: the same Brownian motion provides both descriptions.
Physical diffusion uses its own scale. For constant diffusion coefficient , the position model has variance , and its probability density function satisfies . For example, gives displacement variance after four seconds, hence standard deviation . Standard Brownian motion corresponds numerically to in chosen units; omitting the factor two changes the physical convention. Einstein's 1905 paper relates diffusion to the mean squared displacement in precisely this convention. [ref]
https://djalil.chafai.net/docs/M2/history-brownian-motion/Einstein%20-%201905.pdf. Einstein, 1905 paper, English translation, section 4
Continuity does not supply a smooth physical velocity. The difference quotient has normal distribution , so its standard deviation grows as : for the three durations above it is , , and . This calculation motivates the nowhere differentiability of Brownian motion, but it alone is not a proof of the simultaneous assertion at every time. The theorem says that, with probability one, no finite derivative exists anywhere along the sample path. A drawn polygon only displays a finite grid; its straight segments cannot establish this theorem. See Theorem 7.1.6 in Probability: Theory and Examples (fifth edition) by Rick Durrett.
For physical particles, Brownian motion is a model of position on suitable observation scales. It does not claim that microscopic velocity is a derivative of this idealized path. Einstein explicitly restricts his assumption of independent increments to intervals that are not too short. [ref]
https://djalil.chafai.net/docs/M2/history-brownian-motion/Einstein%20-%201905.pdf. Einstein, 1905 paper, English translation, section 4
Another way to measure the roughness is quadratic variation. On , divide time into equal intervals and formWriting each Brownian increment as with independent standard normal random variables gives . Since and , the variance of is , andThis proves mean-square convergence to along uniform partitions. For and , the expectation is , the variance is , and the root mean square of the error is . For a general deterministic partition of an interval with lengths , the same calculation gives error variance , so shrinking the largest interval also suffices.
The resulting quadratic variation is , whereas the smooth function gives . This difference explains why the ordinary rules of calculus need the second-order correction in the Itô formula. In the figure, coarser sums reuse the same finest-grid Brownian increments; their individual values can oscillate with refinement even though the error tends to zero in mean-square convergence. Refining a fixed interpolating polygon forever would instead give zero quadratic variation, so the finite-grid illustration must not be confused with the limiting Brownian motion.
Historically, Brown's 1828 report describes microscopic observations made in 1827, starting with particles released from pollen and extending to inorganic materials; this challenged an explanation based solely on living matter. His observations and the later mathematical model are distinct contributions. [ref]
https://en.wikisource.org/wiki/The_miscellaneous_botanical_works_of_Robert_Brown/Volume_1/A_brief_account_of_microscopical_observations_made_on_the_particles_contained_in_the_pollen_of_plants. Brown, 1828 report, reprinted in his collected works
Einstein's 1905 paper derived a quantitative connection between kinetic theory, diffusion, and displacement. [ref]https://djalil.chafai.net/docs/M2/history-brownian-motion/Einstein%20-%201905.pdf. Einstein, 1905 paper, English translation
Wiener's 1923 Differential-Space developed integration on spaces of paths, a foundation for Wiener measure; it also acknowledges earlier work and his own previous papers. These dates mark documented contributions rather than an assertion that each subject had a single discoverer. [ref]https://djalil.chafai.net/docs/M2/history-brownian-motion/Wiener%20-%201923.pdf. Wiener, Differential-Space, 1923, sections 1 and 6
Brownian scaling Created 2026-09-24 Updated 2026-10-14
For every , the stochastic process is standard Brownian motion. Its Brownian increments remain independent and have variance ; continuity and the zero starting value are preserved. Equivalently,Equality here is of whole-process distributions, including every finite-dimensional distribution. It is not an equality of the two expressions along a particular realization. With , speeding time up fourfold requires dividing displacement by two to recover the standard law. The figure applies exactly these coordinate changes to four finite samples; the shared colors indicate reused samples, while the dashed lines show pointwise standard deviations, not bounds on entire sample paths.
Seeded Gaussian samples before and after Brownian scaling with c equal to four
. Details. The same square-root normalization explains how a simple random walk approaches Brownian motion. Let , where the independent steps take values and with equal probability. Then has variance . Its linear interpolation isand . Donsker's theorem says in with the uniform norm: this is convergence in distribution of random paths. The interpolation bound vanishes, but the theorem does not assert pointwise convergence of an arbitrarily fixed walk to an independently chosen Brownian motion. The usefulness is that many-step discrete motion has a universal continuous limit.[ref]
Càdlàg process Created 2026-09-24 Updated 2026-11-05
A Càdlàg process has sample paths that are càdlàg functions: they are right-continuous and have a finite left limit at every positive time.
Chi-squared stochastic ordering Created 2026-09-24 Updated 2026-11-05
Chi-squared distributions are stochastically increasing in their statistical degrees of freedom. For any real , take independent and . Gamma additivity givesFor integer , this is the familiar construction by adding extra independent squared standard normal variables. For noninteger degrees of freedom, multiplying the gamma moment-generating functions proves the same statement.
Under this coupling the larger-degree variable is larger on every sample path. Hence for every , and in fact the inequality is strict for : average and use and the strictly positive chi-squared density. Therefore every quantile at a fixed probability in strictly increases with the degrees of freedom. Comparing chi-squared critical values must account for this change; the distribution is not fixed while only its label changes.
Counting process Created 2026-09-24 Updated 2026-11-05
A counting process records accumulated events. It is a nonnegative integer-valued Stochastic process , usually adapted and càdlàg, with and nondecreasing sample paths. Nonexplosion means at every finite time. In a simple counting process, every jump is one; broader counting conventions also allow several events at the same instant.
A rate- Poisson process has independent stationary increments, mean and variance . A one-event process , with , instead records whether its single event has occurred. It is a counting process without the Poisson process's unrestricted repeated arrivals.
The path is the observed count. A counting-process intensity describes its conditional event rate, and a compensator accumulates that predictable rate or, more generally, a predictable event measure. These objects are not the same: the count has integer jumps, whereas a continuous compensator can increase between observed events. In Survival analysis, the one-event convention naturally combines a Hazard function with an at-risk process.
David Pollard 2026-11-05
David Pollard is a statistician whose research and exposition concern weak convergence, empirical processes and stochastic processes. Yale's institutional profile identifies these specialties, together with statistical asymptotics and econometrics.[ref]
A recurring scientific issue in his writing is how bounds for one random quantity become simultaneous bounds for a whole indexed family. His Measurability Woes by David Pollard explains why pointwise almost-sure agreement does not automatically provide a single exceptional set valid at every index. That distinction matters when a supremum or an entire sample path enters an argument. His author page lists Convergence of Stochastic Processes (1984) and Empirical Processes: Theory and Applications (1990), followed by broader notes on probability methods.[ref]
https://www.stat.yale.edu/~pollard/. Books and manuscripts
[ref] Finite-dimensional distribution Created 2026-09-24 Updated 2026-10-14
For times , the corresponding finite-dimensional distribution of a stochastic process is the joint probability distribution of the random vector . The collection of these distributions records every finite set of coordinates of the process.
Knowing only the one-time marginal distributions is insufficient. Let be independent standard normal random variables, and let for every , where is one standard normal random variable. Every and has the same standard normal distribution. Nevertheless, for , the difference has a normal distribution with variance two, whereas . The joint probability distribution of is concentrated on the diagonal; that of is spread across the plane. A model for tomorrow's value therefore needs the relation between observations as well as their separate distributions.
For a real-valued stochastic process, its finite-dimensional distributions determine its probability law on the product sigma-algebra. With an uncountable index set, a path property such as continuity need not be measurable in that sigma-algebra; specifying a suitable space of sample paths and a regular modification of a stochastic process is a separate step. This distinction is explained in MIT, The basics of stochastic processes, section 1.1.
Suppose an integer-valued random walk starts at , has upward increments at most one, and satisfies almost surely. Write for its first-passage time to . On the event of almost sure convergence, the walk tends to and cannot jump over any positive integer, so every is finite. The bound gives . Along this subsequence, on each such sample path, proving the displayed reciprocal limit. No independence between the hitting times and the path is required. The strong law of large numbers supplies the hypothesis for integrable independent and identically distributed random variables as steps with positive mean.
Consider the chosen finite minimization problemOnly adjacent integers are neighbors. At each interior state propose left or right with probability each; at an endpoint propose its sole neighbor with probability and itself with probability . This proposal distribution is symmetric, including at the endpoints. The local minimum at is relative to these allowed moves; is the unique global minimum.
At , improving-only local search rejects both neighbors because and exceed . For simulated annealing, choose , using the natural logarithm. Conditional on proposing from , the acceptance probability isThe one-step transition probability is instead . Both subsequent rightward proposals are downhill, so the conditional probability of the precise next three states being , given and fixed , isThis is one possible escape route, not the probability of eventually reaching . Rejections, excursions toward , and repeated attempts give many other sample paths. The calculation establishes possibility, without claiming a general performance advantage from a selected sample path.
For comparison, halving makes the uphill acceptance probability ; doubling it makes that probability . Cooling makes it harder to leave this local minimum, even though the stationary distribution increasingly favors the global minimum. That tension is the central scheduling problem.
Five-state harmonic absorption example 2026-10-14
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.
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 giveThe interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values and , soFor 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 givesThis is a discrete Poisson equation, in the interior. The extra counts the step just taken. The quadratic valuessatisfy 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 givesThe 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.
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 identityFor 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 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
Gaussian-process characterization of Brownian motion Created 2026-09-24 Updated 2026-10-14
A centered Gaussian process with almost surely continuous sample paths and covariance is standard Brownian motion. Here Gaussian process means that every finite-dimensional distribution is a multivariate normal distribution; having separate normal distributions at each time would not suffice. This characterization is stated in Pitman, Basic Properties of Brownian Motion, Definition 15.2.
To compute the Brownian covariance kernel directly, suppose . Since and the added Brownian increment is centered and independent of ,Symmetry gives for arbitrary nonnegative times. For instance, and their correlation is . Positions are therefore related even though disjoint Brownian increments are independent: both positions contain the displacement accumulated during the first unit of time. Conversely, taking differences of gives zero covariance for disjoint increments; their joint multivariate normal distribution turns this into independence.
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 whenHere 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 isChoosing 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 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 defineIts 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.
Jump activity of a Lévy process 2026-11-05
The jump activity of a Lévy process describes whether it has finitely or infinitely many jumps in a bounded time interval. Its Lévy measure decides this: finite activity corresponds to , in which case the jump component is a Compound Poisson process. Infinite mass gives infinitely many small jumps in every positive-length time interval, almost surely. For every , however, jumps larger than still have a finite rate.
Activity and total variation are different. With zero Brownian component, sample paths have finite variation on compact time intervals exactly whenFor example, on , with and , has infinite total mass but a finite integral of near zero. It therefore permits infinite jump activity with finite variation. Conversely, Brownian motion has no jumps but infinite total variation on every positive-length time interval, almost surely.[ref]
Topics in Probability: Lévy Processes by Davar Khoshnevisan. Lecture 7, the compound Poisson part and Theorem 5 on path variation
Kolmogorov extension theorem Created 2026-10-06 Updated 2026-10-14
Consistent probability distributions on finite collections of coordinates in standard Borel spaces determine a unique probability measure on the product sigma-algebra. Consistency means that discarding coordinates by marginalization agrees with the law already assigned to the smaller collection, and relabeling coordinates relabels the law. The theorem turns finite recipes into a complete stochastic process. In particular, products of one fixed probability distribution construct an independent and identically distributed sequence; putting one common random variable in every coordinate constructs the perfectly shared process above. The theorem supplies a law on the coordinate space, but does not by itself ensure continuous sample paths.
Mean reversion Created 2026-10-14 Updated 2026-11-05
mean reversion is a tendency for a stochastic process to move back towards a reference level. For a mean-reverting Ornstein-Uhlenbeck process with , the conditional expected value of a future deviation is the present deviation multiplied by after time . Individual sample paths can move away from that level: mean reversion describes a conditional tendency, not monotone motion or a guaranteed return by a deadline. It also does not by itself imply a stationary process; the initial probability distribution matters.







