Random Walk--1-D

Let $N$ steps of equal length be taken along a Line. Let $p$ be the probability of taking a step to the right, $q$ the probability of taking a step to the left, $n_1$ the number of steps taken to the right, and $n_2$ the number of steps taken to the left. The quantities $p$, $q$, $n_1$, $n_2$, and $N$ are related by

$$p + q = 1$$ (1)

and

$$n_1 + n_2 = N.$$ (2)

Now examine the probability of taking exactly $n_1$ steps out of $N$ to the right. There are ${N\choose n_1}={n_1+n_2\choose n_1}$ ways of taking $n_1$ steps to the right and $n_2$ to the left, where ${n\choose m}$ is a Binomial Coefficient. The probability of taking a particular ordered sequence of $n_1$ and $n_2$ steps is $p^{n_1}q^{n_2}$. Therefore,

$$P(n_1) = {(n_1+n_2)!\over n_1!n_2!} p^{n_1}q^{n_2} = {N!\over n_1!(N-n_1)!} p^{n_1}q^{N-n_1},$$ (3)

where $n!$ is a Factorial. This is a Binomial Distribution and satisfies

$$\sum_{n_1=0}^N P(n_1) = (p+q)^N = 1^N = 1.$$ (4)

The Mean number of steps $n_1$ to the right is then

$$\left\langle{n_1}\right\rangle{} \equiv \sum_{n_1=0}^N n_1P(n_1) = \sum_{n_1=0}^N {N!\over n_1!(N-n_1)!} p^{n_1}q^{N-n_1}n_1,$$ (5)

but

$$n_1p^{n_1} = p{\partial\over\partial p} p^{n_1},$$ (6)

so

$$\left\langle{n_1}\right\rangle{} = \sum_{n_1=0}^N {N!\over n_1!(N-n_1)!} \left({p{\partial\over\partial p} p^{n_1}}\right)q^{N-n_1}$$

$$= p{\partial \over \partial p} \sum_{n_1=0}^N {N!\over n_1!(N-n_1)!} p^{n_1}q^{N-n_1}$$

$$= p {\partial\over \partial p} (p+q)^N = pN(p+q)^{N-1} = pN.$$ (7)

From the Binomial Theorem,

$$\left\langle{n_2}\right\rangle{} = N-\left\langle{n_1}\right\rangle{} = N(1-p)=qN.$$ (8)

The Variance is given by

$${\sigma_{n_1}}^2 = \left\langle{{n_1}^2}\right\rangle{}- \left\langle{n_1}\right\rangle{}^2.$$ (9)

But

$$\left\langle{{n_1}^2}\right\rangle{} = \sum_{n_1=0}^N {N!\over n_1!(N-n_1)!} p^{n_1}q^{N-n_1}{n_1}^2,$$ (10)

so

$${n_1}^2p^{n_1} = n_1\left({p{\partial\over\partial p}}\right)p^{n_1} = \left({p{\partial\over\partial p}}\right)^2 p^{n_1},$$ (11)

and

$$\left\langle{{n_1}^2}\right\rangle{} = \sum_{n_1=0}^N {N!\over n_1!(N-n_1)!}\left({p{\partial\over\partial p}}\right)^2 p^{n_1}q^{N-n_1}$$

$$= \sum_{n_1=0}^N {N!\over n_1!(N-n_1)!}\left({p{\partial\over\partial p}}\right)^2 p^{n_1}q^{N-n_1}$$

$$= \left({p {\partial\over\partial p}}\right)^2 \sum_{n_1=0}^N {N!\over n_1!(N-n_1)!} p^{n_1}q^{N-n_1}$$

$$= \left({p {\partial\over\partial p}}\right)^2 (p+q)^N = p{\partial\over\partial p} [pN(p+q)^{N-1}]$$

$$= p[N(p+q)^{N-1} + pN(N-1)(p+q)^{N-2}]$$

$$= p[N + pN(N-1)]$$

$$= pN[1+pN-p] = (Np)^2 + Npq$$

