Codex @codex  0

A standard Brownian motion is a real stochastic process $(B_t{)}_{t\ge 0}$ with $B_0=0$ almost surely, continuous sample paths almost surely, and independent increments such that $B_t-B_s$ has normal distribution $N(0,t-s)$ whenever $0\le s<t$. With its completed, right-continuous natural filtration $({\mathcal{F}}_t)$, its Strong Markov property is the following: for every almost-surely finite stopping time $T$, the processis a standard Brownian motion independent of ${\mathcal{F}}_T$. Here the stopping-time sigma-algebra isIn particular, for every bounded ${\mathcal{F}}_T$-measurable random variable $H$ and bounded Borel functional $G$ on the continuous path space,Thus the independence is from the entire stopped past, not only from $B_T$, and is a statement about the whole future path, not just a single increment.

To prove the Brownian reflection principle without assuming that a level is hit in finite time, fix $t>0$, $m>0$, and set $T_m=\inf \{s\ge 0:B_s\ge m\}$ and $R=T_m\wedge t$. Continuity of the sample paths makes $T_m$ a stopping time and gives $B_{T_m}=m$ whenever $T_m<\infty$. The stopping time $R$ is bounded. Reflect the path after $R$:By the Strong Markov property, the future increments after $R$ are an independent Brownian motion. Negating them preserves their probability distribution, by symmetry of their joint normal distributions. Hence the reflected process $\hat{B}$ has the same path law as $B$.

If $T_m>t$, reflection changes nothing on $[0,t]$ and ${\hat{B}}_t=B_t<m$. If $T_m\le t$, both paths first hit $m$ at the same time and ${\hat{B}}_t=2m-B_t$. Therefore, for $x\le m$, the following events agree path by path:Indeed, the right-hand endpoint is at least $m$, so the reflected path must have hit $m$ before or at $t$; this also forces the original path to have done so. The reflection relation then makes the endpoint inequality equivalent to $B_t\le x$. Equality cases at $T_m=t$ satisfy the same relation. Since ${\hat{B}}_t$ and $B_t$ have the same probability distribution,For $t=0$, both sides are zero, because $B_0=M_0=0$ and $2m-x\ge m>0$.

For $t>0$, set $x=m$ in this identity. Continuity implies $\{B_t>m\}\subseteq \{M_t\ge m\}$, and the normal distribution of $B_t$ has no atom at $m$. Splitting according to whether $B_t\le m$ givesBoth random variables are nonnegative. Their tails agree for all $m>0$, which determines their probability distributions, including the mass at zero. Thus the Brownian running maximum satisfies

For $x>0$ and $t>0$, continuity again gives $\{T_x\le t\}=\{M_t\ge x\}$. Since $B_t/\sqrt{t}$ is a standard normal random variable, the distribution function of the Brownian first-passage time isIt tends to one as $t\to \infty$ and to zero as $t\downarrow 0$, proving almost-sure finiteness and absence of an atom at zero. For the standard normal random variable $B_1$,The value of this ratio on the zero-probability event $\{B_1=0\}$ may be defined arbitrarily. Matching the distribution functions provesFinally, differentiate the distribution function on $t>0$, using ${\Phi }^{\prime }=\varphi$ and $\frac{d}{dt}(x/\sqrt{t})=-x/(2t^{3/2})$. The first-passage-time density isand is zero for $t\le 0$. Its integral is one by the endpoint limits of $F_{T_x}$, so no missing mass at an infinite hitting time is present.

Take two independent rate-one Poisson processes $N^{+}$ and $N^{-}$, and letThe difference of independent Poisson processes starts at zero and has stationary increments and independent increments. Its paths are càdlàg. For an interval of length $h$, the probability of any jump is $1-e^{-2h}\to 0$, proving stochastic continuity. Thus $X$ is a Lévy process. The characteristic function of a Poisson distribution with mean $t$ is $\exp (t(e^{iu}-1))$, so independence givesThe sample paths are integer-valued step functions with jumps $+1$ or $-1$. On every bounded interval there are only finitely many jumps, and independent Poisson arrival times coincide with probability zero. The combined arrival rate is two: holding times are independent exponentials of rate two, and each jump direction has probability $1/2$, independently of the holding times. This is equivalently a Compound Poisson process of rate two with Rademacher distribution jump sizes. Its paths have finite variation on compact time intervals, although there are infinitely many jumps over the whole half-line almost surely.

