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

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
*n*_{r } steps to the right and *n _{l}*
steps to the left;

Lets call * P _{N }(x) *, the probability that after N steps the
walker has a total displacement

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

- diffusion of molecules in a dilute gas -
*l*is the distance between collisions with other molecules. Assume statistical independence of displacements between collisions. - the path of the random walker makes a good model for a dilute solution of polymers.
- 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.

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

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

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 R_{N }, 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 *x _{0}
x_{1},x_{2},x_{3}.....
x_{n}*, where

*x _{n}=(ax_{n-1}+c)*mod

where * a,c,m * are integers.
If *a=3, c=4, m=32, x _{0}=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

We must check random numbers in many ways.

- First we ask is the mean in the middle of the range, i.e. is it 0.5 for [0,1] numbers?
- We can graph the path of the random walk made by the numbers. This can be done using rwalk2.f ,

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, x _{0}*.
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.