= Simple random walk
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> give
$$
\mathbb E S_n=0,\qquad \operatorname{Var}(S_n)=n,\qquad \sigma_n=\sqrt n.
$$
For example, after $80$ steps the <expected value> is zero, the <variance> is $80$, and the <standard deviation> is $\sqrt{80}\approx8.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.
\Image[/random-walk-paths-and-drift.png]
{title=Four fair and two biased unit-step random-walk paths, with their expected values and bands one standard deviation wide on either side.}
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>.
Back to article page
