1
00:00:09,118 --> 00:00:12,138
Let me now remind you what we are going to
cover next.
2
00:00:12,608 --> 00:00:16,591
First I'll demonstrate that the root mean
square displacement of a random walk
3
00:00:16,591 --> 00:00:21,550
scales as the square root of time. The
central result - the basic central result
4
00:00:21,550 --> 00:00:23,532
in the theory of random walks.
5
00:00:23,784 --> 00:00:28,110
Next I'll show that two dimensions is
special. In two dimensions and below
6
00:00:28,110 --> 00:00:32,313
a lattice random walk is recurrent,
namely it is sure to return to its
7
00:00:32,313 --> 00:00:37,333
starting point, whereas for dimensions
greater than two, the random walk is
8
00:00:37,333 --> 00:00:41,914
transient, in that its return to its
starting point is uncertain.
9
00:00:42,882 --> 00:00:46,407
Next I'll present the probability
distribution of the random walk and show
10
00:00:46,407 --> 00:00:49,324
how to derive the underlying diffusion
equation.
11
00:00:50,018 --> 00:00:55,038
Next I'll discuss the fundamental central
limit theorem in which the probability
12
00:00:55,038 --> 00:00:59,146
distribution of a random walk is a
Gaussian under some very mild
13
00:00:59,146 --> 00:01:00,233
restrictions.
14
00:01:00,233 --> 00:01:04,633
Finally, I'll present some simple first
passage properties of random walks and
15
00:01:04,633 --> 00:01:06,935
give some elementary examples.
16
00:01:09,275 --> 00:01:13,190
As a first step in understanding the
properties of the random walk, let's
17
00:01:13,190 --> 00:01:17,851
compute how far a random walk goes as a
function of the number of steps in the
18
00:01:17,851 --> 00:01:23,095
walk. This is encapsulated by a quantity
known as the root mean square
19
00:01:23,095 --> 00:01:27,539
displacement and because the root mean
square appears so often, we usually label
20
00:01:27,539 --> 00:01:33,951
it with the index rms, so X rms will be
the root mean square displacement
21
00:01:33,951 --> 00:01:35,131
of a random walk.
22
00:01:35,290 --> 00:01:40,100
So let's - the simplest situation to
consider is the Pearson random walk
23
00:01:40,100 --> 00:01:47,840
in which we take steps of fixed length but
random direction.
24
00:01:47,840 --> 00:01:55,359
So here each step has length a and the
angle between each step theta is random.
25
00:01:55,359 --> 00:02:00,440
So mathematically we can describe the
properties of the Pearson random
26
00:02:00,440 --> 00:02:07,626
walk as that the mean value of each single
step is equal to a, so fixed step length.
27
00:02:12,414 --> 00:02:17,708
Also, there is no bias in the walk, and so
the average value of each individual
28
00:02:17,708 --> 00:02:23,649
displacement x sub i is equal to 0. So
angle bracket is meant to denote average
29
00:02:23,649 --> 00:02:28,839
over all possible realizations of the
walk - over all possible realizations of a
30
00:02:28,839 --> 00:02:33,124
single step. So this is the statement that
there is no bias and furthermore,
31
00:02:33,124 --> 00:02:41,224
because this steps are uncorrelated, that
means that the dot product of x i with x j
32
00:02:41,224 --> 00:02:47,093
for any i not equal to j is equal to 0. So
this is the mathematical statement that
33
00:02:47,093 --> 00:02:53,783
there is no correlation between steps.
Successive steps or steps further down
34
00:02:53,783 --> 00:03:00,413
the road. So with these assumptions, let's
now calculate the mean displacement
35
00:03:00,413 --> 00:03:05,093
of a walk after N steps and the root mean
square displacement. So the mean
36
00:03:05,093 --> 00:03:10,273
displacement, so I'll denote that by
capital X sub N is just the sum of the
37
00:03:10,273 --> 00:03:17,503
individual displacements, so sum from i
equals 1 to N of the little x i and we
38
00:03:17,503 --> 00:03:22,423
take the average value. But by
construction, each x i has an average
39
00:03:22,423 --> 00:03:26,523
value 0, so we are summing a whole bunch
of values that equal 0, and so we get
40
00:03:26,523 --> 00:03:28,253
nothing.
41
00:03:28,654 --> 00:03:32,654
Let's now look at the root - at the mean
square displacement, so we're going to
42
00:03:32,654 --> 00:03:40,074
ask for X N, square it and then take the
average. And so what is this quantity?
43
00:03:40,566 --> 00:03:48,516
So again we have to take the sum of the
displacements x i, i equals 1 to N, square
44
00:03:48,516 --> 00:03:55,346
it and then take the average value. So
when we square this sum, this binomial,
45
00:03:55,346 --> 00:03:59,366
there are two types of terms. There are
called diagonal terms where we have
46
00:03:59,366 --> 00:04:04,716
x i dotted into x i and so there will be
terms that look like this - summation
47
00:04:04,716 --> 00:04:12,286
i equals 1 to N of x i squared and then
there are all the cross terms where we
48
00:04:12,286 --> 00:04:21,776
sum over all possible combinations i not
equal to j of x i dot x j and then we have
49
00:04:21,776 --> 00:04:26,912
to take the average value of all of this.
So by construction, these cross terms are
50
00:04:26,912 --> 00:04:31,201
all 0 because there was no correlations
between successive steps, so we just
51
00:04:31,201 --> 00:04:37,894
forget about this. The diagonal terms,
they're all identical, they're the
52
00:04:37,894 --> 00:04:42,101
squared length of each individual step -
there's N such terms and so this is
53
00:04:42,101 --> 00:04:49,972
nothing more than N a squared. So this
quantity X N squared is known as the mean
54
00:04:49,972 --> 00:04:54,269
squared displacement and the square root
of the mean square displacement is
55
00:04:54,269 --> 00:04:59,812
precisely the root mean square
displacement X rms, so X rms, which is
56
00:04:59,812 --> 00:05:06,210
defined to be the square root of the mean
square displacement X N squared average
57
00:05:06,210 --> 00:05:13,121
value, this is equal to the square root of
N a. So this is our first fundamental
58
00:05:13,121 --> 00:05:18,982
result about random walks, which is that
the rms displacement grows not linearly
59
00:05:18,982 --> 00:05:22,582
in the number of steps, but only as the
square root of the number of steps.
60
00:05:22,873 --> 00:05:27,768
So random walk is actually not very
efficient at exploring space. The other
61
00:05:27,768 --> 00:05:32,358
point to emphasize here is that there is
the factor a which makes this equation
62
00:05:32,358 --> 00:05:36,293
dimensionally correct because on the left
hand side we have the units of length and
63
00:05:36,293 --> 00:05:40,604
on the right hand we have the units of
length and the scaling factor in front is
64
00:05:40,604 --> 00:05:45,120
the square root of N. This is one of the
fundamental results in the theory of
65
00:05:45,120 --> 00:05:46,370
random walks.