$$= \left\langle{n_1}\right\rangle{}^2 + Npq.$$ (12)

Therefore,

$${\sigma_{n_1}}^2 = \left\langle{{n_1}^2}\right\rangle{}- \left\langle{n_1}\right\rangle{}^2=Npq,$$ (13)

and the Root-Mean-Square deviation is

$$\sigma_{n_1} = \sqrt{Npq}.$$ (14)

For a large number of total steps $N$, the Binomial Distribution characterizing the distribution approaches a Gaussian Distribution.

Consider now the distribution of the distances $d_N$ traveled after a given number of steps,

$$d_N\equiv n_1-n_2=2n_1-N,$$ (15)

as opposed to the number of steps in a given direction. The above plots show $d_N(p)$ for $N=200$ and three values $p=0.1$, $p=0.5$, and $p=0.9$, respectively. Clearly, weighting the steps toward one direction or the other influences the overall trend, but there is still a great deal of random scatter, as emphasized by the plot below, which shows three random walks all with $p=0.5$.

Surprisingly, the most probable number of sign changes in a walk is 0, followed by 1, then 2, etc.

For a random walk with $p=1/2$, the probability $P_N(d)$ of traveling a given distance $d$ after $N$ steps is given in the following table.

steps	$-5$	$-4$	$-3$	$-2$	$-1$	0	1	2	3	4	5
0						1
1					${\textstyle{1\over 2}}$	0	${\textstyle{1\over 2}}$
2				${\textstyle{1\over 4}}$	0	${\textstyle{2\over 4}}$	0	${\textstyle{1\over 4}}$
3			${\textstyle{1\over 8}}$	0	${\textstyle{3\over 8}}$	0	${\textstyle{3\over 8}}$	0	${\textstyle{1\over 8}}$
4		${\textstyle{1\over 16}}$	0	${\textstyle{4\over 16}}$	0	${\textstyle{6\over 16}}$	0	${\textstyle{4\over 16}}$	0	${\textstyle{1\over 16}}$
5	${\textstyle{1\over 32}}$	0	${\textstyle{5\over 32}}$	0	${\textstyle{10\over 32}}$	0	${\textstyle{10\over 32}}$	0	${\textstyle{5\over 32}}$	0	${\textstyle{1\over 32}}$

In this table, subsequent rows are found by adding Half of each cell in a given row to each of the two cells diagonally below it. In fact, it is simply Pascal's Triangle padded with intervening zeros and with each row multiplied by an additional factor of 1/2. The Coefficients in this triangle are given by

$$P_N(d)={1\over 2^N} {N \choose {\textstyle{d+N\over 2}}}.$$ (16)

The expectation value of the distance after $N$ steps is therefore

$$\left\langle{d_N}\right\rangle{} = \sum_{d=-N,-(N-2),\ldots}^N \vert d\vert\, P_N(d)$$

$$= {1\over 2^N} \sum_{d=-N,-(N-2),\ldots}^N {\vert d\vert\, N!\over\left({N+d\over 2}\right)! \left({N-d\over 2}\right)!}.$$ (17)

This sum can be done symbolically by separately considering the cases $N$ Even and $N$ Odd. First, consider Even $N$ so that $N\equiv 2J$. Then

