1 00:00:03,920 --> 00:00:08,580 Hello, bonjour, nomoshkar, ola, estou? 2 00:00:08,580 --> 00:00:15,330 Welcome to the second week of Statistical Mechanics: Algorithms and Computations 3 00:00:15,330 --> 00:00:19,330 from the Physics Department of Ecole Normale Superieure. 4 00:00:20,440 --> 00:00:25,120 Last week, we studied simple problems in statistics 5 00:00:25,740 --> 00:00:30,530 children on the beach, discrete pebble games, 6 00:00:31,130 --> 00:00:35,680 people walking around on the Monte Carlo heliport. 7 00:00:37,040 --> 00:00:43,280 In this second week, we move on to study and to simulate 8 00:00:43,280 --> 00:00:47,280 model systems in physics 9 00:00:47,280 --> 00:00:51,920 particle with positions, velocities and interactions 10 00:00:51,920 --> 00:00:55,920 using a statistical approach 11 00:00:55,920 --> 00:01:00,360 that this is at all possible and exact 12 00:01:00,360 --> 00:01:04,360 is one of the great legacies of physics. 13 00:01:05,960 --> 00:01:09,440 The entire program of this week 14 00:01:10,300 --> 00:01:15,800 is to motivate, define and illustrate 15 00:01:16,140 --> 00:01:21,300 the statistical approach in the very famous model 16 00:01:21,300 --> 00:01:24,680 of two dimensional hard spheres 17 00:01:24,680 --> 00:01:27,460 so called hard disks. 18 00:01:28,820 --> 00:01:32,560 This model is at the center of physics 19 00:01:32,560 --> 00:01:36,560 in particular of statistical mechanics 20 00:01:38,160 --> 00:01:42,000 Note, when we speak about hard disks 21 00:01:42,000 --> 00:01:46,000 we mean idealizations of this object 22 00:01:47,550 --> 00:01:50,590 not of computer hard disks 23 00:01:50,590 --> 00:01:54,590 the memories in our laptop 24 00:01:55,660 --> 00:01:59,200 In this lecture - Lecture 2 - 25 00:01:59,580 --> 00:02:03,630 we will introduce the model of hard disks 26 00:02:03,630 --> 00:02:06,500 and also will start simulating 27 00:02:07,950 --> 00:02:14,090 hard disks, which are idealizations of billiard balls 28 00:02:14,330 --> 00:02:20,340 move as free particles whenever they are not in contact with each other 29 00:02:20,340 --> 00:02:22,990 or with a wall 30 00:02:22,990 --> 00:02:27,400 and obey simple reflection rules 31 00:02:28,840 --> 00:02:33,310 whenever they are in contact with each other, as you see here 32 00:02:33,310 --> 00:02:38,430 in an actual simulation of Newtonian dynamics 33 00:02:39,100 --> 00:02:42,430 Building on what we did last week 34 00:02:42,430 --> 00:02:45,400 We will also introduce 35 00:02:45,400 --> 00:02:50,910 direct sampling and Markov chain sampling algorithms 36 00:02:52,360 --> 00:02:56,080 we thus scrutinize the interface 37 00:02:56,080 --> 00:03:00,080 between classical Newtonian mechanics 38 00:03:00,080 --> 00:03:03,090 and statistical mechanics. 39 00:03:04,490 --> 00:03:08,170 We will see that in the statistical approach 40 00:03:08,460 --> 00:03:12,500 any two configurations of hard disks 41 00:03:13,330 --> 00:03:17,070 must be sampled with equal probability 42 00:03:18,210 --> 00:03:21,070 just as we did last week 43 00:03:21,070 --> 00:03:24,630 for pebbles on the heliport 44 00:03:24,630 --> 00:03:27,320 or on the Monte Carlo beach. 45 00:03:29,080 --> 00:03:30,680 In Tutorial 2, 46 00:03:31,630 --> 00:03:35,750 we will connect the equiprobability concept 47 00:03:36,590 --> 00:03:41,000 - a basic version of the celebrated Boltzmann distribution - 48 00:03:42,150 --> 00:03:46,250 with the central notions of statistical mechanics 49 00:03:47,040 --> 00:03:51,770 namely the partition function, the free energy, 50 00:03:52,540 --> 00:03:56,040 the phase space volume 51 00:03:56,630 --> 00:03:59,420 and the virial expansion. 52 00:04:00,160 --> 00:04:02,580 In Homework session 2 53 00:04:02,580 --> 00:04:08,520 our main concern will be - just like last week - on practical computation. 54 00:04:10,660 --> 00:04:15,960 We will actually check that the Newtonian dynamics 55 00:04:15,960 --> 00:04:19,960 of four hard disks perfectly agrees 56 00:04:20,210 --> 00:04:21,820 with the statistical approach. 57 00:04:23,000 --> 00:04:26,430 We will then analyze and interpret 58 00:04:26,430 --> 00:04:30,430 the output for this very simple problem 59 00:04:32,280 --> 00:04:40,100 The material of this week is roughly as difficult as the one of last week. 60 00:04:41,540 --> 00:04:46,630 We'll move to the central notion of statistical mechanics 61 00:04:47,410 --> 00:04:53,850 but we will discover and develop all the concepts using our algorithmic approach. 62 00:04:55,950 --> 00:04:59,250 We will remain perfectly self-contained 63 00:05:00,140 --> 00:05:03,790 and you don't have to have already taken a course 64 00:05:03,790 --> 00:05:07,790 in statistical physics or thermal physics in order to follow. 65 00:05:08,580 --> 00:05:15,670 So, let's get started with week 2 of Statistical Mechanics: Algorithms and Computations. 66 00:05:22,020 --> 00:05:23,800 What you see here 67 00:05:24,830 --> 00:05:28,360 is a configuration of four disks 68 00:05:28,730 --> 00:05:31,450 red, blue, yellow and green 69 00:05:32,680 --> 00:05:36,290 with given positions and velocities 70 00:05:36,290 --> 00:05:39,090 at time t=0 71 00:05:39,490 --> 00:05:45,820 in a box going in x from 0 to 1 and in y from 0 to 1. 72 00:05:48,250 --> 00:05:52,500 Here is the time evolution of the disks 73 00:05:52,500 --> 00:05:56,500 moving about the box, like billiard balls. 74 00:05:58,900 --> 00:06:00,830 The dynamics of this system 75 00:06:02,360 --> 00:06:05,990 - for example from a configuration at t=0 - 76 00:06:06,590 --> 00:06:09,990 consists in straight line evolution 77 00:06:10,530 --> 00:06:12,870 up to the next event. 78 00:06:14,450 --> 00:06:19,010 This event may be a wall collision, 79 00:06:19,570 --> 00:06:24,630 with incoming angle equal to the outgoing angle. 80 00:06:24,630 --> 00:06:30,200 Like with real disks, there are also pair collisions 81 00:06:32,180 --> 00:06:35,550 where the velocities change 82 00:06:36,290 --> 00:06:40,550 according to the rules of an idealized billiard 83 00:06:40,550 --> 00:06:44,550 without the complications of real systems 84 00:06:44,550 --> 00:06:48,550 such as torque or friction. 85 00:06:48,550 --> 00:06:54,000 The collision rules are quite easy to write down. 86 00:06:54,000 --> 00:06:58,000 Let us now describe in detail 87 00:06:58,610 --> 00:07:02,960 the event-driven molecular dynamics algorithm 88 00:07:03,230 --> 00:07:08,080 invented by Alder and Wainwright in 1957. 89 00:07:09,830 --> 00:07:16,990 It solves the Newtonian dynamics of the system without any approximation. 90 00:07:19,530 --> 00:07:23,370 Starting from an initial configuration 91 00:07:23,370 --> 00:07:25,550 - at t=0 - 92 00:07:25,550 --> 00:07:28,920 we must compute the next event. 93 00:07:30,200 --> 00:07:33,960 This event may be a wall collision 94 00:07:33,960 --> 00:07:37,960 or a pair collision. 95 00:07:37,960 --> 00:07:41,960 If it is a wall collision 96 00:07:41,960 --> 00:07:47,470 its time is given by the minimum of the wall collision times 97 00:07:47,470 --> 00:07:51,470 of the red, the blue, the yellow and the green disks, 98 00:07:51,820 --> 00:07:54,080 taken individually. 99 00:07:55,020 --> 00:07:58,570 Look here, the red disk 100 00:07:58,570 --> 00:08:02,570 is moving down and to the left. 101 00:08:03,330 --> 00:08:08,810 Its wall-collision time - disregarding the three other particles - 102 00:08:09,620 --> 00:08:16,460 is the minimum of the times at which it would hit the line x=0 103 00:08:16,460 --> 00:08:19,020 and y=0. 104 00:08:19,020 --> 00:08:24,890 The second type of events is a pair collision, 105 00:08:26,540 --> 00:08:30,520 for example here of the red and the blue disks. 106 00:08:32,440 --> 00:08:37,000 A pair collision takes place when at some future time 107 00:08:38,220 --> 00:08:43,980 the distance between the two disks is equal to twice their radius. 108 00:08:46,030 --> 00:08:51,010 We can compute this time using a quadratic equation. 109 00:08:52,580 --> 00:08:56,500 When the two disks are approaching each other, 110 00:08:58,060 --> 00:09:00,500 the pair collision time 111 00:09:00,500 --> 00:09:07,780 is the minimum of the two positive solutions of this quadratic equation, 112 00:09:08,980 --> 00:09:13,770 otherwise the pair collision time is infinite. 113 00:09:15,610 --> 00:09:20,780 The minimum of the six pair collision times 114 00:09:21,450 --> 00:09:24,780 and the four wall collision times 115 00:09:24,780 --> 00:09:27,960 gives us the next event in the system, 116 00:09:27,960 --> 00:09:34,340 here, at time t=0.45813 117 00:09:34,870 --> 00:09:40,840 a number that we can compute to as high precision as we want. 118 00:09:42,910 --> 00:09:46,620 We can then click through the events. 119 00:09:46,620 --> 00:09:54,570 Here the first event, a pair collision between the red and the yellow disks, 120 00:09:55,030 --> 00:09:58,570 closely followed by the second event, 121 00:09:58,570 --> 00:10:02,570 a wall collision of the blue disk, 122 00:10:03,130 --> 00:10:09,890 then the third event, the fourth event, the fifth event, the sixth event, and so on.. 123 00:10:10,770 --> 00:10:16,890 To conclude our description of the event-driven molecular dynamics algorithm, 124 00:10:17,820 --> 00:10:22,670 we realize that we must not collect events, 125 00:10:23,360 --> 00:10:26,700 but rather make a movie 126 00:10:26,700 --> 00:10:31,000 going from time t to t+delta_t 127 00:10:31,660 --> 00:10:48,590 t+2 delta_t, .. or to make things simple, from t=0 to t=1, 2, 3, 4, 5, 6 and so on.. 128 00:10:49,500 --> 00:10:52,950 Let us now ask a few questions 129 00:10:54,750 --> 00:10:56,140 Question 1 130 00:10:58,250 --> 00:11:06,690 why is Alder and Wainwright's algorithm for molecular dynamics called event-driven? 131 00:11:08,540 --> 00:11:09,950 Is it because 132 00:11:09,950 --> 00:11:17,520 Answer 1: its invention was a major event in the history of science? 133 00:11:18,140 --> 00:11:28,610 or is it (Answer 2) because the algorithm moves forth in a sequence of collisions called events? 134 00:11:35,340 --> 00:11:39,880 Of course the correct answer is Answer 2 135 00:11:40,960 --> 00:11:49,680 although it is true that the invention of molecular dynamics turned out to be a real big thing 136 00:11:50,900 --> 00:11:53,680 Question 2 137 00:11:54,920 --> 00:12:01,720 consider the sequence of configurations at regular time intervals, 138 00:12:02,090 --> 00:12:13,080 that we just saw rushing through from time t=0 to t=1, 2, 3 and so on, up to infinity/ 139 00:12:14,930 --> 00:12:22,450 On which fraction of these pictures do we see two disks in contact 140 00:12:23,850 --> 00:12:27,580 or one disk in contact with the wall? 141 00:12:29,530 --> 00:12:31,210 Answer 1: 142 00:12:32,540 --> 00:12:37,110 the probability is equal to zero, exactly. 143 00:12:39,830 --> 00:12:44,720 Answer 2: the probability is very small, 144 00:12:44,720 --> 00:12:48,720 between 1% and 10%, 145 00:12:48,720 --> 00:12:53,220 depending on the time interval between frames. 146 00:12:56,140 --> 00:13:03,730 Answer 3: the probability of contact is equal to 100%, 147 00:13:04,360 --> 00:13:09,160 because the algorithm is driven forward by collisions. 148 00:13:16,760 --> 00:13:19,750 Answer 1 is correct. 149 00:13:20,170 --> 00:13:25,360 Common sense and powerful mathematical theorems 150 00:13:25,360 --> 00:13:32,780 tell us that there is a finite number of events per unit time interval 151 00:13:34,110 --> 00:13:43,090 so the probability to have an event at time equal to 1.00000 and so on 152 00:13:43,090 --> 00:13:51,960 or at time 16.000000 and so on is exactly equal to zero. 153 00:13:52,740 --> 00:13:56,960 You will not see any collision event 154 00:13:56,960 --> 00:14:02,280 in these frames taken at integer times. 155 00:14:04,790 --> 00:14:06,280 Question 3: 156 00:14:07,780 --> 00:14:11,940 in the event-driven molecular dynamics algorithm 157 00:14:13,460 --> 00:14:17,250 we suppose that a pair collision 158 00:14:17,910 --> 00:14:21,250 or a collision of a particle with a wall 159 00:14:21,250 --> 00:14:24,390 constitute the next event. 160 00:14:26,660 --> 00:14:30,150 Isn't it possible that the next event 161 00:14:30,150 --> 00:14:34,820 is rather a collision of three disks 162 00:14:35,870 --> 00:14:38,820 or a pair collision 163 00:14:38,820 --> 00:14:44,820 taking place at exactly the same time as another wall collision? 164 00:14:50,730 --> 00:14:53,690 No, this is not possible 165 00:14:55,270 --> 00:15:00,030 Common sense and powerful mathematical theorems 166 00:15:00,030 --> 00:15:04,030 again - just like in Question 2 - tell us 167 00:15:04,030 --> 00:15:14,340 that the probability of one event taking place exactly at the same time as another event is equal to zero. 168 00:15:15,710 --> 00:15:21,560 With finite precision arithmetic on our computers 169 00:15:21,560 --> 00:15:29,800 these exceptional events may have to be taken into account in the treatment of errors. 170 00:15:30,450 --> 00:15:34,180 The event-driven molecular dynamics algorithm 171 00:15:34,900 --> 00:15:39,810 exactly solves the hard disks equations of motion 172 00:15:40,430 --> 00:15:43,810 under the assumption 173 00:15:43,810 --> 00:15:47,190 that the calculation of collision times 174 00:15:47,190 --> 00:15:53,080 velocity changes, positions and so on.. is done with infinite precision. 175 00:15:55,930 --> 00:15:59,060 This cannot really be achieved on a computer 176 00:16:00,550 --> 00:16:04,130 but the question arises whether it matters 177 00:16:04,130 --> 00:16:12,910 that in Python - as in other languages - real numbers are truncated to finite precision. 178 00:16:14,450 --> 00:16:17,470 It is easiest to answer this question 179 00:16:18,320 --> 00:16:24,160 by pitting different versions of the same event-driven molecular dynamics algorithm 180 00:16:24,160 --> 00:16:25,780 against each other. 181 00:16:25,780 --> 00:16:31,200 The two versions of the four disks molecular dynamics calculations 182 00:16:31,200 --> 00:16:35,200 that are identical at t=0 183 00:16:35,200 --> 00:16:39,580 remain very similar at initial collisions 184 00:16:39,580 --> 00:16:43,580 but then completely get out of step 185 00:16:43,580 --> 00:16:47,580 after a few dozens collisions. 186 00:16:48,620 --> 00:16:51,580 This is an extremely small number 187 00:16:51,580 --> 00:16:55,400 compared to the millions or so 188 00:16:55,400 --> 00:16:59,580 collisions that we can compute on our computers 189 00:16:59,580 --> 00:17:00,790 per second. 190 00:17:03,580 --> 00:17:05,000 This is quite strange. 191 00:17:05,640 --> 00:17:11,430 Our results for computing times as small as a few microseconds 192 00:17:11,430 --> 00:17:15,430 are exact yet uncontrolled. 193 00:17:16,630 --> 00:17:19,690 We may drive up the precision levels 194 00:17:19,690 --> 00:17:23,690 using special number formats, 195 00:17:23,690 --> 00:17:27,850 like 100 significant digits, 1000 significant digits, 196 00:17:27,850 --> 00:17:30,430 1000000 significant digits, 197 00:17:30,430 --> 00:17:35,340 that are available in Python as in other computer languages. 198 00:17:37,260 --> 00:17:43,580 But this strategy cannot defeat the onset of chaos, 199 00:17:45,060 --> 00:17:50,010 that is: cure the extreme sensitivity of our calculations 200 00:17:50,010 --> 00:17:53,220 to the numerical precision. 201 00:17:54,600 --> 00:17:57,220 It is impossible 202 00:17:57,220 --> 00:18:02,250 to control an event-driven molecular dynamics calculation 203 00:18:02,250 --> 00:18:06,250 for a few billions iterations 204 00:18:07,440 --> 00:18:10,760 Chaos, in a hard disks system, 205 00:18:11,360 --> 00:18:18,030 has its origin in the negative curvature of the disks' surface. 206 00:18:19,620 --> 00:18:22,030 This magnifies 207 00:18:22,030 --> 00:18:26,030 small differences of the trajectory 208 00:18:26,030 --> 00:18:29,100 at each pair collision 209 00:18:29,100 --> 00:18:34,850 and is very well known to whoever has played billiards. 210 00:18:37,620 --> 00:18:40,950 On the other hand, chaos 211 00:18:40,950 --> 00:18:47,990 is the main reason why even for finite system of hard disks 212 00:18:47,990 --> 00:18:54,180 we can describe it by statistical mechanics, as we will discuss in a few minutes. 213 00:18:55,690 --> 00:19:01,820 For the moment, we considered Newtonian dynamics, which is completely deterministic. 214 00:19:02,860 --> 00:19:06,060 Before moving on to the statistical approach, 215 00:19:06,590 --> 00:19:12,360 please take a moment to download, run and modify the programs. 216 00:19:13,730 --> 00:19:16,220 On the Coursera website, 217 00:19:16,220 --> 00:19:20,390 you'll find the program event_disks_box.py 218 00:19:20,390 --> 00:19:24,390 which computes the time evolution 219 00:19:25,420 --> 00:19:30,390 and the program event_disks_box_movie.py 220 00:19:30,390 --> 00:19:37,210 which produced the nice graphic output that you saw all along this section. 221 00:19:38,730 --> 00:19:41,210 Check them out for yourself. 222 00:19:41,210 --> 00:19:46,000 Both the wall collisions and the pair collisions 223 00:19:46,000 --> 00:19:48,640 are programmed in a few lines, 224 00:19:49,540 --> 00:19:53,180 and there are absolutely no approximations 225 00:19:53,800 --> 00:19:58,650 besides the finite precision of our calculations. 226 00:20:04,470 --> 00:20:07,620 The event-driven molecular dynamics algorithm 227 00:20:07,620 --> 00:20:09,100 of the last section 228 00:20:09,600 --> 00:20:13,100 can be written down in a few dozens lines 229 00:20:13,100 --> 00:20:14,150 - as we saw - 230 00:20:14,800 --> 00:20:18,810 and it allows us to follow the ballet 231 00:20:18,810 --> 00:20:23,800 of disks approaching and flying away from each other, 232 00:20:23,800 --> 00:20:29,920 along intricate, even unpredictable trajectories. 233 00:20:31,060 --> 00:20:33,920 In doing so however, 234 00:20:33,920 --> 00:20:37,920 we engage on a computational project 235 00:20:37,920 --> 00:20:43,240 which is much more complicated than what we need. 236 00:20:44,810 --> 00:20:49,700 To continue, we again consider the configurations 237 00:20:49,700 --> 00:20:53,700 that we generated just a few moments ago. 238 00:20:54,140 --> 00:20:58,700 From a physical point of view, these configurations 239 00:20:58,700 --> 00:21:01,110 have kinetic energy 240 00:21:01,110 --> 00:21:05,110 - as we will discuss two weeks from now - 241 00:21:06,310 --> 00:21:12,350 but their potential energy is zero if they have no overlap, 242 00:21:12,900 --> 00:21:16,350 and is infinite if they have an overlap. 243 00:21:18,230 --> 00:21:20,620 Configurations with overlaps 244 00:21:20,620 --> 00:21:23,520 are simply forbidden. 245 00:21:24,090 --> 00:21:29,490 Ludwig Boltzmann - at the end of the 19th century - 246 00:21:29,490 --> 00:21:36,360 boldly conjectured that any configurations with the same energy 247 00:21:36,360 --> 00:21:40,360 also have the same probability to appear 248 00:21:42,400 --> 00:21:46,780 For hard disks, it is the quintessence 249 00:21:46,780 --> 00:21:49,980 of Boltzmann's statistical mechanics 250 00:21:49,980 --> 00:21:55,310 that all configurations a and b of hard disks 251 00:21:55,310 --> 00:22:01,040 have the same statistical weight pi(a)=pi(b). 252 00:22:02,780 --> 00:22:07,710 We already encountered this equation last week 253 00:22:07,710 --> 00:22:11,180 in our Monaco games 254 00:22:11,180 --> 00:22:16,080 and a and b were pebble positions. 255 00:22:17,390 --> 00:22:24,600 We sampled this pebble positions with a random number in x and a random number in y. 256 00:22:27,290 --> 00:22:34,530 Now, we generalize from the children's algorithm on the beach 257 00:22:35,510 --> 00:22:41,510 to a direct sampling Monte Carlo algorithm for hard disks. 258 00:22:43,730 --> 00:22:47,130 We first place the red disk 259 00:22:47,930 --> 00:22:54,760 as a random number in x between sigma (the radius) and 1-sigma 260 00:22:55,610 --> 00:23:00,250 and y: another random number between sigma and 1-sigma. 261 00:23:00,760 --> 00:23:04,680 The red disk has been placed at a random position. 262 00:23:06,510 --> 00:23:12,770 We do the same for the blue disk, the green disk and the yellow disk. 263 00:23:15,720 --> 00:23:18,740 Fantastic! Congratulations! 264 00:23:18,740 --> 00:23:24,060 We have placed the four disks at random positions. 265 00:23:24,880 --> 00:23:31,430 In total, we have produced a random configuration of the four disks, 266 00:23:31,430 --> 00:23:35,430 as called for by Ludwig Boltzmann. 267 00:23:36,570 --> 00:23:38,630 Let's do it again. 268 00:23:38,630 --> 00:23:44,210 Let's place the red disk at a new random position inside the box. 269 00:23:45,250 --> 00:23:51,500 Then the blue disk, then the green disk, ouch! 270 00:23:51,500 --> 00:23:57,390 We have generated an overlap. What should we do now? 271 00:23:59,670 --> 00:24:05,700 You might be tempted by simply taking away the green disk 272 00:24:05,700 --> 00:24:09,700 and trying to place it again 273 00:24:09,700 --> 00:24:12,230 but this is wrong. 274 00:24:13,260 --> 00:24:17,120 The correct solution is called 'tabula rasa' 275 00:24:17,370 --> 00:24:23,460 It consists in wiping out the whole configuration 276 00:24:23,990 --> 00:24:28,010 and in starting again from an empty box 277 00:24:28,010 --> 00:24:32,010 with the red, the blue, the green, the yellow disks 278 00:24:32,010 --> 00:24:34,120 until you succeed. 279 00:24:35,330 --> 00:24:40,360 We will spend a good part of this week's tutorial 280 00:24:40,780 --> 00:24:44,070 to make sure we completely understand 281 00:24:44,070 --> 00:24:48,070 why we have to implement the tabula rasa rule 282 00:24:48,070 --> 00:24:50,770 and why this allows us 283 00:24:50,770 --> 00:24:54,770 to sample a random configuration of hard disks. 284 00:24:57,230 --> 00:25:01,590 Before moving on, please take a moment 285 00:25:01,590 --> 00:25:07,720 to download, run and modify the programs. 286 00:25:08,950 --> 00:25:15,820 On the Coursera website, you'll find the program direct_disks_box.py 287 00:25:15,820 --> 00:25:20,210 that implements the direct sampling Monte Carlo algorithm. 288 00:25:21,990 --> 00:25:25,980 It samples one configuration of four disks 289 00:25:27,020 --> 00:25:32,690 its key element are the random positions in x 290 00:25:32,690 --> 00:25:37,630 and in y, between sigma and 1-sigma. 291 00:25:38,780 --> 00:25:43,600 Four times we generate such a random position 292 00:25:43,600 --> 00:25:47,600 and check for the minimum distance 293 00:25:47,600 --> 00:25:51,600 with the disks we placed earlier. 294 00:25:51,600 --> 00:25:55,940 If this minimum distance is smaller than (2 x sigma) 295 00:25:56,280 --> 00:26:01,620 - twice the radius - we know that we have an overlap. 296 00:26:02,780 --> 00:26:05,920 We then break out of the construction, 297 00:26:05,920 --> 00:26:08,870 and start again, from scratch. 298 00:26:09,380 --> 00:26:12,870 On the website, you also find the program 299 00:26:12,870 --> 00:26:16,220 direct_disks_box_multirun.py 300 00:26:16,220 --> 00:26:19,660 that generates many such configurations, 301 00:26:19,660 --> 00:26:25,410 and as usual the program direct_disks_box_movie.py, 302 00:26:25,410 --> 00:26:30,740 that generated nice graphics output that you see here. 303 00:26:32,330 --> 00:26:38,390 I can ensure you that the sequence of configurations that you see here 304 00:26:38,390 --> 00:26:45,260 is equivalent to the output of the molecular dynamics calculation 305 00:26:45,260 --> 00:26:52,510 if you erase time information, scramble the sequence 306 00:26:52,510 --> 00:26:56,510 and also erase the velocities. 307 00:26:57,220 --> 00:27:02,140 Then, these two sequences are equivalent 308 00:27:02,140 --> 00:27:07,920 and we have arrived at the center of statistical mechanics. 309 00:27:14,050 --> 00:27:20,540 Direct sampling for hard disks works only at low densities and for small particle numbers 310 00:27:20,540 --> 00:27:25,550 as we will discuss in detail in this week's tutorial 311 00:27:27,050 --> 00:27:34,860 To make progress, we move to the more general Markov chain Monte Carlo algorithm 312 00:27:36,400 --> 00:27:44,670 Let me first remind you of the algorithm markov_pi that we discussed last week 313 00:27:46,640 --> 00:27:51,560 From a configuration with position at (x,y) 314 00:27:51,560 --> 00:27:54,840 we moved to a configuration b 315 00:27:54,840 --> 00:28:00,610 by little moves delta_x and delta_y that could be positive or negative. 316 00:28:02,310 --> 00:28:04,950 Detailed balance imposed 317 00:28:04,950 --> 00:28:09,380 that the transition probability from a to b 318 00:28:09,710 --> 00:28:14,370 had to be equal to the transition probability from b to a 319 00:28:14,370 --> 00:28:18,370 in order to satisfy equiprobability 320 00:28:18,370 --> 00:28:22,370 pi(a) = pi(b). 321 00:28:22,770 --> 00:28:27,080 Let us now apply the same reasoning to hard disks. 322 00:28:28,060 --> 00:28:33,080 Consider here configuration a of four hard disks 323 00:28:33,810 --> 00:28:39,590 the move consists in picking one of the four disks - for example the blue disk - 324 00:28:41,120 --> 00:28:50,620 and making a little displacement delta_x and delta_y - that can be again positive or negative - to a configuration b. 325 00:28:51,570 --> 00:28:55,140 The detailed balance condition is satisfied 326 00:28:55,140 --> 00:28:59,140 - with pi(a)=pi(b) - 327 00:28:59,140 --> 00:29:03,460 if we move with the same probability from a to b 328 00:29:03,460 --> 00:29:06,510 as we move from b to a. 329 00:29:08,460 --> 00:29:16,770 It can also happen that the move from configuration a is rejected, as it creates an overlap. 330 00:29:18,200 --> 00:29:23,770 In that case, we remain at the configuration a for the next iteration. 331 00:29:26,850 --> 00:29:33,830 In Python this gives the following program markov_disks_box.py 332 00:29:33,830 --> 00:29:39,160 that you should download from the Coursera website, run and modify. 333 00:29:41,470 --> 00:29:47,130 The key element is the random choice of one disk 334 00:29:47,610 --> 00:29:51,130 whose coordinates we modify a little bit. 335 00:29:53,690 --> 00:29:57,430 The new configuration is tested for overlap 336 00:29:58,630 --> 00:30:02,000 and if two disks are getting too close 337 00:30:02,000 --> 00:30:05,290 or if we have an overlap with the wall 338 00:30:05,860 --> 00:30:09,290 we simply remain with the configuration a 339 00:30:09,290 --> 00:30:13,800 otherwise let's add the new configuration 340 00:30:14,580 --> 00:30:19,140 This precise algorithm for this model of hard disks 341 00:30:19,140 --> 00:30:23,140 was introduced by Metropolis et al. 342 00:30:23,140 --> 00:30:26,060 in a famous article of 1953. 343 00:30:27,000 --> 00:30:34,320 On the website you'll also find the program markov_disk_box_movie.py 344 00:30:34,320 --> 00:30:39,550 that produces nice graphics output shown here. 345 00:30:41,220 --> 00:30:47,200 You'll see that there are correlations between subsequent configurations 346 00:30:48,630 --> 00:30:53,630 and sometimes two subsequent configurations are identical 347 00:30:54,310 --> 00:31:00,490 This corresponds to piles of pebbles that we created the last week. 348 00:31:01,340 --> 00:31:08,310 This algorithm samples the same distribution as the direct_disks algorithm. 349 00:31:10,120 --> 00:31:14,460 As discussed in last week's tutorial by Vivien, 350 00:31:14,460 --> 00:31:19,170 we must check - in addition to the detailed balance condition - 351 00:31:19,170 --> 00:31:23,170 that we satisfy irreducibility 352 00:31:23,170 --> 00:31:25,090 and aperiodicity. 353 00:31:26,120 --> 00:31:30,810 Aperiodicity is trivial to check, for our algorithm 354 00:31:32,600 --> 00:31:36,060 but in order to satisfy irreducibility 355 00:31:36,710 --> 00:31:40,870 we must avoid situations as the one shown here 356 00:31:40,870 --> 00:31:47,790 where the blue disk remains in the upper right corner up to infinite times. 357 00:31:49,540 --> 00:31:53,520 For small systems, with a small number of particles, 358 00:31:53,520 --> 00:31:57,050 we must go to small disk radii 359 00:31:57,050 --> 00:32:01,470 as shown here where the disks move around the whole system 360 00:32:02,390 --> 00:32:06,230 But for larger system this is not a problem 361 00:32:07,010 --> 00:32:14,380 and the markov_disks algorithm remains irreducible up to very high densities. 362 00:32:20,410 --> 00:32:26,650 In this week's homework session, you will show - using numerical simulations - 363 00:32:26,650 --> 00:32:29,380 and up to the numerical precision 364 00:32:30,260 --> 00:32:34,090 that the event-driven molecular dynamics calculations 365 00:32:34,720 --> 00:32:42,220 and the Monte Carlo simulation give equivalent result for thermodynamic quantities. 366 00:32:44,070 --> 00:32:53,110 This means that the equiprobability hypothesis formulated by Boltzmann is satisfied. 367 00:32:54,580 --> 00:33:00,540 This equivalence between Newtonian deterministic mechanics 368 00:33:00,540 --> 00:33:06,090 and statistical mechanics is called the ergodicity hypothesis. 369 00:33:07,100 --> 00:33:10,910 It certainly does not follow from simple principles 370 00:33:10,910 --> 00:33:15,540 like time-reversal invariance or detailed balance. 371 00:33:16,210 --> 00:33:19,540 The proof of equiprobability 372 00:33:19,540 --> 00:33:24,200 has presented a formidable mathematical challenge. 373 00:33:25,850 --> 00:33:31,960 It was once believed to hold only in the limit of infinite number of particles. 374 00:33:34,060 --> 00:33:41,350 Mathematical research has gone very far in actually proving the ergodicity hypothesis 375 00:33:42,280 --> 00:33:50,260 for the special case of hard disks and hard spheres and already for finite number of particles. 376 00:33:52,320 --> 00:33:58,750 The first milestone was obtained by Sinai in 1970. 377 00:34:00,260 --> 00:34:05,490 He proved that for two disks with periodic boundary conditions 378 00:34:05,490 --> 00:34:08,950 the hypothesis was actually satisfied. 379 00:34:10,030 --> 00:34:16,260 Very recently, mathematicians like Simanyi have proven 380 00:34:16,260 --> 00:34:23,050 that a finite number number of hard disks have to satisfy the ergodicity hypothesis. 381 00:34:24,250 --> 00:34:33,970 So you can be sure that what you will do for your homework this week stands on very solid mathematical ground. 382 00:34:39,690 --> 00:34:47,190 In conclusion we have plunged, in Lecture 2 of Statistical Mechanics: Algorithms and Computations, 383 00:34:47,190 --> 00:34:51,190 into the foundations of statistical mechanics. 384 00:34:52,460 --> 00:34:55,190 The hard disk model that we have studied 385 00:34:55,190 --> 00:34:59,560 is special in that all legal configurations 386 00:34:59,560 --> 00:35:04,730 have the same potential energy and therefore the same statistical weight. 387 00:35:06,020 --> 00:35:13,010 This model has been instrumental for the development of statistical mechanics 388 00:35:13,010 --> 00:35:18,630 and also for the development of molecular dynamics 389 00:35:18,630 --> 00:35:21,710 and of the Monte Carlo method. 390 00:35:22,920 --> 00:35:30,410 Next week, we will study the very rich phenomenology of this model 391 00:35:30,410 --> 00:35:35,880 which is at the basis of the physics of liquids, among others. 392 00:35:37,730 --> 00:35:42,100 In the meantime, have fun with Tutorial 2 393 00:35:42,100 --> 00:35:45,130 and with this week's homework. 394 00:35:46,810 --> 00:35:51,710 It remains for me to thank you for your attention for this session 395 00:35:51,710 --> 00:35:57,120 See you again in other sessions of Statistical Mechanics: Algorithms and Computations.