Simple Random Walk

and Stirling's Formula

We will start our discussion of contemporary probability by discussing

an old problem — at least a few hundred years old. Imagine a walker

moving randomly on the integers. The walker starts at 0 and at every

integer time n the walker flips a fair coin and moves one step to the

right if it comes up heads and one step to the left if it comes up tails.

The position of the walker at time n will be denoted by Sn. Sn is a

random variable; the position depends on the outcomes of the n flips

of the coin. We assume So = 0, and we can write

Sn = X\ + • • • -f X

n

,

where Xi = 1 if the ith flip was heads and X\ = — 1 if the ith flip

was tails. We assume that the coin flips are independent, so that the

random variables XL, X2,... are indepedent. Three natural questions

to ask are:

— About how far does the walker go in n steps?

— Where do we expect the walker to be after n steps? (The

answer to this should involve a probability distribution for the possible

positions.)

— Does the walker always return to the starting point; or more

generally, is every integer visited infinitiely often by the walker?

1