1
00:00:03,920 --> 00:00:08,580
Hello! Bonjour! Xin Chào! Shimboni!

2
00:00:08,580 --> 00:00:14,880
Welcome to the first week of Statistical Mechanics: Algorithms and computations

3
00:00:14,880 --> 00:00:18,460
from the physics department of Ecole Normale Supérieure.

4
00:00:18,460 --> 00:00:24,020
This week, as any week, there will be a lecture,

5
00:00:24,170 --> 00:00:28,940
a tutorial, and a homework session.

6
00:00:29,050 --> 00:00:38,020
This week's lecture, Lecture 1, will be devoted to an introduction to Monte Carlo algorithms.

7
00:00:39,220 --> 00:00:45,240
The main setting will be in Monaco; more precisely, in Monte Carlo.

8
00:00:45,240 --> 00:00:49,220
We will watch children play in the sand

9
00:00:49,220 --> 00:00:54,220
and adults play on the Monte Carlo Heliport.

10
00:00:54,220 --> 00:00:59,400
They will teach us a crucial lesson about sampling.

11
00:01:00,120 --> 00:01:09,060
This week's tutorial, Tutorial 1, will analyze Monte Carlo algorithms and their convergence.

12
00:01:09,060 --> 00:01:15,040
We will derive a crucial theorem about the convergence of Monte Carlo algorithms

13
00:01:15,040 --> 00:01:19,540
using this 3x3 pebble game.

14
00:01:19,540 --> 00:01:25,280
Finally, this week's homework session, Homework Session 1,

15
00:01:25,280 --> 00:01:29,060
will be all about practical computing.

16
00:01:29,480 --> 00:01:38,020
We will download, take apart, and put back together simple Python programs.

17
00:01:38,020 --> 00:01:42,820
We will, so-to-speak, get out hands dirty,

18
00:01:42,820 --> 00:01:49,040
and we will learn about a crucial rule of thumb,

19
00:01:49,040 --> 00:01:52,080
the famous one half rule.

20
00:01:52,180 --> 00:02:00,740
that will teach us how to choose the parameters of our Monte Carlo computations.

21
00:02:00,740 --> 00:02:10,160
The material of week 1, this week, is roughly on the level of the entire course,

22
00:02:10,160 --> 00:02:18,760
so if you are able to follow Lecture 1, Tutorial 1, and Homework Session 1,

23
00:02:18,760 --> 00:02:24,160
you will be well set to follow the entire course.

24
00:02:24,160 --> 00:02:32,420
So, let's get started, with Statistical Mechanics: Algorithms and Computations.

25
00:02:36,460 --> 00:02:41,960
The first instance of sampling is called direct sampling

26
00:02:42,350 --> 00:02:47,880
Direct sampling is illustrated by this amusing game

27
00:02:48,170 --> 00:02:56,820
that children (if you believe it) play on the Monte Carlo beaches, on free afternoons.

28
00:02:57,360 --> 00:03:08,830
In the sand, they draw a square and a circle. They then throw pebbles..

29
00:03:08,830 --> 00:03:12,850
..randomly into the square.

30
00:03:13,260 --> 00:03:19,720
Each pebble inside the square is counted as a trial,

31
00:03:20,960 --> 00:03:27,420
and each pebble inside the circle counts as a hit.

32
00:03:27,980 --> 00:03:38,920
In fact, the children on the Monte Carlo beach do a direct sampling Monte Carlo simulation.

33
00:03:39,990 --> 00:03:55,690
They compute the number pi from the ratio of the area of the circle to the area of the square.

34
00:03:58,070 --> 00:04:03,680
This ratio is equal to pi/4,

35
00:04:04,280 --> 00:04:12,130
so, the children can compute the number pi by throwing pebbles.

36
00:04:14,740 --> 00:04:33,180
As an example, suppose that in a game of 4000 pebble trials they obtain 3156 hits,