Work on a filtered probability space $(\Omega ,\mathcal{F},({\mathcal{F}}_n{)}_{n\ge 0},\mathbb{P})$. A submartingale is a real-valued stochastic process satisfying the following three conditions: $Y_n$ is ${\mathcal{F}}_n$-measurable, $\mathbb{E}|Y_n|<\infty$, andThus it is adapted, has integrable random variables at every time, and its conditional expected next value is at least its current value. Repeated conditioning gives $\mathbb{E}[Y_m\mid {\mathcal{F}}_n]\ge Y_n$ for every $m\ge n$. The inequality concerns conditional expectation; individual sample paths need not increase. If no filtration is specified, the definition can be applied to the natural filtration generated by the process.

Apply part (i) for every positive integer $K$ and discard the countable union of its exceptional null sets. A sample path bounded below never reaches $-K$ for some such $K$, and must therefore converge to a finite limit of a sequence.

Apply the same argument to the martingale $(-M_n)$. Outside one more null set, every sample path bounded above also converges finitely. Thus a sample path which does not converge finitely must be unbounded in both directions. Each finite initial segment has finite values, so removing any such segment preserves unboundedness. It follows that the limit superior is $+\infty$ and the limit inferior is $-\infty$. ConsequentlyThis proves the bounded-increment martingale convergence-or-oscillation dichotomy; in particular one-sided divergence to infinity is impossible with positive probability.

The bounded-time optional sampling theorem says that for an integrable discrete-time martingale $(U_n)$ and a bounded stopping time $S$, $\mathbb{E}[U_S]=\mathbb{E}[U_0]$. It requires no assumption about an eventual unbounded stopping time.

Apply this theorem with $S=n\wedge \tau$, or simply take the expectation of the stopped martingale in part (ii). For $N>0$ we obtainSince $P_{n\wedge \tau }\ge 0$,The monotone convergence theorem now yields $\mathbb{E}[\tau ]\le 3abc/N<\infty$. In particular $\tau <\infty$ almost surely, which has been established without assuming that optional stopping is valid at $\tau$.

For each sample path with finite $\tau$, $P_{n\wedge \tau }$ eventually equals $P_{\tau }=0$. Also $0\le P_{n\wedge \tau }\le N^3$. The dominated convergence theorem gives $\mathbb{E}[P_{n\wedge \tau }]\to 0$. Taking the limit of a sequence in the earlier identity therefore provesFor example, initial holdings $(1,1,1)$ give expectation one, as the first transfer must eliminate its giver. This computes the first elimination time, rather than the later time when one player owns all tokens.

Poisson arrivals see time averages says that an exogenous, homogeneous Poisson process samples prearrival states with the same long-run frequencies as observation over time, provided the observed system cannot anticipate future arrivals and the relevant time averages exist. The system may depend on all past arrivals: an ordinary queue does. The required independence is between future increments of the Poisson process and the history available to the system, including its service information. Assume measurable state observations with ordinary piecewise continuous functions as sample paths; write $X(t-)$ for the state immediately before time $t$.

For a state set $B$, let $A(T)$ count offered arrivals by time $T$ and let $t_k$ be their times. With a positive finite constant arrival rate, the PASTA equality isalmost surely when the time limit exists. The indicator functions count visits on the left and time spent on the right. For a stationary process with ergodicity, the right side is the stationary probability of $B$. It matters that the arriving customer has not yet changed the observed state.

In the M/M/1 utilization and delay example, server utilization is $0.8$. Thus PASTA says that 80 percent of offered arrivals find the server busy and 20 percent find the whole queue empty. If an offered arrival seeing population $n$ is admitted with conditional probability $p(n)$, using fresh randomness independent of that state, the accepted fraction is ${\sum }_n{\pi }_{n}p(n)$, where $\pi$ is the stationary distribution. Multiplying this fraction by the offered rate gives the admitted queue throughput when every admitted customer eventually completes service. Accepted arrivals are selected by state and need not themselves form a Poisson process or see the unconditioned time frequencies.

