Random Walks

The Central Idea

A one-dimensional random walk begins at some position \(X_0\) and changes by a random step at each time.

If \(Y_1,Y_2,\ldots\) are the random step variables, then

The position after \(n\) steps is therefore the starting position plus the cumulative effect of all random increments.

The Simplest Random Walk

The standard one-dimensional walk uses steps

Thus,

At each step, the process moves exactly one unit either right or left.

Symmetric Random Walk

The walk is symmetric when

Then

There is no directional preference in the step distribution.

Biased Random Walk

The walk is biased when

If \(p>\frac12\), rightward steps are more likely than leftward steps. If \(p<\frac12\), leftward steps are more likely.

This imbalance creates a nonzero average drift.

A Random Walk as a Random Sequence

A random walk is itself a random sequence:

Each \(X_n\) is a random variable, and the collection

is a stochastic process indexed by discrete time.

A Random Walk as a Markov Chain

For the standard walk,

where the next increment is independent of the earlier history.

Therefore,

The current position is enough to determine the next-step probability law.

The State Space

For an unrestricted one-dimensional walk,

The process can move through all integer positions.

Other random walks may use finite intervals, lattices, graphs, networks, or higher-dimensional coordinate spaces as their state spaces.

One-Step Transition Probabilities

For the standard walk,

and

All other one-step transitions have probability \(0\).

Nearest-Neighbor Structure

A random walk with steps only \(\pm1\) is a nearest-neighbor process.

From state \(i\), the only possible next states are

and

This creates a sparse transition structure.

A Sample Path

Suppose

and the realized steps are

Then the positions are

This sequence is one sample path of the random walk.

Different Paths Can End at the Same Position

After two steps, the paths

and

both end at position \(0\).

Random-walk probabilities often require counting many distinct step sequences that produce the same final location.

Position After \(n\) Steps

Starting from \(X_0=0\),

If \(R_n\) is the number of rightward steps among the first \(n\) steps, then the number of leftward steps is

Therefore,

Connecting the Walk to a Binomial Variable

If rightward steps occur independently with probability \(p\), then

Since

the distribution of the random-walk position can be obtained from the binomial distribution.

Possible Positions After \(n\) Steps

Starting from \(0\), the walk can be at

The parity of the position must match the parity of \(n\).

For example, after an even number of steps the walk can occupy only even positions.

Probability of a Specific Position

To have

the number of right steps must satisfy

Thus,

When \((n+k)/2\) is an integer between \(0\) and \(n\),

Symmetric Position Probability

When \(p=1/2\),

The probability depends on how many step sequences contain the required number of right and left moves.

Example: Return to the Origin After Four Steps

For a symmetric walk starting at \(0\), returning to \(0\) after four steps requires exactly two right and two left steps.

Therefore,

Expected Step

For

the expected step is

Drift

The quantity

is the average change per step and is often called the drift.

• If \(p>1/2\), then \(\mu>0\).
• If \(p=1/2\), then \(\mu=0\).
• If \(p<1/2\), then \(\mu<0\).

Expected Position

Since

linearity of expectation gives

Therefore,

Expected Position in the Symmetric Case

If

then

Hence,

The mean position stays fixed even though individual paths spread farther from the starting point.

Variance of One Step

Since \(Y^2=1\),

Therefore,

Simplifying,

Variance of the Position

If the increments are independent,

Therefore,

Variance in the Symmetric Case

For \(p=1/2\),

Thus,

The standard deviation is

Typical Scale of Displacement

In a symmetric walk, the expected position remains at the starting point, but the standard deviation grows like

This means the typical distance scale grows much more slowly than the number of steps.

Random motion spreads through cancellation as well as accumulation.

Mean Absolute Distance Is Different from Mean Position

In a symmetric walk starting at \(0\),

but this does not imply

The mean position can vanish because positive and negative locations cancel, even while the typical distance from the origin grows.

Recursive Form

A random walk can be written recursively as

This representation emphasizes local evolution: the next state is the current state plus a new random increment.

Cumulative-Sum Form

The same process can be written explicitly as

The recursive and cumulative-sum forms describe the same stochastic process from two complementary perspectives.

Hitting a Target

A central random-walk question is whether the process reaches a specified state.

For target \(a\), define the hitting time

The event \(T_a<\infty\) means that the walk eventually reaches \(a\).

First Return Time

If the walk starts at \(0\), the first return time is

For a nearest-neighbor walk on the integers, a return to \(0\) can occur only after an even number of steps.