37
00:04:34,160 --> 00:04:46,490
they obtain the approximation pi~3.156 from this calculation.

38
00:04:47,390 --> 00:04:57,200
In the limit of an infinitely long beach party, of an infinite number of pebbles,

39
00:04:57,320 --> 00:05:03,290
the exact value of pi will indeed be computed.

40
00:05:04,040 --> 00:05:08,880
In Python, this gives the following program

41
00:05:10,100 --> 00:05:17,060
its key element are the two random numbers random.uniform,

42
00:05:17,950 --> 00:05:30,970
they give a random position in x between -1 and 1, and a random position in y between -1 and 1,

43
00:05:31,710 --> 00:05:38,400
in total, a random pebble position inside the square.

44
00:05:39,000 --> 00:05:51,660
So, here again is the children's game in Python, in a version which allows us to do many runs,

45
00:05:52,550 --> 00:06:02,780
one afternoon of 4000 pebbles, followed by another afternoon of 4000 pebbles, and so on and so on..

46
00:06:03,370 --> 00:06:07,690
Output of this program is shown here.

47
00:06:09,170 --> 00:06:19,280
Before moving on, please take a moment to download, run and modify some programs.

48
00:06:19,960 --> 00:06:33,670
On the Coursera website, you will find the program direct_pi.py, that allows you to do one game of the children's play.

49
00:06:34,590 --> 00:06:41,130
You will also find the program direct_pi_multirun.py,

50
00:06:41,190 --> 00:06:47,310
that allows you to do many runs of the children's game,

51
00:06:47,310 --> 00:06:47,340
or, if you like, many afternoons on the sunny Monte Carlo beach.
that allows you to do many runs of the children's game,

52
00:06:47,340 --> 00:06:55,100
or, if you like, many afternoons on the sunny Monte Carlo beach.

53
00:07:01,700 --> 00:07:07,140
In Monte Carlo, it is not only children who play at pebble games,

54
00:07:09,310 --> 00:07:17,400
adults also play at their version of pebble game on the local heliport.

55
00:07:18,500 --> 00:07:28,550
After storing away all the helicopters, they wander around the square-shaped landing pad,

56
00:07:28,850 --> 00:07:34,550
that looks just like the children's game, only larger.

57
00:07:36,660 --> 00:07:47,610
No one can throw a pebble randomly into such a big field, so the algorithm must be modified.

58
00:07:47,610 --> 00:07:55,600
We start in the upper right corner, our handbag filled with pebbles,

59
00:07:57,060 --> 00:08:04,430
with closed eyes, we throw the pebble in a random direction,

60
00:08:05,410 --> 00:08:11,540
we then walk to the point at which the pebble has landed,

61
00:08:13,530 --> 00:08:20,400
pull out a new pebble, and a new throw will follow.

62
00:08:21,730 --> 00:08:30,800
The aim of the game - as before - is to sweep out evenly the heliport square.

63
00:08:31,630 --> 00:08:43,110
This algorithm will work, but what should we do when we throw a pebble outside of the square?

64
00:08:44,480 --> 00:08:51,020
Should we continue inside the square, as if nothing has happened?

65
00:08:51,610 --> 00:08:55,570
Or should we climb over the fence of the heliport,

66
00:08:55,570 --> 00:08:55,600
and continue outside of the square until eventually we will come back?
Or should we climb over the fence of the heliport,

67
00:08:55,600 --> 00:09:01,960
and continue outside of the square until eventually we will come back?

68
00:09:04,720 --> 00:09:17,090
We should ask somebody to bring us the outfielder, and place it on top of the pebble already present,

69
00:09:18,250 --> 00:09:24,550
then we should pull out a new pebble and do a new throw.

70
00:09:25,860 --> 00:09:36,000
If this is again an outfielder, we should again have it brought and place it on top of the pile.

71
00:09:37,570 --> 00:09:48,450
Eventually we will move on, visit other areas of the heliport, and also come close to the center,