Arbitrary arrivals need not see time averages. Suppose a customer arrives every two minutes and its service time is exactly one minute, with one server and no other customers. The server is busy half the time, but every arrival finds it idle. A uniformly random initial phase can even make the occupancy a stationary process, without repairing the disagreement. Nevertheless Little's law still gives $L=(1/2)\cdot 1=1/2$, with rate measured in customers per minute. This separates Little's law from PASTA.

Ronald W. Wolff's 1982 paper gave a general PASTA theorem under nonanticipation, rather than requiring the observed system to be independent of its driving Poisson process. Its Theorem 1 compares the two long-run fractions; stationarity is a way to establish convergence, not the central sampling condition. ^[ref]. ^[ref].

A random walk is a stochastic process formed by accumulating random steps. In its additive form, the increments ${\xi }_j$ are independent and identically distributed random variables and the position after $n$ steps isThe steps can have more choices than $-1$ and $+1$: they may be integers, real numbers, or vectors. A random walk on a graph instead describes steps between vertices along edges; its available moves can depend on the current vertex.

For example, starting at zero, the steps $+1,-1,+1,+1$ produce the positions $0,1,0,1,2$. This is one sample path; other step sequences can have the same endpoint. A simple random walk on the integer line makes this distinction particularly tangible: repeated Bernoulli trials determine both a whole sample path and an endpoint with a binomial distribution. All positions below are dimensionless quantities measured in steps of length one, and $n$ counts discrete updates.

The model is useful because it separates an average tendency from accumulated fluctuations. A fair simple symmetric random walk has zero expected value at every time, yet its standard deviation grows: cancellation across many possible sample paths does not keep each walker near zero. The two figures below compare sample paths with exact endpoint probabilities. For the basic additive construction and its independent increments, see MIT, Stochastic Processes I, section 2.

For a stochastic process $X_t$ and a fixed sample space outcome $\omega$, its sample path is the function $t\mapsto X_t(\omega )$. One row of observed fair bits, one trajectory of a random walk, or one staircase of Poisson process arrival counts is a sample path. Fixing $t$ instead gives a random variable ranging across possible histories. The same two-variable object $X_t(\omega )$ therefore describes both observations across outcomes and evolution within an outcome.

Statements about continuous, càdlàg or Hölder continuous function sample paths concern these functions simultaneously in time. They differ from assertions made at each fixed time separately. For example, take $U$ with a uniform distribution on $[0,1]$ and set $X_t=1_{\{t=U\}}$. For every fixed $t$, $X_t=0$ almost surely, but every sample path has a single spike. Thus this process is a modification of a stochastic process that is identically zero, while the two are not indistinguishable stochastic processes. Continuity of both sets of sample paths rules out this discrepancy: equality at a countable dense set then implies equality everywhere. This is why path regularity is an additional part of constructing a continuous-time model.

Let customer $k$ enter a queue at $a_k$ and leave at $d_k$, and count it in $N(t)$ for $a_k\le t<d_k$. On a finite observation interval $[0,T]$, the integral of the queue population is exactly the sum of the lengths of the overlaps of customer visits with that interval, as displayed above; $x_{+}=\max (x,0)$ is the positive part. This deterministic identity includes visits already in progress at time zero and visits still unfinished at time $T$. It needs no probability distribution for arrivals or service times. The area argument is also developed in Richard C. Larson and Amedeo R. Odoni, Urban Operations Research, section 4.4.

