
Imagine that a particle is walking in a two-dimensional space, starting at the origin . At every time-step (or “epoch”)
it takes a
vertical step. At every step, the particle either moves up by
, or down by
. This walk is “unbiased” in the sense that the up/down steps are equiprobable.
In this post, we will discuss some natural questions about this “unbiased” or “simple” random walk. For example, how long will it take for the particle to return to zero? What is the probability that it will ever reach +1? When will it touch for the first time? Contents of this post are a summary of the Chapter “Random Walks” from the awesome “Introduction to Probability” (Volume I) by William Feller. Also, this is an excellent reference.
Edit: the Biased Case. The biased walk follows
.
The lazy walk follows
.
In the exposition, we’ll first state the unbiased case and when appropriate, follow it up with the biased case.