72
00:09:48,720 --> 00:09:51,840
where there are no rejections.

73
00:09:51,840 --> 00:09:58,240
At the end of the game, the heliport looks as follows

74
00:10:00,110 --> 00:10:13,220
In the center of the pad, there are only single stones, because from the center there are no outfielders, no rejections.

75
00:10:13,930 --> 00:10:26,090
Close to the boundaries, and especially close to the corners, there are piles, corresponding to rejected moves.

76
00:10:26,660 --> 00:10:40,900
This is quite mind-boggling for us today, and it was even more so in 1953, when this famous Metropolis algorithm was invented.

77
00:10:41,670 --> 00:10:54,040
Before studying why this program is correct, please take a moment to download, run and modify the relevant programs.

78
00:10:54,750 --> 00:11:08,430
On the Coursera website you will find the program markov_pi.py, that allows you to run one party on the Monte Carlo heliport.

79
00:11:08,430 --> 00:11:28,050
The key element of this program is as follows. At position x and y, you move by little random displacement delta_x and delta_y that can be positive or negative.

80
00:11:29,240 --> 00:11:39,790
When the move is rejected, you simply remain where you are, that means, you build a little pile.

81
00:11:40,710 --> 00:11:49,120
On the website, you also find the program markov_pi_multirun.py,

82
00:11:49,870 --> 00:12:00,750
that allows you to simulate many heliport parties. Output of this program is shown here.

83
00:12:03,930 --> 00:12:17,550
You see that although the strategy of piling up pebbles seems a bit strange, the output comes out just right.

84
00:12:22,660 --> 00:12:36,690
We left the Monte Carlo heliport a few moments ago, without clarifying the reason for this pile-up of pebbles, especially near the boundaries.

85
00:12:37,730 --> 00:12:46,440
Remember, we want to spread out the pebbles evenly on the heliport square,

86
00:12:46,440 --> 00:12:46,470
so the strategy of making piles appears very strange indeed.
Remember, we want to spread out the pebbles evenly on the heliport square

87
00:12:46,470 --> 00:12:52,830
so the strategy of making piles appears very strange indeed.

88
00:12:53,930 --> 00:13:04,130
to understand why this strategy is ok, let us simplify the game even further

89
00:13:04,790 --> 00:13:12,100
and consider this 3x3 pebble game shown here

90
00:13:12,870 --> 00:13:22,920
the pebbles can move in at most four directions: left, up, right and down

91
00:13:23,960 --> 00:13:30,440
these moves are in the same spirit as those of the heliport

92
00:13:30,830 --> 00:13:43,730
in the configuration a, we can only move to the left or down, to configurations b and c

93
00:13:45,720 --> 00:13:51,070
we can write this into a little equation

94
00:13:53,660 --> 00:14:10,490
in this equation, p(a->b) is the algorithmic transition probability from a to b, etc.

95
00:14:10,870 --> 00:14:16,730
Now, we consider that we have run this program for a long time.

96
00:14:17,650 --> 00:14:22,530
in fact, we suppose that we have reached a steady state.

97
00:14:22,530 --> 00:14:39,350
The probability pi_a to be at configuration a is then given  by the probability to be at a and to remain on that site,

98
00:14:39,920 --> 00:14:53,120
plus the probability  pi_b to be at configuration b times the probability to move from b to a,

99
00:14:53,360 --> 00:15:05,400
plus the probability  pi_c to be at configuration c and to make a transition from c to a

100
00:15:05,930 --> 00:15:13,510
Putting these two equations together, we find..

101
00:15:25,670 --> 00:15:32,090
this equation is the celebrated global balance condition

102
00:15:34,200 --> 00:15:49,070
our Monte Carlo algorithm, which is nothing else but the set of transition probabilities from one site to another, must satisfy it

103
00:15:49,660 --> 00:16:00,720
there are many algorithms, even on the 3x3 pebble game, that satisfy the global balance condition

