by jinydu » Fri Aug 25, 2006 10:59 am
Here is my attempt to show that for a 1D random walk, the probability of returning to the starting point approaches 1 as the number of steps approaches infinity.
Let us define the starting point to be the origin. Any trajectory that returns to the origin must consist of an even number of steps, since the number of steps in the left and right directions must be equal.
Clearly, for each step, there are two equally probable outcomes: a step to the left and a step to the right. Thus, there are 2^n possible trajectories of size n, and if we fix the number of steps in our trajectory to be n, each individual trajectory has a probability of 1/(2^n) of occuring.
Now suppose we fix our trajectory to have 2n steps. We want to know how many trajectories of this size end up at the origin. To is equivalent to asking how many trajectories have an equal number of left and right steps. It is not so hard to see that this is the same as the number of ways to choose n objects from a collection of 2n objects (Think of a trajectory as a sequence of 2n blanks. If you fill in n of them with "lefts", you have completely determined the sequence, since the rest of the blanks must necessarily be "rights"). It is well known from combinatorics that the number of trajectories is thus (2n)!/((n!)(2n-n)!), which is just (2n)!/(n!)^2. So the probability of a trajectory with 2n steps finishing at the origin is (2n)!/(2^(2n) * (n!)^2).
A trajectory with n steps to never returns to the origin if and only if every "subtrajectory" consisting of the first 2m steps (with m any positive integer less than or equal to n/2) does not stop at the origin. As n goes to infinity, the probability of this happening is:
(Product from n = 1 to infinity) 1 - (2n)!/(2^(2n) * (n!)^2)
If I can show that the above product converges to zero, then the probability of never returning to the origin becomes vanishingly small as the number of steps approaches infinity. If this is the case, then clearly, the chances of returning to the starting point approaches certainty.
Hmm... Admittedly, I don't know what the to do next, although I can use Mathematica to hint that the the product "looks like" it approaches 0. The approximate values of the product for the first ten values of n are:
0.5
0.3125
0.214844
0.156097
0.117683
0.0911352
0.0720449
0.0578967
0.0471585
0.0388493
At n = 1000, the value of the product has decayed to about 2.31827 * 10^-16. That is, the probability that the walker has not yet returned to the starting point after 2000 steps is about 2.31827 * 10^-16.