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.