104
00:16:02,060 --> 00:16:19,720
one way of satisfying the global balance condition consists in equating the pieces involving a and b separately, and also the pieces involving a and c

105
00:16:21,710 --> 00:16:34,500
this is the detailed balance condition, and it is really famous. What does the detailed balance condition mean?

106
00:16:35,210 --> 00:16:44,100
in our 3x3 pebble game, we want to sweep out evenly all the configurations

107
00:16:45,110 --> 00:16:54,380
we want to have pi_a equals to pi_b equals to pi_c, and so on

108
00:16:54,740 --> 00:17:14,720
this implies that we need to have probabilities p(a->b) equal to p(b->a), and p(a->c) equal to p(c->a)

109
00:17:15,430 --> 00:17:34,280
How can we implement this? Well, very simply. By moving from any configuration with probability 1/4 to the right, up ,to the left and down.

110
00:17:35,170 --> 00:17:46,350
All the allowed moves have probability 1/4. This is a simple solution and it involves rejections.

111
00:17:46,710 --> 00:18:02,340
If we are at configuration a, we reject the moves to the right and up. We have a probability of 1/2 of staying at site a.

112
00:18:02,880 --> 00:18:10,820
the probability to move from a to b or from a to c remains 1/4

113
00:18:11,170 --> 00:18:17,030
on configuration b, we have a rejection probability of 1/4

114
00:18:17,660 --> 00:18:24,700
and on configuration c we also have a rejection probability of 1/4

115
00:18:25,060 --> 00:18:40,930
this is the essence of the celebrated Metropolis algorithm, and we will discuss it again in the same setting in Tutorial 1 of Statistical Mechanics, Algorithms and Computations

116
00:18:41,590 --> 00:18:56,960
We have just been able to devise what is called a Markov chain Monte Carlo algorithm for the case where we sweep out all configurations evenly.

117
00:18:57,610 --> 00:19:08,790
before treating the case of general probabilities pi_a, let us ask a few questions

118
00:19:09,150 --> 00:19:21,280
let us suppose that in the 3x3 pebble game, we are in upper right corner at time t=0

119
00:19:22,170 --> 00:19:31,500
we throw a die of the four possible moves to the right, up, to the left, down

120
00:19:32,360 --> 00:19:39,470
we sample the move to the left, where should we move to?

121
00:19:44,430 --> 00:19:55,790
yes, clearly we should move to left. At t=1, the configuration will be as follows

122
00:19:56,590 --> 00:20:22,730
Question 2: at t=1, with the pebble in the upper middle position, we again roll a die (right, up, left, down). We sample the up move, what should we do?

123
00:20:25,250 --> 00:20:38,840
Yes, clearly, we should stay where we are. At time t=2, we are again in the upper middle configuration.

124
00:20:39,580 --> 00:20:48,530
Note that we count this configuration a second time, that we build a pile, so to speak.

125
00:20:48,830 --> 00:21:06,160
Question 3: now, at time t=2, in the upper middle configuration, we again sample a move, we sample the  down move. What should we do?

126
00:21:11,360 --> 00:21:21,350
Clearly, we should move down. At time t=3 we are in the center of the square.

127
00:21:21,770 --> 00:21:37,910
Question 4, final question: at time t=3, in the central configuration what will be the rejection probability of the next move?

128
00:21:40,620 --> 00:21:52,980
Yes, clearly, it will be zero. Each of the four moves will be proposed with probability 1/4 and it will be accepted.

129
00:21:58,630 --> 00:22:07,280
Finally, let us consider what we call the inhomogeneous 3x3 pebble game.

130
00:22:08,440 --> 00:22:15,010
The numbers indicate the statistical weights of the configurations.

131
00:22:15,730 --> 00:22:26,610
and the pebble should be twice as often on the upper right corner than on the site in the middle on the top row.

