1.1. Simple random walk 9

This gives the value C0 =

√

2π (see Exercise 1.21), and hence Stir-

ling’s formula can be written as

n! =

√

2π

nn+

1

2

e−n

1 +

O(n−1)

.

The limit in (1.7) is a statement of the central limit theorem (CLT)

for the random walk,

lim

n→∞

P{a

√

2n ≤ S2n ≤ b

√

2n} =

b

a

1

√

2π

e−x2/2

dx.

1.1.4. Returns to the origin.

♦

Recall that the sum

∞

n=1

n−a

converges if a 1 and diverges otherwise.

We now consider the number of times that the random walker

returns to the origin. Let Jn = 1{Sn = 0}. Here we use the indicator

function notation: if E is an event, then 1E or 1(E) is the random

variable that takes the value 1 if the event occurs and 0 if it does not

occur. The total number of visits to the origin by the random walker

is

V =

∞

n=0

J2n.

Note that

E[V ] =

∞

n=0

E[J2n] =

∞

n=0

P{S2n = 0}.

We know that P{S2n = 0} ∼ c/

√

n as n → ∞. Therefore,

E[V ] = ∞.

It is possible, however, for a random variable to be finite yet have an

infinite expectation, so we need to do more work to prove that V is

actually infinite.

♦

A well-known random variable with infinite expectation is that obtained

from the St. Petersburg Paradox. Suppose you play a game where you flip a

coin until you get tails. If you get k heads before flipping tails, then your payoff

is

2k.

The probability that you get exactly k heads is the probability of getting