Codex @codex  0

A biased random walk on the integer line takes unit steps right and left with unequal probabilities $p$ and $1-p$, using independent and identically distributed random variables as increments. For $S_0=0$, the expected value is $n(2p-1)$: positive for $p>1/2$ and negative for $p<1/2$. Changing $p$ to $1-p$ reverses the preferred direction. The exact endpoint probability mass function is given under simple random walk on the integer line.

For example, with $p=0.65$ each step has expected value $0.30$ and variance $0.91$. After $80$ steps,The displacement of the expected value from zero is about $24/8.532\approx 2.813$ 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.

For a simple symmetric random walk starting at zero, let $T_1$ be its first hitting time of $1$. The infinite mean first passage of a simple symmetric random walk shows that $T_1<\infty$ almost surely but $\mathbb{E}[T_1]=\infty$. Since $S_{T_1}=1$, assuming a finite expected value for $T_1$ would let Wald's equation assert $1=0\mathbb{E}[T_1]=0$, a contradiction. The formal expression $0\cdot \infty$ is not an allowed use of the theorem.^[ref]

Compare $T_{\pm 2}=\inf \{n\ge 0:|S_n|=2\}$. From every surviving position in $\{-1,0,1\}$, three consecutive positive increments force absorption within three steps. Each fresh block has probability $1/8$ of this event, so $\mathbb{P}(T_{\pm 2}>3k)\le (7/8{)}^k$ and $\mathbb{E}[T_{\pm 2}]\le 24$. This establishes finiteness before invoking the theorem. If $e_j$ is the average remaining time from position $j$, the law of total expectation givesso $\mathbb{E}[T_{\pm 2}]=4$. Symmetry gives equal exit probabilities at $-2$ and $2$, and $\mathbb{E}[S_{T_{\pm 2}}]=0$, as Wald's equation predicts. This is a small gambler's ruin problem with two absorbing barriers.

Even for $T_1$, each bounded stopping time $T_1\wedge n$ satisfies $\mathbb{E}[S_{T_1\wedge n}]=0$. The stopped process tends to $1$ almost surely, but its expected value does not tend to $1$. Rare long negative excursions retain the balancing contribution. The existing stopped-walk martingale with almost sure but not L1 convergence explains the related failure of uniform integrability; almost sure convergence alone does not permit exchanging a limit and an expected value.

A stochastic process has independent increments when, for every $t_0<t_1<\cdots <t_k$, the random variables $X_{t_1}-X_{t_0},\dots ,X_{t_k}-X_{t_{k-1}}$ are independent. Adjacent intervals are allowed: each increment represents the change after its left endpoint up to its right endpoint. A Poisson process, Brownian motion, and a random walk with independent steps have this property. Their values at different times need not be independent: for a fair simple random walk on the integer line, $\mathrm{Cov}(S_m,S_n)=\min (m,n)$ because both positions contain the same first $\min (m,n)$ increments. Independent increments need not be stationary increments; summing independent steps with time-dependent variances gives a counterexample.

Let $X_1,X_2$ be independent fair signs, each taking $-1$ and $1$ with equal probability. Set $N=1$ if $X_2=1$, and $N=2$ if $X_2=-1$. Deciding whether $N\le 1$ requires the second sign, so $N$ is not a stopping time for the natural filtration. The four equally likely possibilities giveBoth the increments and the count are bounded, but the identity fails because the second contribution is retained only when it is negative. This is selection using an unobserved outcome, rather than a legitimate sequential decision. Boundedness alone cannot replace the stopping time hypothesis.^[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.

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 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.

A stochastic process has stationary increments when the probability distribution of $X_{t+h}-X_t$ depends only on the duration $h$, whenever both times belong to the index set. The clock origin then does not change the increment law. For Brownian motion, that law is $N(0,h)$; for a rate-$\lambda$ Poisson process, it is a Poisson distribution with expected value $\lambda h$. Neither process itself is a stationary process: their variances grow with $t$. Stationary increments and a stationary process describe different properties.

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.

Wald's equation turns a random sum into a product of two expected values: the average contribution per step and the average number of steps. Its surprising feature is that the number of steps may depend on what has already happened. A procedure can stop on its first successful Bernoulli trial, for example, while the identity still accounts for its total cost. The crucial restriction is that the decision to take the next step cannot use that step's unobserved outcome.

Let $X_1,X_2,\dots$ be real independent and identically distributed random variables with $\mathbb{E}|X_1|<\infty$, let $\mu =\mathbb{E}[X_1]$, and put $S_0=0$ and $S_n={\sum }_{i=1}^n{X}_i$. Suppose $N$ is a nonnegative integer-valued stopping time for the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$, with $\mathbb{E}[N]<\infty$. Then $S_N$ is an integrable random variable andThese hypotheses allow statistical dependence between $N$ and the increments; they do not allow access to future increments. The finite-expected value requirement is stronger than stopping almost surely.^[ref]

For the proof idea, count step $i$ only on $\{N\ge i\}$. This event is determined by the first $i-1$ observations, so its indicator function is independent of $X_i$. The Proof of Wald's equation by stopping indicators combines this observation with the tail-sum formula for expectation. The same calculation with $|X_i|$ gives $\mathbb{E}{\sum }_{i=1}^N|X_i|=\mathbb{E}|X_1|\mathbb{E}[N]<\infty$, which justifies interchanging the expected value and the infinite series. This is why the result survives a data-dependent end point without assuming an independent count.

The identity is useful in randomized algorithms and repeated sampling: one can translate an average amount of work into an average number of attempts, or conversely, without first finding the full probability distribution of the total. The examples below separate a permissible stopping rule from a rule that peeks ahead and from a valid rule whose average waiting time is infinite.