= Simple random walk on the integer line
{title2=$S_n=2B_n-n$}
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>, with
$$
\mathbb P(\xi_j=+1)=p,\qquad \mathbb P(\xi_j=-1)=1-p,\qquad
S_n=\sum_{j=1}^n\xi_j,\qquad 0<p<1.
$$
The <simple symmetric random walk> has $p=1/2$; a <biased random walk> has $p\ne1/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>:
$$
B_n=\sum_{j=1}^n\mathbf1_{\{\xi_j=+1\}},\qquad
B_n\sim\operatorname{Binomial}(n,p),\qquad S_n=B_n-(n-B_n)=2B_n-n.
$$
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 $\binom43=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 function>
$$
\mathbb P(S_n=s)=
\begin{cases}
\displaystyle\binom{n}{(n+s)/2}p^{(n+s)/2}(1-p)^{(n-s)/2},
&s\in\{-n,-n+2,\ldots,n\},\\
0,&\text{otherwise}.
\end{cases}
$$
In particular, the endpoint must have the same <integer parity> as $n$: $S_n\equiv n\pmod2$. For $0<p<1$ the <support of a probability distribution> is exactly $\{-n,-n+2,\ldots,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 https://math.dartmouth.edu/~prob/prob/prob.pdf[Grinstead and Snell, Introduction to Probability, section 12.1].
\Image[/random-walk-endpoint-distributions.png]
{title=Exact binomial endpoint probabilities for fair walks of 20 and 80 steps and a biased walk of 80 steps; only even endpoints are possible.}
The endpoint identity and the <binomial distribution> give the <expected value>, <variance>, and <standard deviation>
$$
\mathbb E S_n=n(2p-1),\qquad
\operatorname{Var}(S_n)=4np(1-p),\qquad
\sigma_n=2\sqrt{np(1-p)}.
$$
A short direct check gives $\mathbb E\xi_j=2p-1$ and $\mathbb E\xi_j^2=1$, hence $\operatorname{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}\approx4.472$ to $\sqrt{80}\approx8.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}\approx8.532$, or $0.9539$ times the fair width, and $\sigma_n/n\approx0.1067$. Centering and dividing by each walk's own <standard deviation> gives, for $n>0$,
$$
Z_n=\frac{S_n-n(2p-1)}{2\sqrt{np(1-p)}},\qquad
\mathbb E Z_n=0,\qquad \operatorname{Var}(Z_n)=1.
$$
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\leq m\leq n$, $S_n=S_m+(S_n-S_m)$, where the second term is <independent> of $S_m$. Their <covariance> is therefore
$$
\operatorname{Cov}(S_m,S_n)=\operatorname{Var}(S_m)=4mp(1-p)>0.
$$
For 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> are
$$
P(x,y)=\begin{cases}p,&y=x+1,\\1-p,&y=x-1,\\0,&\text{otherwise}.\end{cases}
$$
These <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.
Back to article page