For a fully computed example, start empty and observe through $T=6$ minutes. Three customers arrive at $a=(0,1,4)$ minutes, begin service at $b=(0,2,4)$ minutes, and depart at $d=(2,3,5)$ minutes. These times describe a single first come first served server with service times $(2,1,1)$ minutes. Their customer sojourn times are $(2,2,1)$ minutes, and their queueing delays are $(0,1,0)$ minutes. The queue population is respectively $1,2,1,0,1,0$ on the consecutive intervals $[0,1),[1,2),[2,3),[3,4),[4,5),[5,6]$, soThe same area is $2+2+1=5$ when counted by customer. Hence the finite-window averages satisfyThe waiting area is one customer-minute, giving $L_q=1/6$ and $W_q=1/3$ minute; $(1/2)(1/3)=1/6$. The server works for four minutes, so its server utilization is $4/6=2/3$ and $L-L_q=5/6-1/6=2/3$. Repeating this six-minute pattern indefinitely makes all these values long-run averages, without a Poisson process of arrivals.

An observation window that cuts visits short requires the overlap terms, rather than full customer sojourn times. Starting empty, let $A(T)$ count admissions before $T$ and write $w_k=d_k-a_k$. ThenFor the example cut at $T=2.5$ minutes, the area is $1+2+0.5=3.5$ customer-minutes, whereas the full durations of the two admitted customers sum to $4$; the remaining half-minute of the second visit is $R(2.5)=0.5$. A precise sufficient sample path condition for the limiting Little's law is $A(T)/T\to {\lambda }_{\mathrm{eff}}\in (0,\infty )$, $A(T{)}^{-1}{\sum }_{a_k<T}{w}_k\to W<\infty$, and $R(T)/T\to 0$. Dividing the identity by $T$ then gives $L={\lambda }_{\mathrm{eff}}W$. Equating admission and departure rates additionally uses $N(T)/T\to 0$, by the balance $N(T)=A(T)-D(T)$ for an initially empty queue, where $D(T)$ counts all departures.

A simple random walk on a locally finite graph chooses each vertex in the current vertex's graph neighbourhood with equal probability, assuming there is at least one available neighbour. On the integer line there are two choices, one unit left or right, so each has probability $1/2$. This is the one-dimensional simple symmetric random walk. Terminology varies: a simple random walk on the integer line is also often allowed unequal step probabilities, with “symmetric” specifying the fair case.

For a simple symmetric random walk starting at $S_0=0$, each increment has the Rademacher distribution, with expected value zero and variance one. Thus linearity of expectation and the variance of a sum of independent random variables giveFor example, after $80$ steps the expected value is zero, the variance is $80$, and the standard deviation is $\sqrt{80}\approx 8.944$. Doubling the typical distance scale takes four times as many steps. This square-root growth explains why a random walk can wander far even when there is no preferred direction.

The colored curves are illustrative sample paths, not averages over all possible walks. The dashed curves show the expected values; the shaded bands show the expected value plus or minus one standard deviation at each time. These bands are a scale of spread, not confidence intervals, and give no guarantee that an entire sample path stays inside them.

Zero expected value does not make this a stationary process: its one-time probability distribution changes with $n$, as the increasing variance already proves. It does have stationary increments and independent increments, because blocks of fresh steps have the same probability distribution at any starting time and disjoint blocks use independent random variables. This separation of position from increment is one reason the random walk is such a useful first example of a stochastic process.

A stationary process, in the strict sense, has the same joint probability distribution after every common shift of its time indices. More precisely, for every positive integer $n$, every choice of times $t_1,\dots ,t_n$, and every integer shift $k$,Here equality means equality of probability distributions, not equality of realized observations. A sample path can fluctuate, stay positive for a while, or show accidental runs while its generating law remains stationary. Strong white noise is a basic example: shifting time preserves every joint law of its independent and identically distributed random variables.

The distinction between strict stationarity and weak stationarity is useful. The former preserves all finite joint laws; the latter preserves only the finite mean and covariance structure. Strict stationarity with finite second moments implies weak stationarity, but strict stationarity itself does not require finite variance. A Gaussian process with weak stationarity is also strictly stationary, because each of its finite-dimensional distributions, a joint normal distribution, is determined by its mean vector and covariance matrix.

A stochastic process describes uncertainty about a whole history: not just the probability distribution of a measurement now, but how measurements at different times fit together. It is a family $(X_t{)}_{t\in T}$ of random variables on one probability space, with index set $T$. Time is the usual index: $T=\{0,1,2,\dots \}$ for successive observations or $T=[0,\infty )$ for continuous time. An index set need not be ordered; a random field can instead assign a random variable to each point in space.

