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.