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.