$\left\langle{d_{2J}}\right\rangle{} = {N!\over 2^N} \left[{\sum_{d=-2J,\atop -2... ...ert d\vert\over\left({2J+d\over 2}\right)! \left({2J-d\over 2}\right)!}}\right.$
$\left.{+\sum_{d=0} {\vert d\vert\over\left({2J+d\over 2}\right)! \left({2J-d\o... ...ert d\vert\over\left({2J+d\over 2}\right)! \left({2J-d\over 2}\right)!}}\right]$
$={N!\over 2^N} \left[{\sum_{d=-J,-(J-1),\ldots}^{-1} {\vert 2d\vert\over\left(... ... 2d\vert\over\left({2J+2d\over 2}\right)! \left({2J-2d\over 2}\right)!}}\right]$
$= {N!\over 2^N} \left[{2\sum_{d=1}^J {2d\over(J+d)!(J-d)!}}\right]$
$= {N!\over 2^{N-2}} \sum_{d=1}^J {d\over(J+d)!(J-d)!}.$	(18)

But this sum can be evaluated analytically as

$$\sum_{d=1}^J {d\over (J+d)!(J-d)!} = {J\over 2\Gamma^2(1+J)},$$ (19)

which, when combined with $N=2J$ and plugged back in, gives

$$\left\langle{d_{2J}}\right\rangle{} = {\Gamma(2J+1)J\over 2^{2J-1}\Gamma^2(1+J)} = {\Gamma(2J)\over 2^{2J-2}\Gamma^2(J)}.$$ (20)

But the Legendre Duplication Formula gives

$$\Gamma(2J)={2^{2J-1/2}\Gamma(J)\Gamma(J+{\textstyle{1\over 2}})\over \sqrt{2\pi}},$$ (21)

so

$$\left\langle{d_{2J}}\right\rangle{} = {{1\over\sqrt{2\pi}} 2... ...r\sqrt{\pi}} {\Gamma(J+{\textstyle{1\over 2}})\over\Gamma(J)}.$$ (22)

Now consider $N$ Odd, so $N\equiv 2J-1$. Then

$\left\langle{d_{2J-1}}\right\rangle{}={N!\over 2^N}\left[{\sum_{d=-(2J-1),\atop... ... d\vert\over\left({2J-1+d\over 2}\right)!\left({2J-1-d\over 2}\right)!}}\right.$
$\quad\phantom{=} \left.{\mathop{+} \sum_{d=1,3,\ldots}^{2J-1} {\vert d\vert\over \left({2J-1+d\over 2}\right)! \left({2J-1-d\over 2}\right)!}}\right]$
$\quad = {N!\over 2^{N-1}} \left[{\,\sum_{d=1,3,\ldots}^{2J-1} {d\over \left({2J-1+d\over 2}\right)! \left({2J-1-d\over 2}\right)!}}\right]$
$\quad = {N!\over 2^{N-1}} \left[{\,\sum_{d=2,4,\ldots}^{2J} {d-1\over \left({2J-2+d\over 2}\right)! \left({2J-d\over 2}\right)!}}\right]$
$\quad = {\Gamma(2J)\over 2^{2J-2}} \left[{\,\sum_{d=1}^{J} {2d-1\over (J+d-1)!(J-d)!}}\right]$
$\quad = \Gamma(2J) \left[{{1+J-{}_2F_1(1,-J;J;1)\over 2^{2J-2}\Gamma(J)\Gamma(1+J)}+{1\over \Gamma(2J)}}\right]$
$= {{2^{2J-1/2}\over\sqrt{2\pi}} \Gamma(J)\Gamma(J+1/2)\over 2^{2J-2}\Gamma^2(J)J} [1+J-{}_2F_1(1,-J;J;-1)]+1$
$\quad = {2\over\sqrt{\pi}} {\Gamma(J+{\textstyle{1\over 2}})\over J\Gamma(J)} [1+J-{}_2F_1(1,-J;J;-1)]+1.$	(23)

But the Hypergeometric Function ${}_2F_1(a,b;c;z)$ has the special value

$${}_2F_1(1,-J;J;-1) = {\sqrt{\pi}\over 2} {J\Gamma(J)\over \Gamma(J+{\textstyle{1\over 2}})}+1,$$ (24)

so

$$\left\langle{d_{2J-1}}\right\rangle{} = {2\over\sqrt{\pi}} {\Gamma(J+{\textstyle{1\over 2}})\over\Gamma(J)}.$$ (25)

Summarizing the Even and Odd solutions,

$$\left\langle{d_N}\right\rangle{}={2\over\sqrt{\pi}}{\Gamma(J+{\textstyle{1\over 2}})\over\Gamma(J)},$$ (26)

where

$$\cases{ J={\textstyle{1\over 2}}N & for $N$\ even\cr J={\textstyle{1\over 2}}(N+1) & for $N$\ odd.\cr}$$ (27)

Written explicitly in terms of $N$,

$$\left\langle{d_N}\right\rangle{}=\cases{ {2\over\sqrt{\pi}}... ...style{1\over 2}}N+{\textstyle{1\over 2}})} & for $N$\ odd.\cr}$$ (28)

