1
00:00:13,110 --> 00:00:15,222
A more fundamental way to characterize a
2
00:00:15,222 --> 00:00:18,532
random walk is by its probability distribution,
3
00:00:18,534 --> 00:00:21,444
namely the probability that a random walk
4
00:00:21,444 --> 00:00:24,784
is at position x at time t. We will call this
5
00:00:24,784 --> 00:00:28,604
fundamental probability distribution 'p(x,t)'.
6
00:00:28,604 --> 00:00:31,344
What I want to do now is calculate this distribution
7
00:00:31,344 --> 00:00:35,094
for discrete space, discrete time, one-dimensional
8
00:00:35,094 --> 00:00:38,394
random walk. Let's imagine a random walk that
9
00:00:38,394 --> 00:00:43,374
lives in one dimension with discrete sites like
10
00:00:43,374 --> 00:00:54,781
this and so here is position x-2, x-1, x+1, and x+2.
11
00:00:54,781 --> 00:00:57,651
And let's suppose that a random walk hops
12
00:00:57,651 --> 00:01:00,521
to nearest neighbors equally probably to the left
13
00:01:00,521 --> 00:01:04,381
and to the right. So that from x one hops with probability
14
00:01:04,381 --> 00:01:07,781
one-half to the right and probability one-half
15
00:01:07,781 --> 00:01:10,831
to the left. And similarly from x+1, you can
16
00:01:10,831 --> 00:01:13,941
hop to x+2 with a probability of one-half or to
17
00:01:13,941 --> 00:01:16,621
the left with a probability of one-half, and the same
18
00:01:16,621 --> 00:01:20,371
for every other sight of the lattice. With this picture,
19
00:01:20,371 --> 00:01:24,211
let me now compute the probability distribution for
20
00:01:24,211 --> 00:01:28,701
this random walk. This probability distribution is
21
00:01:28,701 --> 00:01:33,301
calculated by something known as a master equation
22
00:01:33,301 --> 00:01:36,581
which describes how this probability distribution evolves
23
00:01:36,581 --> 00:01:41,061
in time. So how can we be at position x at time t? There
24
00:01:41,061 --> 00:01:44,301
are only two ways this can occur. Either the random
25
00:01:44,301 --> 00:01:48,111
walk was at x-1 and it hopped to the right with a
26
00:01:48,111 --> 00:01:51,591
probability of one-half and it was at x-1 at the previous
27
00:01:51,591 --> 00:01:57,051
time, so there will be one-half p, x-1 one-step to the
28
00:01:57,051 --> 00:01:59,711
left at the previous time and the factor of
29
00:01:59,711 --> 00:02:03,241
one-half accounts for that it hops to the right
30
00:02:03,241 --> 00:02:06,351
with probability one-half. Or the random walker
31
00:02:06,351 --> 00:02:10,371
was at position x+1 at the previous time step
32
00:02:10,371 --> 00:02:13,721
and hopped to the left. So this object is called
33
00:02:13,721 --> 00:02:16,381
the master equation and it describes how the
34
00:02:16,381 --> 00:02:19,461
probability distribution evolves in time. Now
35
00:02:19,461 --> 00:02:22,991
it turns out a little bit simpler than calculating
36
00:02:22,991 --> 00:02:28,921
p(x,t) to look at p(r,t), the probability that in time
37
00:02:28,921 --> 00:02:33,401
t, I take r-steps to the right. So here little r is
38
00:02:33,401 --> 00:02:38,471
the number of steps to the right and let me
39
00:02:38,471 --> 00:02:42,171
define little l as the number of steps to the left.
40
00:02:45,963 --> 00:02:49,263
And then r+l, the sum of the number of steps to
41
00:02:49,263 --> 00:02:52,503
the right and to the left, is the total time t. And r-l is
42
00:02:52,503 --> 00:02:54,613
the difference in the number of steps to the right
43
00:02:54,613 --> 00:02:57,683
and to the left and is equal to x. So once we
44
00:02:57,683 --> 00:03:00,673
compute p(r,t), we will then be able to reconstruct
45
00:03:00,673 --> 00:03:05,293
p(x,t). So what is p(r,t)? So in principle, one can
46
00:03:05,293 --> 00:03:07,913
solve the master equation directly, but here I'm
47
00:03:07,913 --> 00:03:11,173
just going to argue probabilisticly that I just have
48
00:03:11,173 --> 00:03:14,983
to count the total number of walks that take a total of r-
49
00:03:14,983 --> 00:03:18,013
steps to the right. So the the total number of walks
50
00:03:18,013 --> 00:03:22,983
of any size, of any orientation, is just t-factorial,
51
00:03:22,983 --> 00:03:26,573
because I can take the steps in any order. So there's
52
00:03:26,573 --> 00:03:30,483
an overall factor, t-factorial. However, if I want to
53
00:03:30,483 --> 00:03:33,413
constrain my walk to take r-steps to the right,
54
00:03:33,413 --> 00:03:37,313
that means that of these t-factorial arrangements
55
00:03:37,313 --> 00:03:41,043
of the steps, r of them have to be to the right and l of
56
00:03:41,043 --> 00:03:44,103
them have to be to the left. So the number of distinct
57
00:03:44,103 --> 00:03:47,173
ways of doing this, we have to divide t-factorial by
58
00:03:47,173 --> 00:03:50,623
r-factorial because all right steps, we can take them in
59
00:03:50,623 --> 00:03:53,493
any order and we'll end up at the same place. And
60
00:03:53,493 --> 00:03:57,173
similarly for the left steps. And then we have one-half
61
00:03:57,173 --> 00:04:00,173
to the power t because each step occurs with
62
00:04:00,173 --> 00:04:03,665
a probability one-half. So this quantity is
63
00:04:03,665 --> 00:04:06,345
precisely the probability that a random walker takes
64
00:04:06,345 --> 00:04:12,125
r-steps to the right in a total of t steps. But now
65
00:04:12,125 --> 00:04:16,435
using this relation between r, l, and t, and x, we can
66
00:04:16,435 --> 00:04:20,765
compute r is equal to (t+x)/2 and similarly
67
00:04:20,765 --> 00:04:26,265
l is equal to (t-x)/2. So therefore we have our
68
00:04:26,265 --> 00:04:29,065
fundamental result that p(x,t) is equal to
69
00:04:29,065 --> 00:04:37,085
t-factorial divided by t plus x over two factorial, t minus
70
00:04:37,085 --> 00:04:43,615
x over two factorial, one-half to the power t. Now,
71
00:04:43,615 --> 00:04:47,155
in this discrete form, it's actually not very convenient
72
00:04:47,155 --> 00:04:49,575
to do any manipulations because it's discrete
73
00:04:49,575 --> 00:04:52,695
and we can't use the power of calculus. And so,
74
00:04:52,695 --> 00:04:57,445
in general, one wants to find this probability distribution
75
00:04:57,445 --> 00:05:01,095
in the limit of t going to infinity. And in this long
76
00:05:01,095 --> 00:05:04,095
time limit, we can use Stirling's approximation to
77
00:05:04,095 --> 00:05:07,725
reduce the factorials to analytic functions, so let
78
00:05:07,725 --> 00:05:12,695
me just write Stirling's approximation. And, the
79
00:05:12,695 --> 00:05:16,912
result is, that one finds after some algebra, 2 over
80
00:05:16,912 --> 00:05:21,362
square root of pi t, e to the minus 2 x squared over t.
81
00:05:23,304 --> 00:05:26,604
So this quantity is known as the Guassian probability
82
00:05:26,604 --> 00:05:29,444
distribution and as we are going to learn, it is a
83
00:05:29,444 --> 00:05:33,554
relatively universal feature of random walks.
84
00:05:35,922 --> 00:05:39,102
Now I've glossed-over going from the discrete to
85
00:05:39,102 --> 00:05:43,482
the continuum because this formulation of a discrete
86
00:05:43,482 --> 00:05:46,642
time, discrete space, random walk...even though it's
87
00:05:46,642 --> 00:05:49,751
conceptually elementary, it's analytically kind of
88
00:05:49,751 --> 00:05:54,081
clunky, and so I'm going arrive at the Guassian
89
00:05:54,081 --> 00:05:56,541
probability distribution in a more elegant fashion
90
00:05:56,541 --> 00:05:58,941
by treating this problem in the continuum limit.
91
00:05:58,941 --> 00:06:02,251
So this will be the subject of the next slide.
92
00:06:04,625 --> 00:06:06,591
After this lecture was completed, somebody
93
00:06:06,591 --> 00:06:08,861
pointed out that I made a stupid mistake in the
94
00:06:08,861 --> 00:06:12,421
final result. So, in using Stirling's approximation
95
00:06:12,421 --> 00:06:16,231
to go from the factorial expression for the probability
96
00:06:16,231 --> 00:06:18,821
distribution to the Guassian, the 2 doesn't belong
97
00:06:18,821 --> 00:06:20,981
in the numerator, it belongs in the denominator.
98
00:06:20,981 --> 00:06:23,381
Sorry about that.