of being at j is the same as being at —j. Computing E(|5
n
|) is not
so easy; however, it is straightforward to calculate E(S^). Note that
E ( ^ ) = E[(X1
+
.-. + Xn)2}
= !(*?)+x;E(xixj).
. 7 = 1 i^3
Since X] = 1 and E(XiXj) = E(Xi)E(Xj) = 0iii^j, we see that
E ( S
2
) = n .
This says that the expected squared distance is n, and we can infer
(at least informally) that the expected distance should be of order
yjn (it is actually about Cy/n for a constant c different than 1).
Where do we expect to be after n steps? Since the walker always
moves from an even integer to an odd integer or from an odd integer
to an even integer, we know for sure that we are at an even integer if
n is even or an odd integer if n is odd. Let us suppose that we have
gone 2n steps, and ask what is the probability that we are at the
even integer 2j. Using the binomial distribution, we can determine
the probability exactly. There are 22n different sequences of +l's
and l's of length 2n. Each one has probability 2 _ 2 n of occurring.
In order for ^ n to equal 2j we need n + j moves to the right (+1)
and n j moves to the left (—1). The number of sequences with
n + j "+l"s and n j "—l"s is given by the appropriate binomial
coefficient. Hence
2 M o - 2 » _
0
- 2 n (2n)!
P{52„ = 2j} = , . 2 - ^ = 2
\n + jj {n + j)\{n-j)\
In particular,
P
{
5
2 n
= 0} = 2 - 2 " ^ .
n\n\
This is a nice exact expression. Unfortunately, it is not so easy to see
how big or small it is. What we need is an approximate formula for
n\. There is such a formula, first published by J. Stirling in 1730 and
now known as Stirling's formula. It is our goal here to see how this
formula can be derived.
Previous Page Next Page