Let 
steps of equal length be taken along a line. Let 
be the probability of taking a step to the right, 
the probability of taking a step to the left, 
the number of steps taken to the right, and 
the number of steps taken to the left. The quantities 
,
,
,
,
and 
are related by
 |
(1)
|
and
 |
(2)
|
Now examine the probability of taking exactly 
steps out of 
to the right. There are 
ways of taking 
steps to the right and 
to the left, where 
is a binomial coefficient.
The probability of taking a particular ordered sequence of 
and 
steps is 
. Therefore,
 |
(3)
|
where 
is a factorial. But this is simply a binomial
distribution, so the mean number of steps 
to the right is
 |
(4)
|
and the mean number of steps to the left is
 |
(5)
|
Similarly, the variance is given by
 |
(6)
|
and the root-mean-square deviation is
 |
(7)
|
Consider now the distribution of the distances 
traveled after a given number of steps,
 |
(8)
|
as opposed to the number of steps in a given direction. The above plots show 
for 
and three values 
, 
, and 
, 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 
.
Surprisingly, the most probable number of sign changes in a walk is 0, followed by 1, then 2, etc.
For a random walk with 
, the probability 
of traveling a given distance 
after 
steps is given in the following table.
| steps |  |  |  |  |  | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 1 | ||||||||||
| 1 |  | 0 |  | ||||||||
| 2 |  | 0 |  | 0 |  | ||||||
| 3 |  | 0 |  | 0 |  | 0 |  | ||||
| 4 |  | 0 |  | 0 |  | 0 |  | 0 |  | ||
| 5 |  | 0 |  | 0 |  | 0 |  | 0 |  | 0 |  |
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
 |
(9)
|
(Papoulis 1984, p. 291). The moments
 |
(10)
|
of this distribution of signed distances are then given by
 |  |  |
(11)
|
 |  |  |
(12)
|
 |  |  |
(13)
|
 |  |  |
(14)
|
so the mean is 
, the skewness is 
, and the kurtosis excess
is
 |
(15)
|
The expectation value of the absolute distance after 
steps is therefore given by
 |  |  |
(16)
|
 |  |  |
(17)
|
This sum can be done symbolically by separately considering the cases 
even and 
odd. First, consider even 
so that 
.
Then
 |  | ![(N!)/(2^N)[sum_(d=-2J,; -2(J-1),...)^(-2)(|d|)/(((2J+d)/2)!((2J-d)/2)!)+0+sum_(d=2,4,...)^(2J)(|d|)/(((2J+d)/2)!((2J-d)/2)!)]](/images/equations/RandomWalk1-Dimensional/Inline85.svg) |
(18)
|
 |  | ![(N!)/(2^N)[sum_(d=-J,-(J-1),...)^(-1)(|2d|)/(((2J+2d)/2)!((2J-2d)/2)!)+sum_(d=1,2,...)^(J)(|2d|)/(((2J+2d)/2)!((2J-2d)/2)!)]](/images/equations/RandomWalk1-Dimensional/Inline88.svg) |
(19)
|
 |  | ![(N!)/(2^N)[2sum_(d=1)^(J)(2d)/((J+d)!(J-d)!)]](/images/equations/RandomWalk1-Dimensional/Inline91.svg) |
(20)
|
 |  |  |
(21)
|
But this sum can be evaluated analytically as
 |
(22)
|
Writing 
,
plugging back in, and simplifying gives
 |
(23)
|
where 
is the double factorial.
Now consider 
odd, so 
. Then
 |  |  |
(24)
|
 |  | ![(N!)/(2^N)[sum_(d=-(2J-1),; -(2J+1),...)^(-1)(|d|)/(((2J-1+d)/2)!((2J-1-d)/2)!)+sum_(d=1,3,...)^(2J-1)(|d|)/(((2J-1+d)/2)!((2J-1-d)/2)!)]](/images/equations/RandomWalk1-Dimensional/Inline104.svg) |
(25)
|
 |  | ![(N!)/(2^(N-1))[sum_(d=1,3,...)^(2J-1)d/(((2J-1+d)/2)!((2J-1-d)/2)!)]](/images/equations/RandomWalk1-Dimensional/Inline107.svg) |
(26)
|
 |  | ![(N!)/(2^(N-1))[sum_(d=2,4,...)^(2J)(d-1)/(((2J-2+d)/2)!((2J-d)/2)!)]](/images/equations/RandomWalk1-Dimensional/Inline110.svg) |
(27)
|
 |  | ![(N!)/(2^(N-1))[sum_(d=1)^(J)(2d-1)/((J+d-1)!(J-d)!)].](/images/equations/RandomWalk1-Dimensional/Inline113.svg) |
(28)
|
But this sum can be evaluated analytically as
![sum_(d=1)^J(2d-1)/((J+d-1)!(J-d)!)=1/([Gamma(J)]^2).](/images/equations/RandomWalk1-Dimensional/NumberedEquation14.svg) |
(29)
|
Writing 
,
plugging back in, and simplifying gives
 |  | ![(N!)/(2^(N-1)[Gamma(1/2+1/2N)]^2)](/images/equations/RandomWalk1-Dimensional/Inline117.svg) |
(30)
|
 |  |  |
(31)
|
 |  |  |
(32)
|
Both the even and odd solutions can be written in terms of 
as
 |
(33)
|
or explicitly in terms of 
as
 |  | ](/images/equations/RandomWalk1-Dimensional/Inline128.svg) |
(34)
|
 |  |  |
(35)
|
The first few values of 
for 
, 1, ... are therefore 0, 1, 1, 3/2, 3/2, 15/8, 15/8, 35/16,
35/16, ... (OEIS A086116 and A060818;
Abramowitz and Stegun 1972, Prévost 1933, Hughes 1995), where the terms of
each pair are given by the generating function
 |
(36)
|
These numbers also arise in the heads-minus-tails distribution.
Now, examine the asymptotic behavior of 
. The asymptotic expansion of the gamma
function ratio is
 |
(37)
|
(Graham et al. 1994), so plugging in the expression for 
gives the asymptotic series
 |
(38)
|
where the top signs are taken for 
even and the bottom signs for
odd. Therefore, for large 
,
 |
(39)
|
which is also shown by Grünbaum (1960), Mosteller et al. (1961, p. 14), and König et al. (1999).
Tóth (2000) has proven that there are no more than three most-visited sites in a simple symmetric random walk in one dimension with unit steps.
