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.