The best thing about pi is finding it in places you don't expect---like, say, a random walk. What is a random walk? Excellent question! Let me show you.
Start at some location. The simplest location to start with is at the origin so x = 0 meters. Now flip a coin. Heads? Great. Move one meter to the right. Tails? One meter to the left. Repeat as often as you like. Congratulations. You've completed a random walk in one dimension. Normally I would draw a diagram to explain this, but instead I'll make a random walk in python. Click play to start and the pencil to see the code.
Examining the code might help you see what's going on. But this is basically how it works:
- Get a random number between 0 and 1.
- If the number is less that 0.5, move in the positive x-direction.
- If the number is greater than 0.5, move in the negative x-direction.
- Repeat until you want to stop.
But I don't want to make one random walk. I want to run it a whole bunch of times and see what happens. Let me start by taking 100 random steps. Of course, if I run it once, I could end up anywhere between -100 and +100. But if I do this 100-step walk 1000 times, I can determine where I end up on average. This histogram shows 1000 random walks of 100 steps in one dimension:
I could find the average of these values, but why bother? It seems clear that the average ending position is back at the origin. That makes sense. If I am equally as likely to go left or right after many steps, I am very likely to have just as many left steps as right steps and end back where I started.
How about a plot of the total distance from the origin to the end of the walk? This is a plot of the absolute value of the final x-position---this is same as the total distance from start to finish of the walk.
Yes, it looks crazy. In fact, the average final distance (not position) for this run is 7.848 and not zero. But it's not crazy. If you look at the first histogram showing the final x-position, yes, the highest occurring final position was x = 0. But if you look at the number of x = -1 and x = +1, they outnumber x = 0 and you have only positive values. These two things give a non-zero average distance.
OK, I've kept you waiting long enough. Today is Pi Day and you came looking for pi, so I will give you some pi because I always write about pi on Pi Day. Of course you've realized that the average distance for a random walk depends on the number of steps. That makes sense, right? But it turns out the average distance also depends on pi. Here is the relationship (please don't ask me to derive this):
In this expression, n is the number of steps. From this, I can use the random walk to find a value for pi. Here's the plan: Run the random walk for 10 steps (do it 1000 times to get an average). Repeat for 20 steps, 30 steps, and so on. If you plot the average distance squared versus the number of steps, you should get a straight line with a slope equal to 2/pi:
Here the slope is 0.631. If I set this equal to 2 over pi the pi would be 3.1696. Not exactly pi (3.1415...), but close enough for me. It's conceivable that you could make a plot that yields a better estimation of pi. You might change the number of runs to do that. When the program gets to higher steps (like near 1000) I probably ought to run more than 1000 runs because it's very possible to get much higher deviations from the expected value. Oh, well---that's something you can try. Here is an online version of this calculation in case you want to play with it.
I might be obsessed with random walks. Someone send help before I lose control. In the meantime, I might as well make a 2-D random walk. It's just like the 1-D walk except I can take each step in one of four directions---+x, -x, +y, -y. Yes, this is still a discrete random walk (a lattice random walk) such that each step has a size of 1 unit and I am always at a coordinate location with integer values.
Here is my visual 2-D random walk with 100 steps, but you can change that in the code if you like.
To help with the visualization, I change the color and size of both spheres that represent the start and finish of the walk. I find it fun to watch. OK, now for some useful stuff. Let's say that I take 100 random steps and I repeat this 1000 times. What is the average ending distance from the starting point? Here is a histogram:
This gives an average distance of 8.820 units. Perhaps this isn't terribly useful. But as with 1-D, you see a relationship between the average distance and the number of steps:
Once again, I can plot the average distance squared vs. the number of steps. In this case, the slope will be pi divided by 4:
From the slope of this data, I get a value of pi at 3.136. Not too bad. It isn't the best way to find pi, but it's still fun.
I promise this will be the last random walk, at least in this post. This walk also is in 2-D, but with a difference. Instead of moving in the x or y direction, this one takes a step size of one at a random angle. This means the moving ball doesn't have to end up with an integer value for the final coordinate.
Does this matter for the distance traveled? Here is same plot of distance squared vs. number of steps:
Looks like it still works. Yay for pi, the hidden ninja of the physical world. It keeps popping up in places you wouldn't expect.
You didn't think you'd escape Pi Day without some homework, did you?
- See if you can get a better plot of distance squared vs. step number. Make one that doesn't get so noisy for high steps.
- See what happens if you create a 2.D walk where the direction and size of each step is random. I concede that this is tougher because you can't use a flat random number (uniform random number distribution) unless you determine the range of step sizes. You could do that and let the step be from 0 to 1. Another option is to use another distribution for the step size, like a gaussian distribution.
- Try using a 3-D lattice random walk to find pi. There is a small trick to this: You must find the relationship between distance and number of steps in 3D. Use this site to get the equation.
