1 00:00:03,620 --> 00:00:07,960 Hello, bonjour, ni hao, hola, 2 00:00:08,790 --> 00:00:14,320 welcome to the second week of Statistical Mechanics: Algorithms and Computations 3 00:00:14,320 --> 00:00:18,080 from the Physics department of Ecole Normale Superieure. 4 00:00:18,650 --> 00:00:23,310 This week's subject is the physics of hard disks. 5 00:00:24,200 --> 00:00:30,170 Remember, hard disks: two-dimensional idealization of billiard balls, 6 00:00:30,650 --> 00:00:34,170 not the hard disk in your computer. 7 00:00:35,060 --> 00:00:40,450 These hard disks - or at least their idealization - 8 00:00:40,800 --> 00:00:43,230 were studied with two approaches. 9 00:00:43,890 --> 00:00:51,910 Molecular dynamics, the solution of Newtonian deterministic mechanics, 10 00:00:52,800 --> 00:01:00,850 and Monte Carlo, the solution of Boltzmann statistical mechanics. 11 00:01:02,870 --> 00:01:05,730 As discussed in the lecture, 12 00:01:05,730 --> 00:01:13,070 for hard disks, Boltzmann statistical mechanics means equal weights 13 00:01:13,070 --> 00:01:17,070 for all legal configurations. 14 00:01:18,380 --> 00:01:23,780 We also discussed that Boltzmann and Newton 15 00:01:23,780 --> 00:01:27,780 are equivalent for all thermodynamic properties, 16 00:01:28,060 --> 00:01:33,210 that means for all properties that do not explicitly depend on time. 17 00:01:33,680 --> 00:01:39,880 In this tutorial, we will study direct sampling for hard disks. 18 00:01:41,200 --> 00:01:43,480 We will find out that 19 00:01:43,890 --> 00:01:51,340 although the program direct_disks.py is not a very powerful program 20 00:01:51,850 --> 00:01:56,700 it is a VIP, a very important program, 21 00:01:57,750 --> 00:02:05,150 as it contains important connections between physics and computation. 22 00:02:05,780 --> 00:02:07,490 In what follows, 23 00:02:08,080 --> 00:02:13,760 Michael will scrutinize the equal probability principle 24 00:02:13,980 --> 00:02:16,050 and the tabula rasa rule. 25 00:02:17,560 --> 00:02:22,090 Then Alberto will explain the profound link 26 00:02:22,090 --> 00:02:26,090 between computation and physics, 27 00:02:26,090 --> 00:02:29,570 or rather, between the acceptance probability 28 00:02:29,570 --> 00:02:32,420 of the direct sampling algorithm 29 00:02:32,420 --> 00:02:36,420 and the partition function of the physical system. 30 00:02:37,890 --> 00:02:43,690 Finally, Vivien will explore an analytical method 31 00:02:44,020 --> 00:02:47,130 for studying the hard disks system, 32 00:02:47,130 --> 00:02:48,710 the virial expansion. 33 00:02:51,100 --> 00:02:55,770 The virial expansion has existed a long time 34 00:02:55,770 --> 00:02:59,410 before numerical calculations became available. 35 00:03:00,860 --> 00:03:05,880 Ludwig Boltzmann himself, the founder of statistical mechanics 36 00:03:05,880 --> 00:03:10,610 wrote a famous paper in 1874 37 00:03:10,610 --> 00:03:14,610 on the virial expansion of the hard sphere system. 38 00:03:15,580 --> 00:03:22,520 So you see, we also keep to the center of the road of statistical mechanics. 39 00:03:28,880 --> 00:03:33,210 In this week's lecture, Lecture 2, Werner explained 40 00:03:33,330 --> 00:03:39,410 that the equiprobability principle is one of the pillars of statistical physics. 41 00:03:39,410 --> 00:03:44,740 This principle states that the probability pi(a) 42 00:03:44,930 --> 00:03:48,210 of a configuration is a function 43 00:03:48,210 --> 00:03:52,210 of the energy of the configuration, that is 44 00:03:52,870 --> 00:03:58,290 pi(a) equals pi of the energy of a. 45 00:03:59,150 --> 00:04:03,490 For hard disks, all allowed configurations 46 00:04:03,490 --> 00:04:06,990 have the same energy E=0. 47 00:04:07,350 --> 00:04:11,670 This gives the same statistical weight to each configuration 48 00:04:11,670 --> 00:04:15,820 pi(a) = pi(b) = pi(c). 49 00:04:17,720 --> 00:04:23,910 The Monte Carlo algorithm must sample these configurations with equal probability, 50 00:04:24,190 --> 00:04:29,480 this was achieved by the direct sampling Monte Carlo algorithm. 51 00:04:30,770 --> 00:04:35,730 Remember that the algorithm direct_disks_box.py 52 00:04:35,730 --> 00:04:40,660 first places one disk at a randomly chosen position 53 00:04:40,660 --> 00:04:45,270 inside the box, then a second one, then a third one, 54 00:04:45,560 --> 00:04:50,180 but in the case of an overlap applies the tabula rasa rule 55 00:04:50,480 --> 00:04:53,990 and wipes out the entire configuration, 56 00:04:53,990 --> 00:04:55,490 and starts afresh. 57 00:04:55,490 --> 00:04:59,490 But why don't we simply take the last disk 58 00:04:59,490 --> 00:05:01,690 (the one that caused the overlap) 59 00:05:01,690 --> 00:05:06,380 and try to put it a second time or a third time 60 00:05:06,380 --> 00:05:09,360 until it finally finds its place? 61 00:05:10,380 --> 00:05:15,120 This algorithm is called random sequential deposition, 62 00:05:15,230 --> 00:05:19,780 and it is important for adhesion and catalysis, 63 00:05:20,050 --> 00:05:24,670 but not for equilibrium statistical physics. 64 00:05:25,190 --> 00:05:29,490 Its configurations are not equally probable 65 00:05:29,490 --> 00:05:33,490 as we will now see, using two arguments. 66 00:05:33,880 --> 00:05:39,800 To do so, let us first consider a discrete hard rods model, 67 00:05:40,220 --> 00:05:44,970 a one dimensional discrete version of hard disks. 68 00:05:45,740 --> 00:05:47,580 On the line shown here, 69 00:05:47,700 --> 00:05:51,580 suppose that the rod centers 70 00:05:51,580 --> 00:05:57,390 can be placed on the sites 0, 1, 2, 3 and 4. 71 00:05:59,350 --> 00:06:03,330 Now assume that there also is an overlap condition, 72 00:06:03,330 --> 00:06:07,330 just like for the two-dimensional hard disks. 73 00:06:07,330 --> 00:06:12,700 We say that two adjacent rod centers 74 00:06:12,710 --> 00:06:15,580 must differ by at least three, 75 00:06:15,590 --> 00:06:20,340 this means that there must be at least two free sites 76 00:06:20,340 --> 00:06:24,340 in between two adjacent rods. 77 00:06:24,900 --> 00:06:30,780 For example we cannot place rods on the sites 0 and 2, 78 00:06:30,780 --> 00:06:36,900 but there's no problem to place them on the sites 1 and 4. 79 00:06:38,560 --> 00:06:43,670 Let us do a simple simulation of random sequential deposition, 80 00:06:43,670 --> 00:06:47,670 where we impose that we end up with two rods: 81 00:06:47,830 --> 00:06:50,450 the red rod and the blue rod. 82 00:06:51,540 --> 00:06:56,720 We place the red rod, then we place the blue rod, 83 00:06:57,860 --> 00:07:01,530 but we have to pull it off again because there's an overlap 84 00:07:01,530 --> 00:07:05,740 and we put it again, we pull it off again, we put it again 85 00:07:05,860 --> 00:07:07,630 until we succeed. 86 00:07:09,740 --> 00:07:12,410 Here you can see a second simulation. 87 00:07:16,940 --> 00:07:19,540 We now analyze the algorithm: 88 00:07:19,540 --> 00:07:22,980 we first place the red rod 89 00:07:22,980 --> 00:07:26,030 and it'll fall with the probability of 1/5 90 00:07:26,030 --> 00:07:30,030 on any of the sites 0, 1, 2, 3, 4. 91 00:07:30,880 --> 00:07:34,030 Rather, with a probability of 1/4 92 00:07:34,030 --> 00:07:38,030 because there is no two-disks configuration 93 00:07:38,030 --> 00:07:42,030 with one of the disks on site 2. 94 00:07:43,100 --> 00:07:48,280 Now, if the red rod is on site 0, 95 00:07:49,320 --> 00:07:53,580 the blue rod can be placed with a probability of 1/2 96 00:07:53,580 --> 00:07:58,590 on the sites 3 and 4. 97 00:07:59,830 --> 00:08:04,250 This gives the allowed configurations a and b. 98 00:08:04,250 --> 00:08:10,540 The same reasoning is valid for the configurations e and f. 99 00:08:11,240 --> 00:08:14,020 These four allowed configurations 100 00:08:14,020 --> 00:08:19,190 have the probability 1/4 times 1/2, 101 00:08:19,580 --> 00:08:21,550 equal 1/8. 102 00:08:22,260 --> 00:08:26,090 In contrast, if the red rod is placed 103 00:08:26,090 --> 00:08:30,090 either on site 1 or on site 3, 104 00:08:30,090 --> 00:08:34,090 there's only one site left 105 00:08:34,090 --> 00:08:36,110 for the blue rod to go. 106 00:08:36,430 --> 00:08:40,950 This leads to the configurations c and d, 107 00:08:42,580 --> 00:08:50,260 which have the probabilities 1/4 times 1, equals to 1/4. 108 00:08:51,090 --> 00:08:56,330 Clearly, we have violated the equiprobability principle. 109 00:08:58,280 --> 00:09:03,800 What would happen if we apply - instead of random sequential deposition - 110 00:09:03,800 --> 00:09:08,980 the tabula rasa strategy of the Monte Carlo algorithm? 111 00:09:09,630 --> 00:09:14,330 In Python, this would give the program shown here 112 00:09:14,330 --> 00:09:18,330 as you will discover in the following little quiz. 113 00:09:19,040 --> 00:09:22,980 Question 1: how many configurations 114 00:09:22,980 --> 00:09:25,560 (legal and illegal ones) 115 00:09:25,560 --> 00:09:33,350 of red and blue rods can be generated by the program direct_discrete.py? 116 00:09:39,600 --> 00:09:42,410 The answer is 25, 117 00:09:42,410 --> 00:09:49,650 as there are five positions for the red rod and five positions for the blue rod to be placed. 118 00:09:50,790 --> 00:09:52,740 Question 2: 119 00:09:53,160 --> 00:09:59,500 how many legal configurations are among these 25 configurations? 120 00:09:59,720 --> 00:10:04,360 Remember that there must be at least two free sites 121 00:10:04,360 --> 00:10:08,360 in between the centers of the red and the blue rods. 122 00:10:15,160 --> 00:10:20,190 The answer is 6, as only the 6 configurations 123 00:10:20,190 --> 00:10:24,670 a, b, c, d, e and f (that we discussed earlier) 124 00:10:24,670 --> 00:10:28,670 survive the tabula rasa wipe out. 125 00:10:28,670 --> 00:10:30,380 Question 3: 126 00:10:30,380 --> 00:10:35,380 what is the probability of the legal configurations a,...,f? 127 00:10:42,880 --> 00:10:46,830 The legal configurations a,...,f have the probabilities 128 00:10:46,830 --> 00:10:52,890 pi(a) = pi(b) = .. = 1/6. 129 00:10:53,780 --> 00:10:56,890 The direct sampling Monte Carlo algorithm 130 00:10:56,890 --> 00:11:02,060 generates the 25 legal and illegal configurations 131 00:11:02,060 --> 00:11:06,060 with equal probabilities 1/25. 132 00:11:06,060 --> 00:11:10,130 The legal configurations a,..,f have 133 00:11:10,130 --> 00:11:14,130 equal probabilities before the tabula rasa wipe out 134 00:11:14,290 --> 00:11:18,440 and consequently have equal probability after. 135 00:11:19,920 --> 00:11:24,210 The argument we just used for the discrete model 136 00:11:24,210 --> 00:11:28,210 applies also for the four hard disks 137 00:11:28,210 --> 00:11:32,210 in the two dimensional box, if we reprogram 138 00:11:32,210 --> 00:11:36,210 direct_disks_box.py 139 00:11:36,210 --> 00:11:42,050 so that it places the four disks at randomly chosen positions 140 00:11:42,050 --> 00:11:46,050 without checking for an overlap. 141 00:11:46,050 --> 00:11:52,040 Now, there's no doubt that these four disks configurations 142 00:11:52,040 --> 00:11:57,760 are uniformly distributed, in an eight-dimensional space 143 00:11:57,760 --> 00:12:01,900 as we have two coordinates (namely x and y) 144 00:12:02,070 --> 00:12:05,550 for each of the four hard disks. 145 00:12:05,550 --> 00:12:09,550 In fact, as we do not check for overlaps, 146 00:12:09,550 --> 00:12:13,550 each point in this eight-dimensional space 147 00:12:13,550 --> 00:12:17,550 is sampled with equal probability. 148 00:12:17,550 --> 00:12:22,220 It is only after we have generated all these configurations 149 00:12:22,220 --> 00:12:24,790 that we cut out pieces. 150 00:12:25,900 --> 00:12:28,790 In this program, the vector L 151 00:12:28,790 --> 00:12:34,220 is a uniform random vector in an eight-dimensional hypercube 152 00:12:34,220 --> 00:12:39,200 from sigma to (1-sigma) in all dimensions. 153 00:12:40,530 --> 00:12:44,030 We then cut out pieces from this hypercube 154 00:12:44,030 --> 00:12:47,010 with the overlap condition. 155 00:12:47,010 --> 00:12:51,190 This is like in the discrete model, where we threw away 156 00:12:51,190 --> 00:12:55,190 19 of the 25 configurations. 157 00:12:55,800 --> 00:13:01,460 In the next section, Alberto will deepen our understanding 158 00:13:01,460 --> 00:13:04,180 of the eight-dimensional space picture 159 00:13:04,180 --> 00:13:08,180 for hard disks, but no longer with walls, 160 00:13:08,180 --> 00:13:13,970 but with periodic boundary condition in the x and y directions. 161 00:13:15,560 --> 00:13:18,900 Before following these exciting developments 162 00:13:18,900 --> 00:13:23,690 you should download, run and modify the relevant programs. 163 00:13:23,690 --> 00:13:27,780 On the Coursera website, you will find programs 164 00:13:27,780 --> 00:13:29,710 for the discrete rods model. 165 00:13:29,710 --> 00:13:35,080 First, the program for sequential random deposition 166 00:13:35,260 --> 00:13:39,520 which also outputs a nice histogram, and as usual 167 00:13:39,520 --> 00:13:44,120 also a random sequential deposition program with nice graphics. 168 00:13:44,560 --> 00:13:51,750 You can also find the program for direct sampling of the four hard disks in the box, 169 00:13:51,750 --> 00:13:55,750 if you have not already downloaded it in Lecture 2. 170 00:13:56,610 --> 00:13:59,750 And even the slower program 171 00:13:59,750 --> 00:14:05,990 which first samples all the positions, and checks for overlaps only in the end. 172 00:14:05,990 --> 00:14:09,260 Make sure that you understand 173 00:14:09,260 --> 00:14:14,840 that direct_disks_box and direct_disks_box_slow 174 00:14:14,840 --> 00:14:21,410 are statistically speaking strictly identical in their output. 175 00:14:26,440 --> 00:14:29,840 Let's move to direct sampling of hard disks 176 00:14:29,840 --> 00:14:31,890 with periodic boundary conditions. 177 00:14:31,890 --> 00:14:34,440 As you can see here, 178 00:14:34,440 --> 00:14:38,440 when a disk is close to the right hand side 179 00:14:38,440 --> 00:14:42,440 of the box, it will appear also on the left hand side 180 00:14:42,440 --> 00:14:45,670 of the box. If you have two disks 181 00:14:45,670 --> 00:14:49,670 they overlap not only if they're close together 182 00:14:49,670 --> 00:14:56,150 but also if for example one disk is on the lower right corner 183 00:14:56,150 --> 00:15:00,150 and the other disk is in the upper right corner 184 00:15:00,400 --> 00:15:05,640 In a system with periodic boundary conditions, walls play no role 185 00:15:06,750 --> 00:15:11,750 Here we show the multirun Python version with periodic boundary conditions. 186 00:15:12,740 --> 00:15:15,750 Many legal configurations are generated 187 00:15:16,410 --> 00:15:20,020 Check out for yourself that the function dist() 188 00:15:20,020 --> 00:15:24,020 correctly implements the periodic boundary conditions. 189 00:15:25,160 --> 00:15:28,220 Now we consider more than four disks. 190 00:15:28,220 --> 00:15:34,110 Let's say N=16 disks, and we fix also the density eta, 191 00:15:34,110 --> 00:15:38,110 which is the fraction of space occupied by disks. 192 00:15:39,730 --> 00:15:42,110 Here, we show the output 193 00:15:42,110 --> 00:15:45,310 for a density eta=0.3, 194 00:15:45,310 --> 00:15:50,160 only 30% of the space is occupied by disks. 195 00:15:51,080 --> 00:15:54,680 For our box of side 1, 196 00:15:54,680 --> 00:15:59,610 the radius of the hard disks can be obtained by the relation 197 00:15:59,610 --> 00:16:03,610 16 x pi x sigma^2 198 00:16:03,610 --> 00:16:05,780 equal to 0.3. 199 00:16:06,150 --> 00:16:08,240 Something chilling is happening: 200 00:16:08,470 --> 00:16:14,010 we typically have to wipe off our table 100000 times 201 00:16:14,010 --> 00:16:17,080 before having a single legal configuration. 202 00:16:17,080 --> 00:16:21,080 This means that our algorithm is exact 203 00:16:21,080 --> 00:16:25,790 but is very bad, because the acceptance ratio is very small. 204 00:16:26,750 --> 00:16:32,460 For a system of 16 disks with a density of 0.3 205 00:16:33,150 --> 00:16:38,880 the acceptance ratio is of the order of 5 x 10^(-6). 206 00:16:39,860 --> 00:16:43,150 Michael spoke a few minutes ago 207 00:16:43,150 --> 00:16:47,990 about the eight-dimensional space of configurations of four disks 208 00:16:48,660 --> 00:16:52,930 These configurations are described by the eight coordinates of the disks 209 00:16:52,930 --> 00:17:00,010 (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4). 210 00:17:00,830 --> 00:17:07,350 Here we have 16 disks, which means that the dimension of the space is 32 211 00:17:08,520 --> 00:17:14,560 Furthermore, if our box has a volume (or an area) equal to V 212 00:17:15,370 --> 00:17:20,390 the 32-dimensional space has a volume V^16 213 00:17:20,390 --> 00:17:24,730 or V^N, where N is the number of disks. 214 00:17:26,380 --> 00:17:33,710 If the system has a density equal to zero, which means that the radius of the hard disks is equal to zero, 215 00:17:33,710 --> 00:17:39,740 all the points of the configurational space are legal configurations. 216 00:17:39,740 --> 00:17:45,690 So the number of legal configurations, which is the partition function of the system, 217 00:17:45,690 --> 00:17:52,500 is V^N. At density 0, the acceptance ratio is 1. 218 00:17:53,730 --> 00:17:56,590 We found that at density 0.3 219 00:17:56,590 --> 00:18:01,390 the acceptance ratio is 5 x 10^(-6). 220 00:18:01,390 --> 00:18:05,630 This means that the number of legal configurations 221 00:18:05,630 --> 00:18:09,720 is 200000 smaller than the volume 222 00:18:09,720 --> 00:18:13,720 of the original 32-dimensional space (V^N). 223 00:18:15,420 --> 00:18:19,110 The number of legal configurations at density eta 224 00:18:19,110 --> 00:18:23,110 - which is the partition function of the hard disks - 225 00:18:23,110 --> 00:18:28,130 is equal to the product of the partition function at density 0 226 00:18:28,130 --> 00:18:32,130 times the acceptance ratio at density eta. 227 00:18:32,630 --> 00:18:37,890 The partition function is a central object in equilibrium statistical mechanics 228 00:18:37,890 --> 00:18:42,690 and is a central object in Statistical Mechanics: Algorithms and Computations. 229 00:18:43,500 --> 00:18:47,880 In a few moments, Vivien will discuss this in more details. 230 00:18:48,370 --> 00:18:51,340 and will provide an approach (an analytical approach) 231 00:18:51,340 --> 00:18:55,940 to compute the acceptance ratio and the partition function 232 00:18:55,940 --> 00:18:59,940 for hard disks. 233 00:19:01,170 --> 00:19:07,580 Before doing this, please take a moment to download, run and modify 234 00:19:07,580 --> 00:19:10,540 the programs we discussed in this section 235 00:19:10,540 --> 00:19:14,800 On the Coursera website, you will find the algorithm 236 00:19:14,800 --> 00:19:18,140 for direct sampling with periodic boundary conditions. 237 00:19:18,950 --> 00:19:23,370 This algorithm allows you to pick out legal configurations 238 00:19:23,370 --> 00:19:27,770 from the hypercube of dimension V^N. 239 00:19:29,260 --> 00:19:33,330 These configurations are as rare as diamonds, 240 00:19:33,330 --> 00:19:37,330 and if you wish they are almost as beautiful. 241 00:19:38,460 --> 00:19:43,980 Note that all coordinates are now random numbers between 0 and 1 242 00:19:44,320 --> 00:19:47,610 because no wall has to be considered. 243 00:19:48,470 --> 00:19:53,970 You can inspect these legal configurations, the diamonds of statistical physics 244 00:19:53,970 --> 00:19:57,970 using, as usual, the graphic version of the program. 245 00:20:03,190 --> 00:20:07,170 Let us go one step further and determine the acceptance ratio 246 00:20:07,170 --> 00:20:12,330 of the direct sampling algorithm at any density eta. 247 00:20:13,080 --> 00:20:18,180 You may be tempted to run the program direct_disks_multirun 248 00:20:18,180 --> 00:20:24,900 for several runs and maybe on many computers for different values of eta. 249 00:20:25,620 --> 00:20:31,950 But I'd rather look at the following configuration of N=16 points 250 00:20:31,950 --> 00:20:35,060 in a box with periodic boundary conditions. 251 00:20:35,060 --> 00:20:39,740 At zero density, that is to say for zero radius 252 00:20:39,740 --> 00:20:43,740 it clearly leads to a valid configuration of hard disks 253 00:20:43,740 --> 00:20:50,540 and this is also the case for a density equal to 0.0001 254 00:20:51,530 --> 00:20:56,360 In contrast, at higher density the radius is larger, 255 00:20:56,360 --> 00:21:02,400 and the points lead to a configuration of hard disks which is illegal. 256 00:21:05,460 --> 00:21:09,280 In fact, from these 16 points in the box 257 00:21:09,280 --> 00:21:13,280 you can obtain a hard disks configuration 258 00:21:13,280 --> 00:21:17,280 for all values of the radius which are smaller 259 00:21:17,280 --> 00:21:25,120 than the maximal radius, equal to half of the minimal distance between two of these points. 260 00:21:25,500 --> 00:21:36,430 In this present configuration, the value sigma_max of this maximal radius is equal to 0.025 261 00:21:36,430 --> 00:21:44,690 and it corresponds to a maximal density eta_max = 0.03143 262 00:21:45,630 --> 00:21:51,160 You may consider the probability distribution p(eta_max) 263 00:21:51,160 --> 00:21:55,160 associated to this maximal density 264 00:21:55,160 --> 00:21:59,160 and from it - as displayed on this formula - 265 00:21:59,160 --> 00:22:05,390 you can reconstitute the probability distribution pi_accept(eta) 266 00:22:05,390 --> 00:22:10,260 of the acceptance ratio of the direct sampling algorithm. 267 00:22:11,040 --> 00:22:17,130 You can find this formula on the fact-sheet associated to this class session. 268 00:22:18,440 --> 00:22:21,550 For 16 disks you obtain the following graph 269 00:22:21,550 --> 00:22:25,550 which has been obtained from a few millions realizations of the program. 270 00:22:26,810 --> 00:22:30,930 It describes the acceptance rate as a function of the density eta 271 00:22:30,930 --> 00:22:36,420 and you observe that it decays faster than exponentially with eta. 272 00:22:37,360 --> 00:22:41,700 We will now obtain an analytical approximation 273 00:22:41,700 --> 00:22:46,930 of the acceptance rate and of the partition function of hard disks. 274 00:22:47,300 --> 00:22:52,890 It will be excellent in the limit of small densities, and valid for any value of N 275 00:22:53,600 --> 00:22:58,140 To do so, let's consider the following N=16 276 00:22:58,140 --> 00:23:02,140 points in the box with periodic boundary conditions 277 00:23:02,140 --> 00:23:06,480 This configuration is described by the set of vectors 278 00:23:06,480 --> 00:23:10,480 x_0, x_1, .., x_(N-1) 279 00:23:10,910 --> 00:23:17,610 each of these vectors contains the two spatial coordinates of the point, x and y. 280 00:23:18,920 --> 00:23:26,490 For relatively small radius, this configuration will be allowed 281 00:23:26,490 --> 00:23:31,800 In general this configuration will be valid provided that the distances 282 00:23:31,800 --> 00:23:40,410 between disk 0 and disk 1, disk 0 and disk 2 up to N-1 and N-2 283 00:23:40,410 --> 00:23:44,410 are all larger than 2 sigma. 284 00:23:44,730 --> 00:23:48,410 If one of these conditions is not valid, 285 00:23:48,410 --> 00:23:51,470 then the configuration is illegal. 286 00:23:52,030 --> 00:23:58,420 Following Alberto a few minutes ago, we will rewrite this condition in integral form, as follows. 287 00:24:04,540 --> 00:24:10,640 This integral runs over the 2 N components of the N vectors of the configuration 288 00:24:10,640 --> 00:24:17,130 and Upsilon is equal to 1 if there is an overlap, and 0 otherwise. 289 00:24:18,620 --> 00:24:24,530 It is important to note that if one of these brackets is equal to zero 290 00:24:24,530 --> 00:24:29,470 then the contribution of the configuration vanishes in the integral 291 00:24:30,570 --> 00:24:38,270 This expression of the partition function is exact, but no one has been able to compute it analytically. 292 00:24:39,900 --> 00:24:44,450 Let's consider all the brackets, each of them is equal to 293 00:24:44,450 --> 00:24:48,450 1 if there is no overlap, and 0 otherwise. 294 00:24:49,130 --> 00:24:53,980 We can expand and multiply out all these brackets 295 00:24:53,980 --> 00:24:59,650 For instance if one picks the ones in each of these brackets 296 00:24:59,650 --> 00:25:04,770 and then one computes the integral, one obtains V^N. 297 00:25:05,260 --> 00:25:10,500 This is in fact the partition function - as Alberto showed - 298 00:25:10,500 --> 00:25:17,610 of the ideal gas of hard disks of radius equal to zero. 299 00:25:18,800 --> 00:25:22,970 To go to the next order, let's consider all the brackets 300 00:25:22,970 --> 00:25:28,680 there are (N-1)N/2 of them, 301 00:25:28,680 --> 00:25:33,950 so what you can do is to pick one of the Upsilon 302 00:25:34,610 --> 00:25:40,210 in a single term, and to pick one in all the other brackets. 303 00:25:41,130 --> 00:25:47,220 Doing so, you obtain a four dimensional integral, which is displayed here. 304 00:25:47,650 --> 00:25:56,060 Thanks to the invariance by translation and the periodic boundary condition, it reduces to V times a two-dimensional integral. 305 00:25:57,020 --> 00:26:04,180 We observe - as displayed in this figure - that the excluded region corresponds to a disk of radius 2sigma. 306 00:26:04,610 --> 00:26:08,450 This allows to compute the integral as follows. 307 00:26:10,340 --> 00:26:14,800 Now, we can come back to the full expression of the partition function, 308 00:26:14,800 --> 00:26:18,800 and if we stop the evaluation at this term 309 00:26:18,800 --> 00:26:21,190 we obtain the following expression. 310 00:26:21,880 --> 00:26:25,860 For large N, it behaves as V^N 311 00:26:25,860 --> 00:26:31,120 times the exponential of - (N-1) times eta. 312 00:26:32,730 --> 00:26:42,520 This means that the acceptance probability decays exponentially with both the density and the number N of particles. 313 00:26:42,790 --> 00:26:49,410 Remember that we have a computer program called direct_disks_any.py, 314 00:26:49,410 --> 00:26:54,160 which allows to evaluate numerically the acceptance rate. 315 00:26:54,460 --> 00:27:00,330 We can thus compare it to our prediction, and this is displayed on the following picture 316 00:27:01,360 --> 00:27:06,260 As you observe the analytical prediction matches very well 317 00:27:06,260 --> 00:27:10,260 the numerical results in the low density regime. 318 00:27:11,090 --> 00:27:16,860 Let's now remark that the partition function is proportional to V^N 319 00:27:18,050 --> 00:27:24,470 To obtain an extensive quantity, in physics we take the logarithm of this quantity 320 00:27:24,470 --> 00:27:27,670 and you obtain the following result. 321 00:27:28,470 --> 00:27:34,110 Let us now explain why it corresponds to a virial expansion. 322 00:27:34,840 --> 00:27:44,100 To do so, we can first differentiate log(Z(eta)) with respect to V 323 00:27:44,560 --> 00:27:48,100 and then multiply by V/N. 324 00:27:48,830 --> 00:27:52,100 You obtain the following expression 325 00:27:52,970 --> 00:27:56,100 the first term is a constant equal to 1 326 00:27:56,100 --> 00:28:01,890 and it corresponds to the partition function V^N 327 00:28:01,890 --> 00:28:09,810 of the ideal hard disks gas of radius zero, that Alberto explained. 328 00:28:10,660 --> 00:28:14,720 The next term is proportional to 1/V 329 00:28:15,590 --> 00:28:25,510 In fact, we obtain this term in 1/V because we consider only the term with one Upsilon in the expansion. 330 00:28:26,100 --> 00:28:33,980 We could go on in this expansion of the brackets and consider pairs of Upsilon, triplets and so on 331 00:28:34,710 --> 00:28:42,190 This would yield an expansion - as previously - in powers of 1/V 332 00:28:44,120 --> 00:28:50,870 However, this is not the state of the art of statistical mechanics for the 21st century. 333 00:28:50,870 --> 00:29:00,030 Indeed, Ludwig Boltzmann in 1874 computed the 4th term of the virial expansion, 334 00:29:00,030 --> 00:29:04,030 that is to say the term in 1/V^3. 335 00:29:04,030 --> 00:29:08,030 It was for three-dimensional hard spheres. 336 00:29:08,030 --> 00:29:11,230 This computation was really complicated, 337 00:29:11,230 --> 00:29:18,490 it was subject to years of debate, but in the end he was right and others were not. 338 00:29:18,490 --> 00:29:29,350 The virial expansion was once believed to provide a systematic access to the thermodynamics of liquids and gases, in our case hard disks. 339 00:29:29,350 --> 00:29:34,510 In the same as the expansion of the exponential function 340 00:29:34,510 --> 00:29:42,720 exp(x) = 1 + x + x^2/2 + x^3/6 and so on. 341 00:29:43,770 --> 00:29:49,640 This expansion is valid for all values of x, real or complex. 342 00:29:50,540 --> 00:29:55,140 However, for the virial expansion this is not the case any more. 343 00:29:56,500 --> 00:30:00,160 What is proven today is that this expansion is valid 344 00:30:00,160 --> 00:30:05,000 only up to some finite values of the density eta. 345 00:30:05,760 --> 00:30:11,630 However it cannot predict the existence of a phase transition. 346 00:30:12,740 --> 00:30:16,210 Those phase transitions will be the subject of our next week. 347 00:30:17,870 --> 00:30:24,150 Now, please, download run and modify the programs we have seen during this session. 348 00:30:24,840 --> 00:30:29,810 You may also have a look to the fact-sheet that corresponds to the computation 349 00:30:29,810 --> 00:30:33,810 of the virial expansion we have just seen. 350 00:30:34,420 --> 00:30:40,530 On the Coursera website you may also have a look on the following program. 351 00:30:41,360 --> 00:30:43,620 It is sweet and short, 352 00:30:43,620 --> 00:30:50,010 it allows to determine the acceptance ratio for any density eta. 353 00:30:51,170 --> 00:30:54,010 Have fun going through this 354 00:30:55,460 --> 00:31:01,260 those are 15 lines, but not easy to understand. 355 00:31:01,260 --> 00:31:05,470 In conclusion, we have moved in this tutorial 356 00:31:05,470 --> 00:31:15,790 from the tabula rasa rule to the discussion of the high-dimensional abstract spaces of our hard disk configurations. 357 00:31:17,140 --> 00:31:26,560 We moved towards the center of statistical physics: the partition function and the virial expansion. 358 00:31:28,420 --> 00:31:32,190 Our discussion revealed a beautiful connection 359 00:31:32,190 --> 00:31:37,200 between algorithms and the physical description of our systems. 360 00:31:38,120 --> 00:31:42,750 But our analytical approach remained perturbative. 361 00:31:43,700 --> 00:31:46,750 This is a true limitation 362 00:31:47,330 --> 00:32:00,340 We will see next week that our algorithms have the potential to carry us beyond this horizon and this limitation of the perturbative approach 363 00:32:01,420 --> 00:32:05,900 This will allow us to study phase transitions, 364 00:32:07,170 --> 00:32:12,020 when the liquid of hard disks becomes solid, 365 00:32:12,020 --> 00:32:17,270 and this is a major revolution in physics. 366 00:32:18,910 --> 00:32:24,650 In the meantime, have fun with the homework session of this week 367 00:32:24,650 --> 00:32:31,490 and see you again next week at Statistical Mechanics: Algorithms and Computations.