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
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
— Does the walker always return to the starting point; or more
generally, is every integer visited infinitiely often by the walker?