Let me now remind you what we are going to cover next.
First I'll demonstrate that the root mean square displacement of a random walk
scales as the square root of time. The central result - the basic central result
in the theory of random walks.
Next I'll show that two dimensions is special. In two dimensions and below
a lattice random walk is recurrent, namely it is sure to return to its
starting point, whereas for dimensions greater than two, the random walk is
transient, in that its return to its starting point is uncertain.
Next I'll present the probability distribution of the random walk and show
how to derive the underlying diffusion equation.
Next I'll discuss the fundamental central limit theorem in which the probability
distribution of a random walk is a Gaussian under some very mild
restrictions.
Finally, I'll present some simple first passage properties of random walks and
give some elementary examples.
As a first step in understanding the properties of the random walk, let's
compute how far a random walk goes as a function of the number of steps in the
walk. This is encapsulated by a quantity known as the root mean square
displacement and because the root mean square appears so often, we usually label
it with the index rms, so X rms will be the root mean square displacement
of a random walk.
So let's - the simplest situation to consider is the Pearson random walk
in which we take steps of fixed length but random direction.
So here each step has length a and the angle between each step theta is random.
So mathematically we can describe the properties of the Pearson random
walk as that the mean value of each single step is equal to a, so fixed step length.
Also, there is no bias in the walk, and so the average value of each individual
displacement x sub i is equal to 0. So angle bracket is meant to denote average
over all possible realizations of the walk - over all possible realizations of a
single step. So this is the statement that there is no bias and furthermore,
because this steps are uncorrelated, that means that the dot product of x i with x j
for any i not equal to j is equal to 0. So this is the mathematical statement that
there is no correlation between steps. Successive steps or steps further down
the road. So with these assumptions, let's now calculate the mean displacement
of a walk after N steps and the root mean square displacement. So the mean
displacement, so I'll denote that by capital X sub N is just the sum of the
individual displacements, so sum from i equals 1 to N of the little x i and we
take the average value. But by construction, each x i has an average
value 0, so we are summing a whole bunch of values that equal 0, and so we get
nothing.
Let's now look at the root - at the mean square displacement, so we're going to
ask for X N, square it and then take the average. And so what is this quantity?
So again we have to take the sum of the displacements x i, i equals 1 to N, square
it and then take the average value. So when we square this sum, this binomial,
there are two types of terms. There are called diagonal terms where we have
x i dotted into x i and so there will be terms that look like this - summation
i equals 1 to N of x i squared and then there are all the cross terms where we
sum over all possible combinations i not equal to j of x i dot x j and then we have
to take the average value of all of this. So by construction, these cross terms are
all 0 because there was no correlations between successive steps, so we just
forget about this. The diagonal terms, they're all identical, they're the
squared length of each individual step - there's N such terms and so this is
nothing more than N a squared. So this quantity X N squared is known as the mean
squared displacement and the square root of the mean square displacement is
precisely the root mean square displacement X rms, so X rms, which is
defined to be the square root of the mean square displacement X N squared average
value, this is equal to the square root of N a. So this is our first fundamental
result about random walks, which is that the rms displacement grows not linearly
in the number of steps, but only as the square root of the number of steps.
So random walk is actually not very efficient at exploring space. The other
point to emphasize here is that there is the factor a which makes this equation
dimensionally correct because on the left hand side we have the units of length and
on the right hand we have the units of length and the scaling factor in front is
the square root of N. This is one of the fundamental results in the theory of
random walks.