1.1. Simple random walk 7
and
log 1
1
n
−1/2
=
1
2n
+
O(n−2).
By taking logarithms in (1.2) and adding the terms we finish the proof
of (1.1). In fact (see Exercise 1.19), we can show that
(1.5) n! = C0
nn+ 1
2
e−n
1 +
O(n−1)
.
1.1.3. Central limit theorem. We now use Stirling’s formula to
estimate the probability that the random walker is at a certain posi-
tion. Let Sn be the position of a simple random walker on the integers
assuming S0 = 0. For every integer j, we have already seen that the
binomial distribution gives us
P{S2n = 2j} =
2n
n + j
2−2n
=
2n!
(n + j)!(n j)!
2−2n.
Let us assume that |j| n/2. Then plugging into Stirling’s formula
and simplifying gives us
P{S2n = 2j}


2
C0
1
j2
n2
−n
1 +
j
n
−j
1
j
n
j
n
n2 j2
1/2
.
(1.6)
In fact (if one uses (1.5)), there is a c such that the ratio of the two
sides is within distance c/n of 1 (we are assuming |j| n/2).
What does this look like as n tends to infinity? Let us first
consider the case j = 0. Then we get that
P{S2n = 0}

2
C0 n1/2
.
We now consider j of order

n. Note that this confirms our previ-
ous heuristic argument that the probability should be like a constant
times
n−1/2,
since the typical distance is of order

n.
Previous Page Next Page