A more fundamental way to characterize a

random walk is by its probability distribution,

namely the probability that a random walk

is at position x at time t. We will call this

fundamental probability distribution 'p(x,t)'.

What I want to do now is calculate this distribution

for discrete space, discrete time, one-dimensional

random walk. Let's imagine a random walk that

lives in one dimension with discrete sites like

this and so here is position x-2, x-1, x+1, and x+2.

And let's suppose that a random walk hops

to nearest neighbors equally probably to the left

and to the right. So that from x one hops with probability

one-half to the right and probability one-half

to the left. And similarly from x+1, you can

hop to x+2 with a probability of one-half or to

the left with a probability of one-half, and the same

for every other sight of the lattice. With this picture,

let me now compute the probability distribution for

this random walk. This probability distribution is

calculated by something known as a master equation

which describes how this probability distribution evolves

in time. So how can we be at position x at time t? There

are only two ways this can occur. Either the random

walk was at x-1 and it hopped to the right with a

probability of one-half and it was at x-1 at the previous

time, so there will be one-half p, x-1 one-step to the

left at the previous time and the factor of

one-half accounts for that it hops to the right

with probability one-half. Or the random walker

was at position x+1 at the previous time step

and hopped to the left. So this object is called

the master equation and it describes how the

probability distribution evolves in time. Now

it turns out a little bit simpler than calculating

p(x,t) to look at p(r,t), the probability that in time

t, I take r-steps to the right. So here little r is

the number of steps to the right and let me

define little l as the number of steps to the left.

And then r+l, the sum of the number of steps to

the right and to the left, is the total time t. And r-l is

the difference in the number of steps to the right

and to the left and is equal to x. So once we

compute p(r,t), we will then be able to reconstruct

p(x,t). So what is p(r,t)? So in principle, one can

solve the master equation directly, but here I'm

just going to argue probabilisticly that I just have

to count the total number of walks that take a total of r-

steps to the right. So the the total number of walks

of any size, of any orientation, is just t-factorial,

because I can take the steps in any order. So there's

an overall factor, t-factorial. However, if I want to

constrain my walk to take r-steps to the right,

that means that of these t-factorial arrangements

of the steps, r of them have to be to the right and l of

them have to be to the left. So the number of distinct

ways of doing this, we have to divide t-factorial by

r-factorial because all right steps, we can take them in

any order and we'll end up at the same place. And

similarly for the left steps. And then we have one-half

to the power t because each step occurs with

a probability one-half. So this quantity is

precisely the probability that a random walker takes

r-steps to the right in a total of t steps. But now

using this relation between r, l, and t, and x, we can

compute r is equal to (t+x)/2 and similarly

l is equal to (t-x)/2. So therefore we have our

fundamental result that p(x,t) is equal to

t-factorial divided by t plus x over two factorial, t minus

x over two factorial, one-half to the power t. Now,

in this discrete form, it's actually not very convenient

to do any manipulations because it's discrete

and we can't use the power of calculus. And so,

in general, one wants to find this probability distribution

in the limit of t going to infinity. And in this long

time limit, we can use Stirling's approximation to

reduce the factorials to analytic functions, so let

me just write Stirling's approximation. And, the

result is, that one finds after some algebra, 2 over

square root of pi t, e to the minus 2 x squared over t.

So this quantity is known as the Guassian probability

distribution and as we are going to learn, it is a

relatively universal feature of random walks.

Now I've glossed-over going from the discrete to

the continuum because this formulation of a discrete

time, discrete space, random walk...even though it's

conceptually elementary, it's analytically kind of

clunky, and so I'm going arrive at the Guassian

probability distribution in a more elegant fashion

by treating this problem in the continuum limit.

So this will be the subject of the next slide.

After this lecture was completed, somebody

pointed out that I made a stupid mistake in the

final result. So, in using Stirling's approximation

to go from the factorial expression for the probability

distribution to the Guassian, the 2 doesn't belong

in the numerator, it belongs in the denominator.

Sorry about that.