Recurrence of the Symmetric One-Dimensional Walk

A classical result states that a symmetric random walk on

returns to its starting state with probability \(1\).

Such a walk is called recurrent.

Probability \(1\) does not mean that every sample path returns after a fixed number of steps. The return time is random and can be very large.

Biased Walks Can Drift Away

If \(p\ne1/2\), the one-dimensional walk has nonzero drift.

In the unrestricted walk on \(\mathbb{Z}\), this directional tendency makes the process transient: it need not return to its starting state.

The long-run behavior is therefore qualitatively different from the symmetric case.

Bounded Random Walks

A random walk can be restricted to a finite set such as

The behavior at the boundaries must then be specified.

Common choices include absorbing boundaries, reflecting boundaries, and modified transition rules.

Absorbing Boundaries

Suppose \(0\) and \(N\) are absorbing.

Then

and

Once the process reaches either boundary, it remains there.

Reflecting Boundaries

A reflecting boundary prevents the walk from leaving the allowed state space without permanently trapping it.

For example, a walk at \(0\) might be forced to move to \(1\), or might stay at \(0\) when a leftward step is attempted.

The exact transition rule must be specified as part of the model.

Gambler's Ruin Model

A classic bounded random walk uses

where \(X_n\) represents a player's fortune.

At each play, the fortune changes by \(+1\) with probability \(p\) and by \(-1\) with probability \(1-p\).

States \(0\) and \(N\) are absorbing.

Probability of Reaching the Upper Boundary

Let

For interior states,

with boundary conditions

Symmetric Gambler's Ruin Probability

When

the solution is linear:

Starting halfway between the two absorbing boundaries gives a one-half probability of reaching the upper boundary first.

Example: Symmetric Boundary Hitting

Suppose the boundaries are

and the symmetric walk starts at

Then the probability of reaching \(10\) before \(0\) is

Biased Gambler's Ruin Probability

When \(p\ne1/2\), let

Then

Directional bias changes the boundary-hitting probability nonlinearly.

Expected Absorption Time

A different question asks how long the bounded walk takes to reach either absorbing boundary.

For the symmetric gambler's ruin model,

The expected duration is largest near the middle of the interval.

Hitting Probability and Hitting Time Are Different Questions

A hitting probability asks

Will the process reach the target?

A hitting-time question asks

When will it reach the target?

These require different calculations.

Random Walks on Graphs

Random walks are not limited to numerical positions.

On a graph, the current state is a vertex. At each step, the walk moves along an edge to a neighboring vertex according to specified probabilities.

A common rule chooses uniformly among the available neighbors.

Example: Random Walk on a Triangle

Suppose three vertices \(A,B,C\) form a triangle, and from each vertex the walk chooses either neighboring vertex with probability \(1/2\).

Using state order \(A,B,C\), the transition matrix is

This is a random walk on a finite network.

Random Walks and Degree

For a simple random walk on an undirected graph, a vertex with degree \(d_i\) sends probability

along each incident edge.

Vertices with more neighbors typically receive greater stationary weight in the long run.

Stationary Distribution on an Undirected Graph

For a connected finite undirected graph, the simple random walk has stationary probabilities proportional to vertex degree:

Since

this can also be written

Random Walks in Two Dimensions

A two-dimensional lattice walk can move on

A simple version chooses among

with equal probability \(1/4\).

The state is now a coordinate pair rather than a single integer.

Random Walks in Higher Dimensions

The same idea extends to

In higher dimensions, recurrence behavior changes.

The simple symmetric walk is recurrent in dimensions \(1\) and \(2\), but transient in dimensions \(3\) and higher.

Why Dimension Matters

Higher-dimensional spaces provide many more directions in which the walk can spread.

In one and two dimensions, repeated random motion is sufficiently constrained that the simple symmetric walk returns to its starting point with probability \(1\).

In three or more dimensions, there is a positive probability of never returning.

Random Walks with Larger Steps

The increments do not need to be restricted to \(\pm1\).

A more general walk can have

where the \(Y_k\) follow another discrete or continuous distribution.

The central random-walk structure is cumulative random change.

Random Walk with a Stay-Put Step

A walk might use

Then the process may move left, remain in place, or move right.

Such a model can be useful when systems may remain unchanged during an observation period.

Random Walks with State-Dependent Probabilities

The transition probabilities need not be the same at every location.

For example,

The process can still be Markov, but the transition rule now depends on the current state.

Random Walks with Time-Dependent Probabilities

The step probabilities can also vary with time:

This produces a time-inhomogeneous random walk.

The cumulative-sum structure remains, but identical-step assumptions no longer apply.

Random Walks and Martingales

For a symmetric random walk,

This conditional expectation means the current position is the best conditional prediction of the next position.

Such processes are examples of martingales, a topic developed later in this stochastic-process section.

Centering a Biased Walk

If the drift is

then the centered process

has zero expected incremental drift.

This is an early example of separating deterministic trend from random fluctuation.

Scaling and Diffusion

A symmetric random walk spreads on a scale proportional to

Under suitable rescaling, random walks lead toward continuous stochastic models such as Brownian motion.

This connection is foundational in probability, statistical physics, finance, and diffusion modeling.

Random Walks and the Central Limit Theorem

Since

the central limit theorem applies to many random walks with independent identically distributed increments.

For large \(n\), the standardized position

is approximately standard normal under the usual assumptions.

Simulation of a Random Walk

A random walk is straightforward to simulate.

1. Choose the initial position \(X_0\).
2. Generate a random step \(Y_1\).
3. Set \(X_1=X_0+Y_1\).
4. Generate another random step.
5. Continue recursively.
6. Record the positions to obtain a sample path.

What Simulation Can Show

Repeated simulations can help estimate:

• position distributions;
• hitting probabilities;
• first-passage times;
• maximum and minimum positions;
• absorption frequencies;
• long-run state frequencies on finite graphs;
• the effect of directional bias.

Simulation Does Not Replace Exact Structure

Simulation provides numerical evidence and approximate probabilities.

Exact formulas, recurrences, transition matrices, and combinatorial arguments can reveal structure that simulation alone may hide.

The two approaches are strongest when used together.

Applications of Random Walks

Random walks appear in models of:

• particle motion and diffusion;
• financial price changes;
• inventory fluctuations;
• queue lengths;
• population changes;
• network navigation;
• search algorithms;
• genetic drift;
• reliability systems;
• statistical sampling methods.

Model Assumption: Independent Steps

The standard random walk assumes the increments

are independent.

Real systems can violate this assumption through momentum, persistence, feedback, environmental dependence, or resource constraints.

Model Assumption: Identical Step Distribution

A standard time-homogeneous walk also assumes the same step distribution at every time.

If the step probabilities change over time or depend on position, the model becomes more general and some simple formulas must be modified.

Model Assumption: State Description

Position alone forms a Markov state only when the next-step distribution is determined by the current position under the model.

If the next move also depends on hidden momentum, previous direction, age, or another variable, then the state may need to be augmented.

Common Error: Confusing Steps with Positions

The increment \(Y_n\) is the change made at step \(n\).

The position \(X_n\) is the cumulative result after \(n\) steps.

They are related by

but they are not the same random variable.

Common Error: Assuming Expected Position Is Typical Position

In a symmetric walk,

when \(X_0=0\).

This does not mean that the walk is usually at \(0\). The distribution spreads with standard deviation \(\sqrt{n}\).

Common Error: Ignoring Parity

A nearest-neighbor walk starting at \(0\) cannot be at an odd position after an even number of steps, or at an even position after an odd number of steps.

Before calculating a probability, check whether the requested position is even reachable at that time.

Common Error: Multiplying When Paths Should Be Added

For one particular sequence of steps, multiply the step probabilities.

When several distinct paths lead to the same final event, add the probabilities of those paths.

This is the same principle used in multi-step Markov-chain calculations.

Common Error: Confusing Return Probability with Return Time

Saying that a symmetric one-dimensional walk returns to the origin with probability \(1\) does not specify how long the return takes.

Probability of eventual return and distribution of return time are separate quantities.

Common Error: Treating Probability \(1\) as Certainty for Every Path

An event with probability \(1\) is called almost sure, but probability theory can still contain exceptional sample paths of probability \(0\).

Mathematical statements about recurrence are probabilistic statements over the full collection of paths.

Common Error: Forgetting Boundary Rules

A bounded random walk is incomplete until the behavior at its boundaries is specified.

Absorbing, reflecting, and other boundary rules produce different stochastic processes even when the interior steps are identical.

A Reliable Procedure for Position Probabilities

1. Identify the starting position \(X_0\).
2. Identify the step distribution.
3. Translate the target position into a required number of right and left steps.
4. Check parity and feasibility.
5. Use a binomial probability when the increments are independent and identically distributed \(\pm1\) steps.
6. Interpret the result in terms of all step sequences leading to the target.

A Reliable Procedure for Expectation and Variance

