what


Random walks

what


Someone drank too much wine on seder night and is having trouble walking home. He sees a lampost and wishes to reach it so he can hold on to it, but is not very well coordinated and so takes a random walk around it.

Let us consider a one dimensional version of his/her walk on the positive and negative x axis, making each step of length l.

what

The step length l is a unit step on the axis. At each point the drunkard can step to the right with probability p and to the left with probability q=1-p. He takes nr steps to the right and nl steps to the left; N, his total number of steps being N=nr + nl . His total displacement, x , after N steps is (nr -nl)l .

Lets call PN (x) , the probability that after N steps the walker has a total displacement x . Then his/her mean nett displacement is

what

with a variance of:

what

It is easy to obtain the following two analytic results for general p and q as well as the last one for the special symmetric case:

what


The ideal random walk model we that we have just presented has a surprising number of applications almost ``as is'':

  1. diffusion of molecules in a dilute gas - l is the distance between collisions with other molecules. Assume statistical independence of displacements between collisions.
  2. the path of the random walker makes a good model for a dilute solution of polymers.
  3. particles diffusing within solids make random walks between the atoms.

However many applications require substantial modification of the conditions.


The ideal random walk can be solved analytically, but once realistic complications are included (for example in an ideal random walk a walker can cross his path, but in a polymer two atoms cannot occupy the same physical space - this becomes serious as the solution gets denser) analytic solution becomes difficult if not impossible. We will therefore discuss the numerical modelling of random walks, using the ideal one as our example, but with a view to application to realistic cases.

Two computational methods are commonly used: enumeration and simulation. enumeration is suited to small systems and simulation to larger ones. Let us develop a method of exact enumeration, starting at the origin, to calculate the P N (x) , by drawing the steps and calculating the probabilities.

what

There is a factor of two on the N=2 returns to the origin because as shown, the steps can be taken in two different orders (left then right or right then left. Both are drawn.) There is a factor of 3 in the walks to each of x=1, x=-1 because the steps can be taken in 3 different orders although this is not drawn explicitly on the web page. (Draw these yourself for practice if you have any difficulty understanding the counting.)

The mean values are

what

where the trick is to recall that p+q=1 . In question 1 of the second targil, you are asked to extend these ideas by writing a computer program that enumerates the number of walks NW (x,N) that reach the point x in N steps, for some larger values of N. To understand this notation, think about NW (-4,4) . There is just one of these, resulting from 4 steps to the left with probability q 4 . The other NW quantities are more complicated, but can be broken down into iterative parts.

To develop recursion relations let us first consider the expression NW(0,4)=NW(+/-1,3). It follows from the fact that to be at x=0 after 4 steps, the walker must be at either x=1 or x=-1 after three steps. We calculated this above and saw that there are three ways to be at x=1 and and three to be at x=-1 after three steps, six in total. For each of these another step can take us back to the origin hence the equality.

Another useful relation is NW(+/-2,4) = NW(+/-1,3) + NW(+/-3,3). In order to be at x=2 or x=-2 after four steps the walker must be either at x=3 or x=1 in the former case or at x=-3, or x=-1 in the latter after three steps.

Let us consider some more applications and extensions of random walks. We have so far only discussed one dimension, but the problem can be formulated in two and higher dimensions, on for example square or triangular or more complicated lattices. The steps do not have to be uniform in length, and the choice of next direction may not be random, but could be biased towards persistence in the same direction. Some specific examples are: Polyethylene, which is a polymer made up of CH 2 momomers where each monomer is a step of a random walk. A solution of sphaghetti in a sauce is just a polymer in a good solvent. Some measurments that we make make on these chains include the rms end-to-end distance, or RN , the maximum displacement at step N, which behaves like aN to the power nu at step N. nu is a critical exponent, and there is a beautiful formalism connecting some random walk models to other models with phase transitions at which critical exponents are defined such as Ising models to which we will return much later. We conclude this subsection with an example from a recent calculation by D. Saada on the diffusion of Hydrogen in Carbon.

The following material forms the basis for question 2 of the second targil.

When the number of walks becomes large, explicit enumeration is not always possible so we simulate. When simulating it is important to be able to visualize results to understand what we are doing. A useful program for simulating random walks is rwalk1.f using cplot.f to graph the results. These programs are on this http site .

The basic idea in simulation of random walks is that in order to choose the next step, which will go to the right with probability p we select a uniform [0,1] random number, and if it is less than p then the next step is to the right and if greater than p to the left.

Thus, to simulate random walks we need to learn about random numbers, keeping in mind that the selection of these numbers in the computers is itself a random walk although not with uniform step size. The best random numbers come from physical processes like radiactive decay, but using these is a little inconvenient. The ones in a computer are technically pseudorandom. There is a sequence which repeats after some period of time. Lets call the sequence x0 x1,x2,x3..... xn, where x0 is the seed. A common method is `linear congruential' for example:

xn=(axn-1+c)mod m

where a,c,m are integers. If a=3, c=4, m=32, x0=1 then the series is 1,7,25,15,17,23,9,31,1,7,5 ..... with a period of 8, not very random. The maximum here should be 32 so this is a particularly pathetic set of numbers.

It is usual to use uniform [0,1] random numbers, and for the linear congruentials transforming x n+1 to x n+1/m does this. A simple computer routine called urand.f calculates random numbers that are GOOD for demonstrations, NOT for research.

We must check random numbers in many ways.

  1. First we ask is the mean in the middle of the range, i.e. is it 0.5 for [0,1] numbers?
  2. We can graph the path of the random walk made by the numbers. This can be done using rwalk2.f ,
Practical implementation of rwalk2.f and cplot.f on aluf/t2, phelafel and phclasses is as follows:
If the files not already present, download the files, then compile rwalk2.f with gfortran rwalk2.f -o rwalk2.ex
(on some older computers, replace gfortran with f77)
and run it with rwalk2.ex
It will make a datafile called fort.8 on aluf/t2 and possibly something else on other machines.
Then compile cplot.f with
pgplotcl cplot
Run it by writing cplot
answering the data file as fort.8 and then answering /xwindow
If the graphics does not work check if you wrote -X, try to see if the command xterm &
gives a new window and if not go to the commands page and follow the instructions in the item about PGPLOT. or call me for help if we are both in the classroom.

Now you are ready to input different a, c, m, x0. We can observe any obvious periodicities. Some interesting sets to try are (899, 0, 32768, 12), (1, 2, 1000, ?), (106, 1283, 6075, ?), (899, 0, 32768, 12345). See graphs of some of these and try them yourself.

If we require random numbers according to a distribution that is not uniform [0,1] we can transform the uniform ones to the desired distribution. We will return to random numbers later in the course; for now the simple generator is adequate.

Back to the Lecture 2 page, where some more details about PGPLOT are also given.
Back to the Lecture 3 page.