1
00:00:09,433 --> 00:00:13,411
In the previous module,
I gave you a cartoon example
2
00:00:13,418 --> 00:00:16,349
of how a Markov chain coarse-grains
3
00:00:16,349 --> 00:00:18,896
as you go to longer
and longer time blocks.
4
00:00:18,902 --> 00:00:20,558
So, I gave you a Markov chain
5
00:00:20,569 --> 00:00:23,143
that worked, let’s say,
at one second resolution,
6
00:00:23,503 --> 00:00:26,621
and then I showed you
how to build a Markov chain
7
00:00:26,629 --> 00:00:29,658
that worked if your time
resolution was poor.
8
00:00:29,668 --> 00:00:31,594
So, for example let’s say,
9
00:00:31,595 --> 00:00:36,206
you could only observe the first second
of each two second block.
10
00:00:37,139 --> 00:00:42,458
That decimation coarse graining
transforms the underlying model itself,
11
00:00:42,479 --> 00:00:44,156
and so, as you saw,
12
00:00:44,170 --> 00:00:48,483
when we went from the fine-grained model,
Markov chain,
13
00:00:49,012 --> 00:00:52,204
and coarse-grained it
on blocks of scale 2,
14
00:00:52,208 --> 00:00:54,626
that Markov chain seemed to get
a little more complicated,
15
00:00:54,639 --> 00:00:56,798
and all I mean by that,
it seemed to have more arrows –
16
00:00:57,208 --> 00:01:00,057
we don’t really have good way
to judge the complexity of a Markov chain.
17
00:01:00,318 --> 00:01:02,111
But the model certainly changed,
18
00:01:02,133 --> 00:01:04,988
and it didn’t necessarily
change for the better.
19
00:01:05,006 --> 00:01:07,425
Even though we simplified
our observations,
20
00:01:07,457 --> 00:01:11,438
the model itself seemed to do something,
well, not necessarily weird,
21
00:01:11,459 --> 00:01:15,921
but something that didn’t seem to have
a particular structure to how it changed.
22
00:01:17,395 --> 00:01:20,911
But if we coarse-grained
on sufficiently long timescales,
23
00:01:20,916 --> 00:01:26,004
it appeared that the Markov chain
coarse-grained to a simpler case
24
00:01:26,030 --> 00:01:30,427
where the outgoing probabilities
for each of the states were the same.
25
00:01:31,071 --> 00:01:36,350
So, each state had the same probability
to go to state A, B, C, and D
26
00:01:38,102 --> 00:01:40,056
as the other states did.
27
00:01:40,456 --> 00:01:42,182
In this module, here, what I’m going to do
28
00:01:42,191 --> 00:01:44,404
is show you how to do
a little bit of linear algebra
29
00:01:44,414 --> 00:01:46,131
to actually make that concept rigorous,
30
00:01:46,150 --> 00:01:50,022
to talk about how a Markov
chain will, eventually,
31
00:01:50,040 --> 00:01:51,643
if you coarse-grain enough,
32
00:01:51,670 --> 00:01:56,247
simplify into a small into a smaller
subspace of all possible models.
33
00:01:56,457 --> 00:02:01,139
This would be one of our first examples
of a renormalization group transformation
34
00:02:01,164 --> 00:02:03,847
that takes you
to what we call a fixed point.
35
00:02:04,736 --> 00:02:05,997
So, what I’m going to do
36
00:02:05,998 --> 00:02:08,348
is give you that example
using a much simpler Markov chain
37
00:02:08,362 --> 00:02:09,620
which I’ve drawn on the board here.
38
00:02:09,631 --> 00:02:12,168
This Markov chain has two states, A and B.
39
00:02:12,191 --> 00:02:13,475
What I’ve done,
40
00:02:13,491 --> 00:02:17,270
instead of writing
exact numerical probabilities
41
00:02:17,277 --> 00:02:18,502
for each of these transitions,
42
00:02:18,515 --> 00:02:22,007
I’ve just parameterized the system
with one parameter ϵ.
43
00:02:22,313 --> 00:02:25,670
So, in this case here,
what we have is a system
44
00:02:25,688 --> 00:02:29,312
that can jump from A to B
with probability 1 - ϵ,
45
00:02:29,830 --> 00:02:33,578
or it can stay in state A
with probability ϵ.
46
00:02:33,593 --> 00:02:35,957
If we make ϵ small,
47
00:02:35,963 --> 00:02:38,824
that means that the probability
to stay in state A is small,
48
00:02:38,839 --> 00:02:40,867
so the system will tend
to oscillate back and forth –
49
00:02:40,878 --> 00:02:44,054
it will go ABABAB.
50
00:02:44,055 --> 00:02:48,133
As ϵ gets larger and larger,
51
00:02:48,139 --> 00:02:51,205
it will have a certain probability
to stay in state A.
52
00:02:51,214 --> 00:02:58,572
So, it might it might, in fact,
go AAABBBABAABB,
53
00:02:58,586 --> 00:03:02,666
it’s a kind of slippy counter
as ϵ gets larger and larger.
54
00:03:02,696 --> 00:03:06,561
So, a simple way
to write or describe this model
55
00:03:06,969 --> 00:03:09,990
is to imagine that we describe
the state of the system
56
00:03:09,997 --> 00:03:11,370
using your column vector.
57
00:03:11,425 --> 00:03:13,690
In this case the column vector
will have two entries:
58
00:03:13,692 --> 00:03:17,003
the first entry will be the probability
that you’re in state A;
59
00:03:17,006 --> 00:03:20,216
the second entry will be the probability
that you’re in state B.
60
00:03:20,463 --> 00:03:23,697
Now we can describe
the evolution of that system over time
61
00:03:23,713 --> 00:03:25,618
using a two-by-two matrix
62
00:03:26,062 --> 00:03:30,013
where the entries of the matrix
look like this.
63
00:03:32,253 --> 00:03:36,358
Each term here
is a conditional probability
64
00:03:36,378 --> 00:03:40,926
that tells you how you move
depending upon which state you’re in.
65
00:03:41,021 --> 00:03:44,628
So, for example, we can see
if the matrix is written like this,
66
00:03:44,628 --> 00:03:48,680
where, for example, the first term
in the top-left corner here of this matrix
67
00:03:48,688 --> 00:03:52,210
is the probability
that given you’re in state A,
68
00:03:52,227 --> 00:03:55,776
what’s the probability
that you transition to state A,
69
00:03:55,776 --> 00:03:57,246
stay in state A.
70
00:03:57,246 --> 00:04:00,157
Or here, for example,
if you’re in the top-right corner,
71
00:04:00,161 --> 00:04:03,163
this is the probability that,
given you’re in state B,
72
00:04:03,176 --> 00:04:05,396
you transition to state A.
73
00:04:05,578 --> 00:04:08,702
Notice that when you do
the matrix multiplication here,
74
00:04:09,449 --> 00:04:11,239
and I’ll just do the top one
75
00:04:11,242 --> 00:04:15,500
to give you a sense of how this works,
in case you haven’t seen it before,
76
00:04:19,166 --> 00:04:21,334
This top entry here now says
77
00:04:21,345 --> 00:04:23,577
that the probability
that you’re in state A
78
00:04:23,588 --> 00:04:24,996
after one time step
79
00:04:25,012 --> 00:04:27,646
is the probability
that you begin in state A
80
00:04:28,027 --> 00:04:30,565
and transition to the same state A,
81
00:04:30,574 --> 00:04:33,374
you stay in that state,
the probability of A given A,
82
00:04:33,637 --> 00:04:36,891
plus the probability
that if you begin in state B,
83
00:04:36,904 --> 00:04:38,215
the probability of state B,
84
00:04:38,229 --> 00:04:41,574
times the probability
of transitioning from B to A.
85
00:04:41,584 --> 00:04:47,754
And then we’ll leave as a homework example
for you to compute the second term here.
86
00:04:48,039 --> 00:04:51,669
So what we see is we can now
evolve the system through time
87
00:04:51,675 --> 00:04:55,520
by multiplying using this matrix here,
88
00:04:55,525 --> 00:04:59,262
which is sometimes called
stochastic matrix.
89
00:04:59,401 --> 00:05:01,494
One of the things
that you can see right away
90
00:05:01,501 --> 00:05:05,164
that makes this matrix special
compared to all two-by-two matrices
91
00:05:05,180 --> 00:05:08,682
is that all the columns here
have to sum to 1.
92
00:05:08,702 --> 00:05:10,238
If you’re in state A,
93
00:05:10,246 --> 00:05:12,355
one of two things
in this case must happen.
94
00:05:12,379 --> 00:05:15,512
You either stay in the state
or you transition to another state.
95
00:05:16,112 --> 00:05:17,743
There’s no other possibilities,
96
00:05:17,756 --> 00:05:21,074
and the probabilities therefore exhaust
the space and have to sum to 1.
97
00:05:21,561 --> 00:05:23,508
Another feature, of course,
of a stochastic matrix
98
00:05:23,517 --> 00:05:25,211
is none of these entries can be negative.
99
00:05:25,468 --> 00:05:28,505
So stochastic matrices are
an interesting sort of subspace
100
00:05:28,543 --> 00:05:32,744
of all the possible two-by-two matrices
that you will encounter in your life.
101
00:05:36,722 --> 00:05:40,700
Once you’ve represented the Markov chain
as a stochastic matrix,
102
00:05:40,717 --> 00:05:45,425
and I’ll write a particular Markov chain
that we have here in this new form,
103
00:05:46,265 --> 00:05:49,624
it becomes a simple matter
to talk about what happens
104
00:05:49,652 --> 00:05:51,616
if you skip observations.
105
00:05:51,634 --> 00:05:54,978
If the system jumps 2 time-steps
before you see it again,
106
00:05:55,033 --> 00:05:59,892
all I do is take this evolution matrix T –
107
00:05:59,896 --> 00:06:04,161
sometimes we call it an evolution operator
if we’re feeling a little punchy –
108
00:06:04,424 --> 00:06:07,988
all we do is take
this evolution operator T
109
00:06:08,645 --> 00:06:10,771
and multiply it by itself.
110
00:06:10,780 --> 00:06:12,205
And now what we have
111
00:06:12,209 --> 00:06:15,034
is when this matrix
acts on a probability vector
112
00:06:15,047 --> 00:06:16,707
it takes it one step in the future.
113
00:06:16,714 --> 00:06:19,491
You act on that matrix again
on the results of that,
114
00:06:19,509 --> 00:06:21,722
and it takes you two steps in the future.
115
00:06:21,754 --> 00:06:26,475
And so the Markov chain corresponding
to the observation series
116
00:06:26,507 --> 00:06:28,605
that’s been coarse-grained
in blocks of two,
117
00:06:28,633 --> 00:06:32,105
and this is decimation course graining
where we take the first observation,
118
00:06:32,382 --> 00:06:36,760
we can now write that very simply
as the product of this matrix with itself.
119
00:06:36,769 --> 00:06:39,340
So I'll write that out for you,
120
00:06:39,897 --> 00:06:44,052
and just show you how the first term goes.
121
00:06:44,088 --> 00:06:45,973
The probability that if you’re in state A,
122
00:06:45,990 --> 00:06:49,299
and you stay in state A two steps later,
123
00:06:49,309 --> 00:06:58,004
is equal to this product here:
ϵ² + (1 - ϵ)²
124
00:06:58,013 --> 00:07:01,731
And we’ll leave these other entries
as an exercise, as you please.
125
00:07:02,355 --> 00:07:04,091
In words what this says
126
00:07:04,105 --> 00:07:06,519
is the probability
that if you begin in state A,
127
00:07:06,531 --> 00:07:08,734
you’ll be in state A two steps later,
128
00:07:08,744 --> 00:07:10,604
is the sum of two possibilities:
129
00:07:10,613 --> 00:07:13,598
the first is, of course,
if you stay in the state A –
130
00:07:13,642 --> 00:07:16,689
if you just stay in the state A
on the second time-step,
131
00:07:16,719 --> 00:07:19,276
or on the first time-step
and the second time-step.
132
00:07:19,566 --> 00:07:21,916
So the probability
of that happening is ϵ²,
133
00:07:21,934 --> 00:07:24,527
the probability that you stay in A twice;
134
00:07:24,940 --> 00:07:27,932
or the other possibility
is that you start in state A
135
00:07:27,954 --> 00:07:30,010
on the second time-step
you jump to state B,
136
00:07:30,031 --> 00:07:32,601
and then you quickly jump back
to state A before anybody notices.
137
00:07:32,896 --> 00:07:36,080
And that’s the second term here (1 - ϵ)².
138
00:07:37,314 --> 00:07:42,467
So now we can see that in some sense
it’s a rather trivial problem
139
00:07:42,505 --> 00:07:46,295
to see what happens to this matrix
as you continue to coarse-grain:
140
00:07:46,302 --> 00:07:48,809
if you take blocks of 3, 4, or 5,
141
00:07:49,186 --> 00:07:51,997
all you have to do
to see the resulting model
142
00:07:52,026 --> 00:07:55,344
is raise T to the power
that you’re interested in.
143
00:07:55,358 --> 00:07:57,914
Here n is now just the block size.