Monday, July 30, 2007

Random Walking

What is the probability that two random walkers starting from a point meet each other during their walk?

We consider random walks in 1, 2 and 3 dimensions.

A 1d random walk can be thought of as a random walk along a long street(Similar to number line), where at each point he may choose to proceed in the same direction or reverse his direction.

A 2d random walk can be thought of as a random walk on a 2d grid, where at each point he may choose any one of four directions(forward, backward, left and right).

Similarly a random walker walking in 3d space has 6 options at each point(Four directions of 2d walk plus up and down).

I wrote a python program to simulate random walks in 1, 2 and 3 dimensions.

The function randwalk simulates a random walk in any dimension. The dimension is determined by the parameter update which is a function which returns the new position of a random walker given his old position. The limit parameter limits the no: of steps taken by a random walker(Random walkers won't walk forever:-) ).


I obtained the following results.

Two 1d random walkers meet about 95% of time at an average of about 1 move before meeting each other.
Two 2d random walkers meet about 60-70% of time at an average of about 20 moves before meeting each other.
Two 3d random walkers meet about 30-35% of time at an average of about 10 moves (This is surprising) before meeting each other.

The above simulation is not very realistic. It assumes that both random walkers walk the same distance at the same pace.
Also, in real life, random walkers don't choose directions randomly. Instead, they may prefer one path over another according to their tastes and preferences.

References



Introduction to probability, Charles M. Grinstead and J . Laurie Snell

6 comments:

azhar said...

he he good one ...:)

Balagopal said...

thanks

Anonymous said...

Good work...
The result of 3d walk is not a convincing one.

Anonymous said...

-sandeep

manikantan said...

this was really exellent

Anonymous said...

@sandy

I still don't know why so few moves for 3d.

balu