1 00:00:03,210 --> 00:00:07,400 Hello, bonjour, selamat siang, gruezi, 2 00:00:07,840 --> 00:00:11,730 Welcome to the fifth, no sixth, no seventh.. 3 00:00:11,730 --> 00:00:17,510 well, to the seventh tutorial of Statistical Mechanics: Algorithms and Computations, 4 00:00:17,510 --> 00:00:20,880 from the Physics Department of Ecole Normale Supérieure. 5 00:00:20,880 --> 00:00:26,210 and to a final discussion of quantum statistical mechanics 6 00:00:27,020 --> 00:00:30,210 Our program today is twofold 7 00:00:30,560 --> 00:00:34,780 for once, we discussed in this week's lecture 8 00:00:34,780 --> 00:00:38,780 a 50-lines quantum Monte Carlo program 9 00:00:38,780 --> 00:00:43,030 that allowed us to observe Bose-Einstein condensation 10 00:00:43,030 --> 00:00:47,030 for 500 or 1000 bosons 11 00:00:47,030 --> 00:00:51,030 in a three-dimensional harmonic trap. But attention! 12 00:00:51,030 --> 00:00:55,530 Don't forget to wear your glasses, because of the many lasers 13 00:00:58,020 --> 00:01:00,330 As we lower the temperature 14 00:01:00,840 --> 00:01:03,020 all of a sudden 15 00:01:03,340 --> 00:01:08,290 the bosons clump together in the center of the trap 16 00:01:10,250 --> 00:01:15,400 very clearly, it was the permutations that provoked this transition 17 00:01:16,080 --> 00:01:19,880 because if we turn them off, like this, 18 00:01:20,840 --> 00:01:23,880 the effect simply disappears. 19 00:01:26,360 --> 00:01:31,160 Thus we understand that long permutation cycles 20 00:01:31,160 --> 00:01:35,160 play a key role in Bose-Einstein condensation 21 00:01:35,840 --> 00:01:39,330 but it's Michael who will provide the full story. 22 00:01:41,010 --> 00:01:45,460 He will derive a curious recursion relationship 23 00:01:45,460 --> 00:01:53,040 for the permutations of ideal bosons, that are equivalent to a theorem on random permutations. 24 00:01:54,160 --> 00:01:57,310 Alberto then will use this insight 25 00:01:57,310 --> 00:02:03,840 to construct a rejection-free direct sampling algorithm for ideal boson. 26 00:02:05,600 --> 00:02:10,190 Remember: in markov_harmonic_bosons.py 27 00:02:10,820 --> 00:02:16,760 we used a Markov chain algorithm to sample permutations, by trial and error 28 00:02:17,470 --> 00:02:19,790 but we can quite soon do better. 29 00:02:20,290 --> 00:02:23,790 But now, let's first listen to Michael 30 00:02:23,790 --> 00:02:27,790 explain to us how permutations really work. 31 00:02:34,990 --> 00:02:40,310 In this week's lecture, you saw that the appearance of long permutation cycles 32 00:02:40,310 --> 00:02:44,310 was the driving force behind Bose-Einstein condensation, 33 00:02:44,310 --> 00:02:48,310 let us look at this from yet another angle. 34 00:02:48,310 --> 00:02:52,310 Here, you see ten particles in one permutation cycle. 35 00:02:53,290 --> 00:02:58,750 We can now unwind them, by drawing the path of the first particle 36 00:02:59,470 --> 00:03:05,300 followed by a second particle, whose path starts where the first particle left off, 37 00:03:05,970 --> 00:03:10,110 then, by a third particle, a fourth particle, 38 00:03:10,110 --> 00:03:14,780 a fifth and a sixth and so on.. 39 00:03:15,580 --> 00:03:19,360 Finally, we have one particle of mass one 40 00:03:19,360 --> 00:03:25,190 at inverse temperature 10 beta, that is ten times lower temperature than T. 41 00:03:26,140 --> 00:03:33,460 Let us now focus on the analysis of permutation cycles without worrying too much about particles 42 00:03:34,050 --> 00:03:38,550 We consider random permutations as those generated by the program 43 00:03:38,550 --> 00:03:42,550 permutation_sample.py, in this week's lecture. 44 00:03:42,550 --> 00:03:46,550 We modify it a bit in order to look at the permutation cycles. 45 00:03:46,550 --> 00:03:51,800 This gives the program permutation_sample_cycle.py. 46 00:03:52,800 --> 00:03:56,280 Central element here is the use of dictionaries 47 00:03:56,950 --> 00:03:59,600 with the keys being the particles 48 00:03:59,600 --> 00:04:07,500 and the values being the permutations of the particles, that is their successor in the permutation cycle. 49 00:04:08,950 --> 00:04:18,150 So this is the output of permutation_sample_cycle.py for N=20, together with the length of permutation cycles. 50 00:04:18,150 --> 00:04:21,320 See, there are cycles of all lengths. 51 00:04:21,320 --> 00:04:25,320 We have 9, 11, 15, 6, 1, .. 52 00:04:25,320 --> 00:04:28,610 This is what we will now fully understand. 53 00:04:29,290 --> 00:04:35,640 For N=4, we already know that there are 4!=24 permutations. 54 00:04:35,640 --> 00:04:39,640 And we can analyze the permutation structure exactly. 55 00:04:40,890 --> 00:04:46,070 So here are the 24 permutations of the 4 particles. 56 00:04:46,620 --> 00:04:50,710 We want to compute their partition function, let's call it YN 57 00:04:51,220 --> 00:04:56,850 This is the sum over all permutations, if we give a weight to each permutation. 58 00:04:57,380 --> 00:05:01,870 If this weight is one, we are already done, because then YN 59 00:05:01,870 --> 00:05:08,330 simply equals N!, that is the number of possible permutations of N particles. 60 00:05:09,150 --> 00:05:14,990 Let us be a bit more general. We give a weight z1 to each cycle of length 1, 61 00:05:14,990 --> 00:05:18,990 a weight z2 to each cycle of length 2, 62 00:05:18,990 --> 00:05:20,000 and so on. 63 00:05:20,680 --> 00:05:25,770 So this permutation on the top has the weight z1 ^ 4 64 00:05:26,550 --> 00:05:33,570 this permutation has the weight z1^2 * z2, and so on.. 65 00:05:47,020 --> 00:05:50,220 Let us now pull apart 66 00:05:50,220 --> 00:05:55,890 the last element, together with its cycle: the last element cycle. 67 00:05:55,890 --> 00:06:05,100 This last element cycle involves k elements, n1, .., n(k-1) and the last element. 68 00:06:05,780 --> 00:06:12,110 And of course N - k elements do not belong to this last element cycle. 69 00:06:13,020 --> 00:06:19,280 Their partition function is Y_(N-k) and we know nothing about them. 70 00:06:21,290 --> 00:06:25,370 Y_N is computed from the number of choices k, 71 00:06:26,270 --> 00:06:29,370 the cycle weight z_k, 72 00:06:29,370 --> 00:06:35,220 the number of different sets n_1 to n_(k-1) (given k), 73 00:06:35,720 --> 00:06:42,380 the number of different cycles (given the set n_1, .., n_(k-1), n_N) 74 00:06:42,380 --> 00:06:45,330 and the partition function 75 00:06:45,330 --> 00:06:52,520 Y_(N-k) of the particles that do not participate in the last element cycle. 76 00:06:53,370 --> 00:06:59,700 It is easy to see that these different terms give for the number of different choices 77 00:06:59,700 --> 00:07:02,120 this combinatorial factor 78 00:07:02,120 --> 00:07:07,240 and the number of different cycles is( k-1)! 79 00:07:07,970 --> 00:07:11,460 This finally leads to the expression shown here. 80 00:07:20,660 --> 00:07:24,610 which is a recursion relation, as it allows us 81 00:07:24,610 --> 00:07:30,760 to compute Y_N from the smaller elements Y_0, .., Y_(N-1) 82 00:07:31,800 --> 00:07:35,970 If we set z_k=1 for all k 83 00:07:35,970 --> 00:07:39,080 we simply have the case of random permutations 84 00:07:39,080 --> 00:07:42,620 where Y_N = N! 85 00:07:42,620 --> 00:07:47,020 Y_(N-k) = (N-k)! 86 00:07:47,450 --> 00:07:52,240 then all terms on the right hand side of the equation are the same 87 00:07:52,240 --> 00:07:59,470 This means that the last element appears with the same probability in cycles of all lengths 88 00:07:59,470 --> 00:08:01,450 from 1 to N. 89 00:08:01,450 --> 00:08:07,430 To confirm this finding for the case N=4, simply count. 90 00:08:07,430 --> 00:08:12,370 Element 4 is in 6 cycles of length 4 91 00:08:12,370 --> 00:08:19,610 6 cycles of lengths 3, 6 cycles of lengths 2, and 6 cycles of lengths 1. 92 00:08:20,540 --> 00:08:24,730 In conclusion, we have seen a nice recursion formula 93 00:08:24,730 --> 00:08:29,210 that can be used to count permutations with arbitrary weights. 94 00:08:30,420 --> 00:08:33,950 Next, Alberto will apply this relation 95 00:08:33,950 --> 00:08:37,390 to bosons, but before listening to him 96 00:08:37,390 --> 00:08:42,600 please take a moment or two to download, run and modify the program 97 00:08:42,600 --> 00:08:45,780 permutation_sample_cycle.py 98 00:08:45,780 --> 00:08:49,240 with its characteristic use of dictionaries 99 00:08:49,240 --> 00:08:54,500 one of the key features of modern programming languages like Python. 100 00:08:58,860 --> 00:09:03,840 In this week's lecture, Werner already discussed that the partition function 101 00:09:03,840 --> 00:09:08,260 associated let's say with 4 bosons is given by 102 00:09:08,260 --> 00:09:12,260 one over 24, times the sum 103 00:09:12,260 --> 00:09:16,710 of the partition functions associated to the 24 permutations. 104 00:09:18,550 --> 00:09:26,350 Here for example the first permutation corresponds to z(beta)^4, 105 00:09:27,510 --> 00:09:32,220 and the second term has a partition function which is 106 00:09:32,220 --> 00:09:39,040 z(2 beta) z(beta)^2 107 00:09:39,040 --> 00:09:45,390 This corresponds to a cycle of length 2 and a pair of cycles of length 1. 108 00:09:45,390 --> 00:09:53,240 And then we have the third term, which has exactly the same partition function, the fourth term and so on. 109 00:09:56,840 --> 00:10:00,580 Of course, z(beta) 110 00:10:00,580 --> 00:10:03,680 is a number which is explicitly known, 111 00:10:03,680 --> 00:10:10,700 it is the partition function of a single particle inside a three-dimensional harmonic trap. 112 00:10:11,680 --> 00:10:15,600 In week 5 we have computed the partition function 113 00:10:15,600 --> 00:10:18,430 for a one-dimensional harmonic trap 114 00:10:19,230 --> 00:10:22,430 It was given by a geometric sum 115 00:10:22,430 --> 00:10:28,260 So in three dimensions we have now to multiply three times this geometric sum 116 00:10:28,260 --> 00:10:30,700 and this gives the following expression. 117 00:10:33,010 --> 00:10:36,100 So, for ideal bosons 118 00:10:36,100 --> 00:10:39,150 the N-particle partition function 119 00:10:39,150 --> 00:10:44,320 is just a sum of a product of single-particle partition functions. 120 00:10:44,820 --> 00:10:48,540 However, this sum is very non-trivial 121 00:10:48,540 --> 00:10:55,030 except for small N, where we can enumerate all the N! permutations. 122 00:10:55,030 --> 00:10:59,610 It is better to adapt the recursion formula introduced by Michael. 123 00:11:00,670 --> 00:11:05,100 Now, the weight of a cycle of length k 124 00:11:05,100 --> 00:11:09,100 is given by the single-particle partition function 125 00:11:09,100 --> 00:11:12,100 at the inverse temperature beta*k 126 00:11:12,600 --> 00:11:16,900 Taking into account that the partition function 127 00:11:16,900 --> 00:11:20,280 carries a factor of 1/N! 128 00:11:20,280 --> 00:11:25,060 we can reorganize the relation in this way. 129 00:11:27,340 --> 00:11:33,760 This recursion relation goes back to Landsberg in 1961. 130 00:11:34,290 --> 00:11:37,760 It relates the partition function 131 00:11:37,760 --> 00:11:41,760 of a system of N ideal bosons 132 00:11:41,760 --> 00:11:45,960 to the partition function of a single particle z 133 00:11:46,150 --> 00:11:52,190 and the partition functions Z of systems with fewer particles. 134 00:11:52,980 --> 00:11:56,310 So, we have arrived to an analytical solution 135 00:11:56,310 --> 00:11:59,740 that is implemented in the Python program 136 00:11:59,740 --> 00:12:04,580 canonic_harmonic_recursion.py for the partition function. 137 00:12:05,630 --> 00:12:07,410 Here you see 138 00:12:07,410 --> 00:12:09,710 that we have implemented 139 00:12:09,710 --> 00:12:18,400 the small z as the partition function of a single particle inside a three-dimensional harmonic trap, 140 00:12:18,400 --> 00:12:21,990 and note that we have shifted the ground-state 141 00:12:21,990 --> 00:12:28,310 so that the energy levels are E=0, E=1, E=2 and so on. 142 00:12:28,310 --> 00:12:32,310 But the method is very general. 143 00:12:32,310 --> 00:12:39,170 We pause for a moment, to gain a better understanding of this recursion relation. 144 00:12:39,740 --> 00:12:43,520 And remember: as discussed by Michael, 145 00:12:43,520 --> 00:12:48,300 each component refers to the last element cycle. 146 00:12:49,140 --> 00:12:53,820 So, the probability to find a particle n 147 00:12:53,820 --> 00:12:57,820 in a cycle of length k is given by this relation 148 00:12:59,890 --> 00:13:04,440 But the particle n is no way special, so this relation 149 00:13:04,440 --> 00:13:10,230 gives the probability to find any particle inside a cycle of length k. 150 00:13:11,100 --> 00:13:14,230 We can compute these probabilities 151 00:13:14,230 --> 00:13:19,930 by modifying the program canonic_harmonic_recursion.py 152 00:13:19,930 --> 00:13:23,930 as you see here for 1000 particles. 153 00:13:23,930 --> 00:13:29,190 In a harmonic trap at high temperature, only short cycles appear 154 00:13:29,650 --> 00:13:34,730 while at smaller temperature also longer cycles become probable. 155 00:13:35,370 --> 00:13:37,870 In the limit of zero temperature 156 00:13:37,870 --> 00:13:42,780 the probability of a single particle to belong to a cycle of length k 157 00:13:42,830 --> 00:13:45,570 becomes independent of k. 158 00:13:46,810 --> 00:13:53,140 The output for 1000 particles at different temperatures is shown here. 159 00:13:54,730 --> 00:13:57,140 In this week's homework 160 00:13:57,490 --> 00:14:01,880 you will produce this kind of figures from simulations 161 00:14:03,380 --> 00:14:11,160 It can be shown that the derivative of this function gives the distribution function of condensed particles. 162 00:14:12,400 --> 00:14:22,870 So, we have solved a physical problem: we can compute the partition function of N ideal bosons without any approximation. 163 00:14:23,590 --> 00:14:26,190 Does this ring a bell with you? 164 00:14:26,190 --> 00:14:32,540 Sure, we should have a rejection-free direct-sampling algorithm. 165 00:14:32,540 --> 00:14:38,600 And indeed we have. Thanks to the last equation, we can sample 166 00:14:38,600 --> 00:14:42,920 the permutation cycle associated with the last particle, 167 00:14:42,920 --> 00:14:49,160 and then continue again and again until we have nothing left. 168 00:14:50,350 --> 00:14:54,750 So, before continuing, please take a moment to download 169 00:14:54,750 --> 00:15:02,900 run and modify the program direct_harmonic_bosons.py that we discussed in this section. 170 00:15:03,960 --> 00:15:09,270 This is the last point of our development in quantum statistical mechanics. 171 00:15:09,740 --> 00:15:13,940 It is remarkable that for such an intricate problem 172 00:15:13,940 --> 00:15:16,820 we can write a rejection-free algorithm 173 00:15:16,820 --> 00:15:20,060 as if we were on the Monte Carlo beach. 174 00:15:24,350 --> 00:15:29,800 So in conclusion we have come in this tutorial to a clear understanding 175 00:15:29,800 --> 00:15:31,830 of random permutations 176 00:15:31,830 --> 00:15:35,830 and of their role in Bose-Einstein condensation. 177 00:15:37,300 --> 00:15:42,290 In Michael's list of 24 permutations, 178 00:15:42,290 --> 00:15:46,710 he was able to pull apart the last element 179 00:15:46,710 --> 00:15:49,050 and the last element cycle. 180 00:15:49,050 --> 00:15:54,690 And we were able to see that the last element 4 181 00:15:54,690 --> 00:15:58,690 was just as often in a cycle of length 4 182 00:15:58,690 --> 00:16:03,770 as in a cycle of length 3, or length 2, or length 1. 183 00:16:04,330 --> 00:16:07,550 We then used this insight 184 00:16:07,550 --> 00:16:09,580 on random permutations 185 00:16:09,580 --> 00:16:14,340 to understand cycle probabilities in the ideal Bose gas. 186 00:16:15,110 --> 00:16:21,620 And this allowed to compute the canonic partition function for ideal bosons. 187 00:16:22,310 --> 00:16:30,400 Once more, this analytical solution gave a great sampling algorithm that Alberto just presented. 188 00:16:30,820 --> 00:16:34,980 So it is now time to appropriate yourself 189 00:16:34,980 --> 00:16:39,960 of this great algorithm, to get your own Bose-Einstein condensate 190 00:16:39,960 --> 00:16:44,850 and most of all to have fun with homework session 7. 191 00:16:46,280 --> 00:16:50,620 And thanks to all of you for your attention 192 00:16:50,620 --> 00:16:57,000 and see you again next week at Statistical Mechanics: Algorithms and Computations.