Thursday, 28 April 2011

Isaac Newton's Random Walk

Poor Isaac Newton.  He was having a pleasant afternoon nap, but was disturbed by a gravity-driven apple.  His attempts at destroying the apple that fell on his head have almost led to the death of a poor innocent bystander, and he's had to explain his actions to the local constabulary.  After a long and gruelling day, he's visited the local pub, and drunk slightly too much cider (stupid apples).  Now, having stepped out of the pub, he has to get to his house at the end of the street.  Alternatively, he could go to his aunt's house, at the other end of the street.

Conveniently, the pub is located at the middle of the street, which is 20 metres long.  His house is at one end, his aunt's house is at the other end.  Both possible destinations are 10 metres away.  In his slightly tipsy state of mind, the best that Mr Newton can manage is a stride of 1 metre; however, he's so unbalanced (he's also developing an apple-shaped bruise on his head) that it's not guaranteed that he'll keep going in the same direction.  In fact, it's 50/50 each time on which way he'll go.

How many steps will it take him to get home?  And at the rate of one step every 10 seconds, how much time will it take?

There are two ways of solving this one: the pure maths way, or the spreadsheet way (actually do some experiments on a spreadsheet).  Let's do the spreadsheet way first.

Each step is 1 metre long, but can be +1 metre or -1 metre, so we need to randomly produce a +1 or a -1 and add it to the previous distance walked.  This is easy enough in a spreadsheet - with a column of random +1 and -1 and a column which sums the previous column.  The function I've used for the random numbers is:


I then look down the 'total distance covered' column until I find the first +10 or -10.

I've run the test 20 times, and have obtained the following results for the number of steps it takes Mr Newton:

22, 20, 30, 20, 82, 94, 142, 106, 52, 51, 76, 92, 44, 74, 142, 50, 25, 17, 82 and 16.

What is there to say on this?  Isaac only has to travel a net distance of 10 metres in either direction, and yet in some cases it's taken him over 100 steps to cover the distance (he's not just drunk, he's very drunk).  At his best, he's managed it in 16 steps, with most of them in the same direction!

The results here show how probability (chance) is a key part of this question.  We've not given Isaac any sense of direction at all, and he's at the mercy of probability.  As a result, mathematically, all we can aim for is an approximate, or an average distance that Newton can travel.  Unfortunately for him, the mathematical average of his wanderings is going to be close to zero - for every step he takes to the left, he has an equal chance of taking a step to the right.

Doing it the pure maths way involves probability.  There's a 50% chance that Newton will go to the left (let's call this a step of -1) and a 50% chance he'll go to the right (this is a step of +1).  Let's start him at zero, and assume that he has to reach either +10 (his home) or -10 (his aunt's home).

After his first step, he has a 50% chance of moving even closer to his target, and a 50% chance of returning to his starting position.  So the probability of him making two consecutive steps towards either target is (0.5 x 0.5) x 2 since he has two targets to aim for (one at each end of the street), which is 0.5 - in fact, after two steps, Isaac has either moved two steps towards one target (+1, +1 = +2 or -1, -1 = -2) or moved back to his start position (+1, -1  =0 or -1, +1 = 0).

However, the maths becomes considerably more complex after three steps, and more complicated still if we need Isaac to achieve ten steps in one direction or the other.  I won't do the maths here, but after a large number of steps, it becomes clear that the most probable location after a large number of steps is close to the start point, as mentioned above.  On average, the number of steps in one direction will be balanced by an equal or similar number of steps in the other.  This is known among mathematicians as the random walk problem, and Wikipedia has plenty to say on it (no surprises there).

The question becomes not "When will Mr Newton reach his destination?" but "How likely is he to have reached his destination after 10 or 20 or 30 or 40... steps?" and that's far more complicated than I'd like to cover here - it's why I prefer science to maths!

No comments:

Post a Comment