132
00:22:27,260 --> 00:22:35,290
and four times as often on the upper left corner than on the site just below it.

133
00:22:35,290 --> 00:22:47,950
To devise a Markov chain Monte Carlo algorithm for the inhomogeneous pebble game, we must visit again the detailed balance condition

134
00:22:48,490 --> 00:22:56,720
where probabilities pi_a and pi_b are the numbers written up here.

135
00:22:57,380 --> 00:23:11,140
we would now violate the detailed balance condition if we move with the same probability from site a to site b as from site b to site a

136
00:23:11,350 --> 00:23:31,890
Metropolis et al., in 1953, proposed their famous Metropolis acceptance probability to handle the case when the probabilities pi_a on the sites are no longer constant.

137
00:23:32,370 --> 00:23:36,920
they proposed the rule shown here

138
00:23:37,960 --> 00:23:52,790
In this rule either the transition probability p(a->b) or the transition probability p(b->a) is equal to one.

139
00:23:53,590 --> 00:24:01,150
an in both cases, the detailed balance condition is ok

140
00:24:01,620 --> 00:24:10,010
Let us illustrate this most important Metropolis acceptance probability in the pebble game.

141
00:24:10,810 --> 00:24:24,780
Suppose we are in the upper right corner, and we want to move to the left. This move will be proposed with probability 1/4.

142
00:24:25,940 --> 00:24:39,530
we should accept this move with the probability minimum(1, 0.5/1), which is equal to 1/2.

143
00:24:39,880 --> 00:24:51,300
so we should accept this move from the corner to the middle with a probability 1/2, otherwise we should stay where we are.

144
00:24:52,610 --> 00:25:00,460
Likewise, suppose we are in the center-left configuration and we want to move down

145
00:25:00,780 --> 00:25:07,500
the move then will be proposed with probability 1/4 again

146
00:25:07,710 --> 00:25:23,260
we should accept this move with a probability minimum(1, 3/0.5), which is equal to minimum(1,6) which is equal to 1

147
00:25:23,640 --> 00:25:28,970
that is, we should accept this move with probability one

148
00:25:28,970 --> 00:25:35,600
the 3x3 pebble game algorithms can be found on the Coursera website

149
00:25:36,840 --> 00:25:50,010
the homogeneous 3x3 pebble game will be scrutinized in Tutorial 1 under the name of pebble_basic.py

150
00:25:51,440 --> 00:26:01,820
the inhomogeneous pebble game that we just discussed can be found under the name of pebble_basic_inhomogeneous.py

151
00:26:02,830 --> 00:26:17,010
you will see how in that algorithm the propose probability of 1/4 is modified by the Metropolis acceptance probability

152
00:26:17,340 --> 00:26:29,910
of minimum of 1 and probability pi of the site that you want to go to, divided by probability pi of the site where you are at

153
00:26:30,540 --> 00:26:38,590
you are invited to download, run and modify  all these programs.

154
00:26:42,780 --> 00:26:54,790
In conclusion, we have plunged in this lecture 1 of Statistical Mechanics: Algorithms and Computations, into the field of Monte Carlo algorithms

155
00:26:56,190 --> 00:27:03,180
the key concept is sampling, obtaining the pebble positions.

156
00:27:03,480 --> 00:27:22,000
we have studied two basic approaches to sampling: direct sampling in the children's algorithm  and Markov chain sampling in the adults game on the heliport.

157
00:27:22,740 --> 00:27:35,460
to understand Markov chain sampling, we took to a discretized version of the heliport, namely the 3x3 pebble game

158
00:27:36,000 --> 00:27:47,830
in its homogeneous version and inhomogeneous version, that was governed by the Metropolis acceptance probability

159
00:27:49,820 --> 00:27:53,420
it remains to thank you for your attention.

160
00:27:53,420 --> 00:28:05,930
See you again in further sessions of Statistical Mechanics: Algorithms and Computations, where the concepts introduced today will be considerably deepened.