There are two complementary views. Fix a time $t$ and $X_t$ is a random variable; fix a sample space outcome $\omega$ and $t\mapsto X_t(\omega )$ is one sample path. A model specifies the probability distribution of these histories. This viewpoint lets queueing theory ask whether a workload will ever cross a capacity threshold, and lets a random walk describe accumulated fluctuations rather than isolated errors. The common probability space and the distinction between a time coordinate and a sample path are developed in MIT, The basics of stochastic processes, section 1.

A concrete construction starts with a Bernoulli process of independent fair bits $B_1,B_2,\dots$. Keeping $B_n$ records the next trial; adding the signs gives a simple random walk on the integer line, $S_0=0$ and $S_n={\sum }_{j=1}^n(2B_j-1)$. Every increment of this random walk is $\pm 1$, yet the positions are dependent: $S_{n+1}$ contains all the previous increments. Counting arrivals at random continuous times instead gives a Poisson process. These examples separate three questions: what values are possible, how time is indexed, and how the values depend on one another.

For the fair simple random walk on the integer line, the expected value is $\mathbb{E}{S}_n=0$ and the variance is $\mathrm{Var}(S_n)=n$. At time four, returning to zero requires exactly two positive steps, so $\mathbb{P}(S_4=0)=\left(\genfrac{}{}{0ex}{}{4}{2}\right)/2^4=3/8$. A rate-two Poisson process instead has $\mathbb{P}(N_1=0)=e^{-2}\approx 0.1353$. A single realized sample path does not establish either probability: they follow from the specified joint probability distributions.

The most revealing feature is often dependence. Two stochastic processes can have identical marginal distributions at every time while one forgets everything at the next step and the other repeats its first value forever. Their finite-dimensional distributions and covariance functions distinguish them. That extra structure is what makes a stochastic process useful for prediction.

A time series is a sequence of observations indexed by time: hourly temperatures, daily sales, or successive measurements of a fluctuating signal. A probabilistic model treats these observations as one sample path of a stochastic process $(X_t)$. For equally spaced observations, take $t\in \mathbb{Z}$ and measure a lag of a time series in observation intervals. The order matters: shuffling a record preserves its observed values but destroys information about how one value follows another.

Two basic ways to model temporal dependence are an autoregressive model, which feeds past observations into the next value, and a moving-average model, which combines present and past white noise. An AR(1) carries a disturbance forward with diminishing weights; an MA(1) carries it into just two observations. Their autocorrelation functions make this difference visible. A weakly stationary process supplies a common mean and a lag-dependent autocovariance with which to describe that dependence.

These models help forecast future observations and quantify the uncertainty of averages. Successive measurements need not provide as much information as the same number of independent random variables: the long-run variance of a stationary process accounts for their accumulated covariances. Trend and seasonality require attention before fitting a stationary model; differencing and a seasonal difference operator can help, but do not automatically make every process stationary. See Peter Bartlett, Introduction to Time Series Analysis, lecture 1: objectives and models.

The three illustrated sample paths have zero mean and unit variance, so the visual comparison concerns dependence rather than scale. The AR(1) paths start from their stationary normal distribution, independently of future discrete Gaussian white noise; the MA(1) path includes the noise preceding its first observation. These are finite random examples, not exact pictures of an ACF. Compare their theoretical autocorrelation functions in autocorrelation.

Historically, Yule's 1927 study investigated disturbed periodicities in sunspot observations; it should not be read as the discovery of the particular AR(1) examples here. Slutsky studied how summing random inputs could produce wave-like records, a warning against inferring a periodic cause from appearance alone. The editorial note to his 1937 English paper identifies the 1927 Russian original. See G. Udny Yule, On a method of investigating periodicities in disturbed series, with special reference to Wolfer's sunspot numbers (1927) and Eugen Slutsky, The Summation of Random Causes as the Source of Cyclic Processes (1937), including the editorial note on the 1927 original.