1. Compute \(E[Y]\) for one increment.
2. Compute \(\operatorname{Var}(Y)\).
3. Use \(X_n=X_0+\sum_{k=1}^{n}Y_k\).
4. Apply linearity of expectation.
5. For independent increments, add variances.
6. Separate drift from random spread in the interpretation.

A Reliable Procedure for Boundary-Hitting Problems

1. Identify the target and competing boundary states.
2. Define a hitting probability such as \(h_i\).
3. Condition on the first step.
4. Write the resulting recurrence relation.
5. Apply the boundary conditions.
6. Solve the recurrence.
7. Check that the resulting probabilities lie between \(0\) and \(1\).

Example: Full Position Workflow

A symmetric random walk starts at

Find the probability that

Since

we need

Therefore,

Exactly four right steps and two left steps are required, so

Hence,

Practice 1: Build a Sample Path

A walk begins at \(X_0=0\) and takes the steps

List the positions \(X_0,X_1,\ldots,X_5\).

Practice 2: Identify Possible Positions

What positions can a nearest-neighbor random walk starting at \(0\) occupy after five steps?

Practice 3: Position Probability

For a symmetric walk starting at \(0\), find

Practice 4: Expected Step

Suppose

Find \(E[Y]\).

Practice 5: Expected Position

A walk starts at \(X_0=5\) and has \(p=0.6\).

Find \(E[X_{10}]\).

Practice 6: Variance

For a symmetric walk, find

and the corresponding standard deviation.

Practice 7: Symmetric Gambler's Ruin

A symmetric walk moves on

with absorbing boundaries \(0\) and \(12\).

Starting at \(3\), what is the probability of reaching \(12\) before \(0\)?

Practice 8: Expected Absorption Time

In the same symmetric gambler's ruin model with \(N=12\), find the expected time to absorption when the walk starts at \(3\).

Practice 9: Random Walk on a Graph

A vertex has degree \(5\), and a simple random walk chooses uniformly among its neighbors.

What is the transition probability along each incident edge?

Practice 10: Identify the Error

A student says that a symmetric random walk starting at \(0\) is always at \(0\) on average, so it does not spread.

Explain the error.

Practice Answers

Practice 1

Starting from \(0\),

Therefore, the sample path is

Practice 2

After five steps, the possible positions are

Practice 3

To end at \(2\) after four steps,

so \(R_4=3\).

Therefore,

Practice 4

Thus,

Practice 5

The drift per step is

Therefore,

Practice 6

For a symmetric walk,

Therefore,

and

Practice 7

For the symmetric gambler's ruin model,

Thus,

Practice 8

The expected absorption time is

Therefore,

Hence,

Practice 9

Uniform choice among \(5\) neighbors gives

along each incident edge.

Practice 10

The statement confuses mean position with spread.

For a symmetric walk,

but

Therefore, positive and negative positions cancel in the mean while the distribution itself becomes increasingly dispersed.

What to Remember

A random walk accumulates random increments:

• A standard one-dimensional walk uses steps \(+1\) and \(-1\).
• The walk is symmetric when \(p=1/2\) and biased otherwise.
• A nearest-neighbor random walk is a Markov chain because the next-step law depends on the current position.
• For independent \(\pm1\) steps, position probabilities can be obtained from binomial probabilities.
• Starting from \(0\), the parity of \(X_n\) must match the parity of \(n\).
• The drift is \(E[Y]=2p-1\).
• The expected position is \(E[X_n]=X_0+n(2p-1)\).
• The variance is \(4np(1-p)\).
• For the symmetric walk, \(\operatorname{Var}(X_n)=n\) and the standard deviation is \(\sqrt{n}\).
• Hitting probabilities and hitting times answer different questions.
• Boundary behavior must be specified in bounded walks.
• The symmetric one-dimensional walk is recurrent.
• Simple symmetric walks are recurrent in dimensions \(1\) and \(2\) and transient in dimensions \(3\) and higher.
• Random walks extend naturally to graphs, networks, higher dimensions, and more general increment distributions.
• Simulation is useful for exploring random-walk behavior but does not replace exact probabilistic structure.

The essential modeling pattern is: random local steps accumulate into global stochastic motion.

Where We Go Next

Random walks describe how one evolving state changes through repeated random increments. Another major class of stochastic processes tracks how a population of objects reproduces, grows, or disappears from one generation to the next.

The next lesson, Branching Processes, develops stochastic population growth through random offspring counts, generation sizes, extinction, expected growth, and criticality.