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 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
The ideal random walk model we that we have just presented has a surprising number of applications almost ``as is'':
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 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:
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.
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.