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.