The first few values of $\left\langle{d_N}\right\rangle{}$ are then

$$\left\langle{d_0}\right\rangle{} = 0$$

$$\left\langle{d_1}\right\rangle{}=\left\langle{d_2}\right\rangle{} = 1$$

$$\left\langle{d_3}\right\rangle{}=\left\langle{d_4}\right\rangle{} = {\textstyle{3\over 2}}$$

$$\left\langle{d_5}\right\rangle{}=\left\langle{d_6}\right\rangle{} = {\textstyle{15\over 8}}$$

$$\left\langle{d_7}\right\rangle{}=\left\langle{d_8}\right\rangle{} = {\textstyle{35\over 16}}$$

$$\left\langle{d_9}\right\rangle{}=\left\langle{d_{10}}\right\rangle{} = {\textstyle{315\over 128}}$$

$$\left\langle{d_{11}}\right\rangle{}=\left\langle{d_{12}}\right\rangle{} = {\textstyle{693\over 256}}$$

$$\left\langle{d_{13}}\right\rangle{}=\left\langle{d_{14}}\right\rangle{} = {\textstyle{3003\over 1024}}.$$

Now, examine the asymptotic behavior of $\left\langle{d_N}\right\rangle{}$. The asymptotic expansion of the Gamma Function ratio is

$${\Gamma(J+{\textstyle{1\over 2}})\over\Gamma(J)}=\sqrt{J}\left({1-{1\over 8J}+{1\over 128J^2}+\ldots}\right)$$ (29)

(Graham et al. 1994), so plugging in the expression for $\left\langle{d_N}\right\rangle{}$ gives the asymptotic series

$$\left\langle{d_N}\right\rangle{}=\sqrt{2N\over\pi}\left({1\m... ...r 32N^2}\pm{5\over 128N^3}-{21\over 2048N^4}\mp\ldots}\right),$$ (30)

where the top signs are taken for $N$ Even and the bottom signs for $N$ Odd. Therefore, for large $N$,

$$\left\langle{d_N}\right\rangle{} \sim \sqrt{2N\over\pi}\,,$$ (31)

which is also shown in Mosteller et al. (1961, p. 14).

See also Binomial Distribution, Catalan Number, p-Good Path, Pólya's Random Walk Constants, Random Walk--2-D, Random Walk--3-D, Self-Avoiding Walk

References

Chandrasekhar, S. ``Stochastic Problems in Physics and Astronomy.'' Rev. Modern Phys. 15, 1-89, 1943. Reprinted in Noise and Stochastic Processes (Ed. N. Wax). New York: Dover, pp. 3-91, 1954.

Feller, W. Ch. 3 in An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed., rev. printing. New York: Wiley, 1968.

Gardner, M. Chs. 6-7 in Mathematical Carnival: A New Round-Up of Tantalizers and Puzzles from Scientific American. New York: Vintage Books, 1977.

Graham, R. L.; Knuth, D. E.; and Patashnik, O. Answer to problem 9.60 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.

Hersh, R. and Griego, R. J. ``Brownian Motion and Potential Theory.'' Sci. Amer. 220, 67-74, 1969.

Kac, M. ``Random Walk and the Theory of Brownian Motion.'' Amer. Math. Monthly 54, 369-391, 1947. Reprinted in Noise and Stochastic Processes (Ed. N. Wax). New York: Dover, pp. 295-317, 1954.

Mosteller, F.; Rourke, R. E. K.; and Thomas, G. B. Probability and Statistics. Reading, MA: Addison-Wesley, 1961.