Lecture 5: January 26

Random Walks

The Gaussian (or normal error) distribution, is very important because of the Central Limit Theorem - see Problem 12.9 on page 384 in Chapter 12. The theorem states that the averages of sufficiently large numbers of independently chosen random variables is Gaussian distributed, regardless of the shape of the underlying distribution!

The random walk provides an example of this important theorem. A single walk step belongs to a distribution with just two values, "forward" or "backward", with equal probabilities, just like tossing a coin. How can this distribution be related to the Gaussian distribution, which ranges over all real numbers? The key is to take the limit of a very large number of independent steps. For example, the position of the walker after two independent steps can range over 5 values (-2, 0, +2) assuming unit step size; after three steps, the walker can be at positions (-3, -1, +1, +3); and so on. So the average distance traveled after N steps can be arbitrarily close to any real number in the interval [-1, +1] when N becomes very large.

The Central Limit Theorem applied to this example says:

• Choose a large N.

• Perform a large number M of walks (trials or experiments) each with N steps and measure the average displacement <x>.

• A histogram of these M measured values will be approximately Gaussian

2-D Random Walk - Java Graphics

This program provides a simple example of using the comphys.graphics package to program animations. A typical skeleton animation program is:

import comphys.graphics.*;

public class TwoDimWalk extends Animation {

    void initial () {
        // physics model initialization code
    }

    void takeStep () {
        // generate data for next animation frame
    }

    class Movie extends Plot {     // inner class for picture or plot
        Movie () {
            setSize(400, 400);     // size in pixel units
            setBackground("white");
        }

        public void paint () {
            if (needToClear) {
                clear();
                double L = Math.sqrt(2 * N);
                setWindow(-L, L, -L, L);
            }
            setColor("green");
            plotLine(xPrevious, yPrevious, xWalker, yWalker);

            // overlay frame-specific graphics
            plotOverlay();
            setColor("red");
            floodCircle(xWalker - 0.5, xWalker + 0.5,
                        yWalker - 0.5, yWalker + 0.5);
        }
    }

    Movie movie;
    Reader NReader;

    public void init () {
        initial();
        add(movie = new Movie());
        add(NReader = new Reader("Steps N =", N));
        addControlPanel();
    }

    public void step () {
        takeStep();
        movie.repaint();
    }

    public void reset () {
        N = NReader.readInt();
        initial();
        needToClear = true;
        movie.repaint();
    }

    public static void main (String[] args) {
        TwoDimWalk tdw = new TwoDimWalk();
        tdw.frame("Random Walk in Two Dimensions", 430, 550);
    }
}