ramdom walk

[papernuke]

I read in this place that it said if you walked straight foreward, in the 1st and 2nd dimensions you would always end up in the same place. It also said that if you did that in the 3rd dimension, there would be a 34% chance that you would, and in the fourth, 19%. Can someone explain that to me please?

[moonlord]

You don't walk straight forward, you turn randomly at every point. Wikipedia is your best friend about this.

[wendy]

A random walk, although random as such, can be restricted to the edges of a lattice. For example, an ant, on say, chicken-wire {6,3}, might choose to walk the full length of each side, and then randomly choose between the two or three wires at the end.

In two dimensions, there is eventually a large chance that you will cross your path, and even a lesser that you will end up where you started. But this is likely to happen.

In three and higher dimensions, the chance of even crossing your path is less likely. It gets much less likely as the dimension goes higher. The figures quoted as 34% and 19% are not known to me, but probably are correct.

W

[jinydu]

http://mathworld.wolfram.com/RandomWalk ... ional.html

Amazingly, it has been proven that on a two-dimensional lattice, a random walk has unity probability of reaching any point (including the starting point) as the number of steps approaches infinity.

http://mathworld.wolfram.com/RandomWalk ... ional.html

On a three-dimensional lattice, a random walk has less than unity probability of reaching any point (including the starting point) as the number of steps approaches infinity. The probability of reaching the starting point again is 0.3405373296.... This is one of Pólya's random walk constants.

http://mathworld.wolfram.com/PolyasRand ... tants.html

The last link gives a (non-elementary) formula for the probability of eventually (that is, as the number of steps approaches infinity) of returning to the starting point for an arbitrary number of dimensions.

[jinydu]

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.

[PWrong]

The product of a_n is the exponential of the sum of ln(a_n). So you need to show that this sum tends to - infinity.

Then you can use the fact that ln(1-x) < -x for all 0<x<1