Brownian motion

Introduction
Problem set 1
Sums of random variables
Problem set 2
References

Introduction

Brownian motion is the observed movement of small particles as they are randomly bombarded by the molecules of the surrounding medium. This was first observed by the biologist Robert Brown and was eventually explained by Albert Einstein, for which work he received the Nobel prize.

We can simulate Brownian motion in one dimension by tossing coins. If the sequence of tosses is

  1  1  0  1  1  1  0  0  1  0
  0  0  1  0  1  0  0  1  0  1

then we can move are particle one unit to the right each time we see a 1, and on unit to the left each time we see a 0. This results in the new sequence

  1  2  1  2  3  4  3  2  3  2
  1  0  1  0  1  0 -1  0 -1  0

We haven't dispalyed the starting position (0). We can also display this graphically:

         *
        * * *
    *  *   * *
  *   *       * * *
  -------------*-*-*-*-*---  x = 0
                    * *

We can simulate Brownian motion using the computer if we have a good generator of uniformly distributed random numbers. This is what the program uni.c does. To copy uni.c to your directory, do this

  % cp /u/cl/doc/ma217/uni.c .
  % ls uni.c
  % uni.c

We copied uni.c from the directory /u/cl/doc/ma217. Note the period (.) in the copy (cp) command. It stands for your current directory. Now type the program r1.c. Finally, compile it like this:

  % gcc r1.c uni.c

This compiles both your program and uni.c. The two compiled files are then linked together, and you can run them using

  % a.out

Recall that a.out is the default name of a compiled C program. You should get this output:

    1:  0.775535
    2:  0.847905
    3:  0.297409
    4:  0.017542
    5:  0.121674
    6:  0.527103
    7:  0.889287
    8:  0.182352
    9:  0.387452
   10:  0.564470

Once you have a good way of producing uniformly distributed random numbers in the range [0,1], you can compute other sequences of random numbers. For example, to get a uniformly distributed sequence of zeros and ones, use the rule:

  if u < 1/2
    then v = 0
    else v = 1

where u is a random variable uniformly distributed in the range [0,1]. To get a sequence of uniformly distributed numbers in the range [-1,+1], set

   v = 2u - 1

Problem set 1

Modify r1.c so that you can enter the seed value and the number of random numbers to be printed. You may want to change the output format. Recall that the seed is a long, so you need code like this: scanf("%ld", &iseed).
Test the random number generator uni.c using five "bins" --- five equal intervals which partition the unit interval. You should use your own random seed (perhaps more than once).
Devise a program which simulates random walk in one dimension. Do this by setting x = 0, then repeatedly adding uniformly distributed random numbers in the range [-1,1] to x. Random walk models the motion of a small particle in a thin tube of water. It is repeatedly hit, but at random, by the water molecules surrounding it. As your first application of this program, find the distance moved from the origin by the particle in 100 steps.
Continuation. Let our particle perform a 10-step random walk 100 times. For each of these "experiments &quot, let Y denote the signed distance from the origin at the end of 100 steps. Make a frequency histogram for Y and find the average value of Y. Is your average value a good approximation of what the expected value is?
Redo the previous problem for 100-step random walks. Study the relative shape of the frequency histograms.
Continuation. For several of the 100-step random walks make graphs of x versus time. Interpret these in the context of the gambler's ruin problem.

Sums of random variables

Problems 4 and 5 of the last problem set dealt with random variables that are themselves sums of random variables:

  Y = X_1 + X_2 + ... + X_N

Here the X_i are independent and have identical probability distributions. The central limit theorem, which we have mentioned before, says that as N gets larger and larger, the probability distribution of Y becomes closer and closer to a fixed distribution, the normal distribution. Its general shape is that of a bell curve, with the center of the bell at

  Y =  E(Y) = N E(X)

This bell can be a narrow one or a broad one. About 68% of the area under the bell lies above the interval

  [ E(Y) - SD(Y), E(Y) + SD(Y) ]

where

  SD(Y) = sqrt(N) SD(X)

is the standard deviation. Let us call this the core of the bell. Note that about 95% of the area under the bell lies above the two standard deviation interval.

Problem Set 2

In the histograms of the previous problem set, find the area of the core and compare it to its expected value.
Find the histogram for a random walk of 100 steps, repeated 1000 times. You will want to set up an array to hold the statistics and have your program compute them. Graph the results and compare them with what theory predicts.
Brownian motion explains processes as diverse as diffusion of a salt in water and conduction of heat. Image that a lump of salt is placed in the center of a long thin tube. Individual salt ions dissolve and are subject to brownian motion. The random walks of distinct ions are independent. Consequently, if we record the final positions of 1000 ions which "walk " 100 steps, we get the same kind of results as when repeatedly make a single ion walk from the origin. Thus the core in our simulation represents the densest part of region of salty water.
Suppose that after one second the core is one millimeter wide. How wide will it be afer 100 seconds? How wide will it be after 10,000 seconds (almost three hours later). If the concentration is 10 units at one second, what will it be at 100 seconds and at 10,000 seconds?

Make a sketch of the width of the core as a function of time.

Conclude by make a brief, labeled sketch of the diffusion process we have studied. Feature bell-shaped blobs getting wider and shorter, and explain what is going on.
(Optional) Learn the story of Gauss's role in discovering the normal distribution. Hint: it has to do with astronomy. You might also want to learn more about the normal distribution itself.

References

David Freedman, Robert Pisani, and Roger Purves, Statistics, W. W. Norton (1978).
The authors strive to develop statistical intution with as little mathematics as possible.
Sheldon Ross, A First Course in Probability, Macmillan (1976).