1 00:00:03,700 --> 00:00:09,517 Next we're going to talk about an intricate extension of the asymptotic 2 00:00:09,517 --> 00:00:15,172 techniques that we're looking at, where there's two variables involved. 3 00:00:15,172 --> 00:00:19,777 And these arise frequently in the analysis of algorithms. 4 00:00:19,777 --> 00:00:23,130 So. In a lot of times in the study of 5 00:00:23,130 --> 00:00:28,007 algorithms we have two variables that we are working with. 6 00:00:28,007 --> 00:00:32,800 One is the size of the problem and the other is the cost. 7 00:00:32,800 --> 00:00:39,694 so we're going to wind up with intricate expressions that are involved with those 8 00:00:39,694 --> 00:00:43,983 two variables and they might vary independently. 9 00:00:43,983 --> 00:00:49,404 So, we have some definite challenges. The problem is as I indicated when 10 00:00:49,404 --> 00:00:55,014 talking about doing sums is that, the relative values of the variables, might 11 00:00:55,014 --> 00:00:58,434 matter. and that makes it even more challenging 12 00:00:58,434 --> 00:01:02,607 to, deal with sums over the whole range of relative values. 13 00:01:02,607 --> 00:01:07,533 and you'll see what this means when I get to some applications. 14 00:01:07,533 --> 00:01:12,869 fortunately as was the case with the harmonic numbers and sterling numbers 15 00:01:12,869 --> 00:01:18,684 where, there's a couple of fundamental functions that, arise over and over again 16 00:01:18,684 --> 00:01:23,916 that take most of the work. similar is true of functions of two 17 00:01:23,916 --> 00:01:27,634 variables. There's a couple of fundamental functions 18 00:01:27,634 --> 00:01:31,081 that arise. and we'll look at the aymptotics of 19 00:01:31,081 --> 00:01:34,190 those. and they are, are the ones that arise 20 00:01:34,190 --> 00:01:37,435 most often. And if it's not that function it's a 21 00:01:37,435 --> 00:01:42,978 function that similar that we can model the analysis on the analysis that have 22 00:01:42,978 --> 00:01:47,033 developed, been developed classically for these functions. 23 00:01:47,033 --> 00:01:50,548 so first example is the binomial distribution. 24 00:01:50,548 --> 00:01:54,807 again that's okay. Might be related to the cost, and might 25 00:01:54,807 --> 00:02:02,320 be related to the problem size how are we going to compute values like that for 26 00:02:02,320 --> 00:02:10,130 [COUGH] 27 00:02:10,130 --> 00:02:10,130 how are we going to make computations if we wind up with an expression like that. 28 00:02:10,130 --> 00:02:14,239 It turns out that as I just explained for the, Catalan numbers. 29 00:02:14,239 --> 00:02:19,252 If k is zero, that's close to, one over square root of pi n. 30 00:02:19,252 --> 00:02:24,759 That's two entries in. but If k is large, that's exponentially 31 00:02:24,759 --> 00:02:27,800 small. It's a very, very tiny quantity. 32 00:02:27,800 --> 00:02:33,997 So we're going to have to come up with an analysis that tells us, both those 33 00:02:33,997 --> 00:02:37,842 things. another example is called the Ramanuj-, 34 00:02:37,842 --> 00:02:42,157 Ramanujan Q distribution. It's actually kind of similar. 35 00:02:42,157 --> 00:02:47,648 A binomial coefficient is n factorial over n- k factorial, k factorial. 36 00:02:47,648 --> 00:02:52,748 this one's n minus n factorial over n- k factorial, n to the k. 37 00:02:52,748 --> 00:02:58,710 And that actually arises in the analysis of several classical, algorithms. 38 00:02:58,710 --> 00:03:03,300 in that one, if K=zero. It's just infectorial, or infectorial. 39 00:03:03,300 --> 00:03:07,698 It's one And, but if K is close to N that one is 40 00:03:07,698 --> 00:03:12,175 exponentially smaller. N to the N is way smaller than N 41 00:03:12,175 --> 00:03:16,915 factorial. So this the types of functions and the 42 00:03:16,915 --> 00:03:24,766 types of challenges that we face with analyzing functions of two variables. 43 00:03:24,766 --> 00:03:33,673 now to get an idea of, of, what goes on we use plots like this where we draw one 44 00:03:33,673 --> 00:03:42,297 line for each value of k and then we scale you can't, in a graph, you can't 45 00:03:42,297 --> 00:03:48,519 have a variable n. So we make that a variable n by scaling 46 00:03:48,519 --> 00:03:56,458 the actual values by a factor of, of 2n. so the binomial coefficients 47 00:03:56,458 --> 00:04:03,216 so [COUGH] for k2. = 2 it's, one quarter, one-half 48 00:04:03,216 --> 00:04:05,577 one-fourth. then 49 00:04:05,577 --> 00:04:15,675 Or, just forgetting about the, [COUGH]. The exponential scaling factor that's 50 00:04:15,675 --> 00:04:18,126 121. And this is 1331. 51 00:04:18,126 --> 00:04:25,479 14641, so you can see Pascal's Triangle in these plots. 52 00:04:25,479 --> 00:04:35,049 And what happens, as many people are familiar, is that as n increases this 53 00:04:35,049 --> 00:04:41,190 discrete two variable distribution converges to the normal distribution. 54 00:04:41,190 --> 00:04:47,419 and to and to a curve that we can describe with a simple mathematical 55 00:04:47,419 --> 00:04:54,359 function and we're going to see the math to get us to the place that this picture 56 00:04:54,359 --> 00:04:58,223 shows us. we ought to be able to have a simple 57 00:04:58,223 --> 00:05:02,087 description of this distribution and we do. 58 00:05:02,087 --> 00:05:06,345 this is what Ramanujan Q distribution looks like. 59 00:05:06,345 --> 00:05:13,353 Again the same type of plot for different factors of K we draw a curve. 60 00:05:13,353 --> 00:05:19,760 so k goes from zero to n. when k is small it's very close to one. 61 00:05:19,760 --> 00:05:26,403 when K gets close to N over two, it becomes extremely small and then there's 62 00:05:26,403 --> 00:05:33,749 a curve that describe its growth so for a large N we ought to be able to use some 63 00:05:33,749 --> 00:05:40,939 function that defines that curve for any value of K and that's what we're after 64 00:05:40,939 --> 00:05:43,827 with bivariate asymptotics. now 65 00:05:43,827 --> 00:05:49,658 let's take a look, first, at the Ramanujan Q distribution. 66 00:05:49,658 --> 00:05:56,188 The calculation's a little bit simpler. It's an extension of the calculation that 67 00:05:56,188 --> 00:06:01,708 we did for the catalyn numbers. it's just that now, we're carrying on 68 00:06:01,708 --> 00:06:05,596 this variable k. So, first step is use the x log 69 00:06:05,596 --> 00:06:09,794 technique. N factorial where as k factorial to n to 70 00:06:09,794 --> 00:06:17,035 the k is e to log of n factorial - log of N - K factorial - log of N to the K, 71 00:06:17,035 --> 00:06:20,796 which is K log N. So that's the first step. 72 00:06:20,796 --> 00:06:24,936 Now, how are we going to expand each one of those? 73 00:06:24,936 --> 00:06:30,175 Well, the first two, is, are just, handled with, Sterling. 74 00:06:30,175 --> 00:06:35,499 so we'll use, Sterling's approximation to log n factorial. 75 00:06:35,499 --> 00:06:39,555 and just plug that in, in both of these cases. 76 00:06:39,555 --> 00:06:45,808 so that says log n factorial is n + one-half log n - n + log of square root 77 00:06:45,808 --> 00:06:51,508 of two pi + O of one over n. Now the difference is that's what we use 78 00:06:51,508 --> 00:06:58,679 for the first term, for the next term we have that value of k that we have to 79 00:06:58,679 --> 00:07:04,894 worry about so we're going to have O of one over N minus K, which we can cover 80 00:07:04,894 --> 00:07:11,199 with O of one over N. So that's plugging in Sterling's formula 81 00:07:11,199 --> 00:07:18,298 for the first two terms and then there's the - K log N term still left there from 82 00:07:18,298 --> 00:07:22,109 the N to the K. So again, we've got a bunch of terms. 83 00:07:22,109 --> 00:07:28,012 Three terms for the log N factorial, three, three terms for the log N minus K 84 00:07:28,012 --> 00:07:34,065 factorial, and then the minus K log N. And we've got to do algebra to deal with 85 00:07:34,065 --> 00:07:37,727 those terms. And again, there's some cancellations 86 00:07:37,727 --> 00:07:43,256 that are going to help us out. Log square to two pi cancels the minus N 87 00:07:43,256 --> 00:07:48,090 plus N cancels There's 88 00:07:48,090 --> 00:07:51,847 log of n - k is log of n+ log of 1-k over n. 89 00:07:51,847 --> 00:07:56,154 so we get some cancellations there. so 90 00:07:56,154 --> 00:08:01,653 if we collect all those terms, with all the cancellations. 91 00:08:01,653 --> 00:08:08,709 that's, what we're left with e to the -n - k + one-half log of 1 - k over n. 92 00:08:08,709 --> 00:08:12,559 You might want to check, the math on that. 93 00:08:12,559 --> 00:08:18,240 But, it's all, simple algebra that leaves us with that. 94 00:08:18,240 --> 00:08:25,554 And the only technique used is log of n - k equals log N plus log of one minus K 95 00:08:25,554 --> 00:08:30,049 over N, and we're down to just a few terms. 96 00:08:30,049 --> 00:08:35,361 [COUGH] so. Now we have to expand the log of one 97 00:08:35,361 --> 00:08:41,528 minus K over N and that's minus K over N minus K squared over 2N squared, plus all 98 00:08:41,528 --> 00:08:46,579 of K cubed over N cubed, so now we're carrying both variables in the big o 99 00:08:46,579 --> 00:08:51,972 term, which can be a little tricky, we're tryin to, make this work for as many 100 00:08:51,972 --> 00:08:57,023 values of K as we can, but different values of K, particularly when K is 101 00:08:57,023 --> 00:09:02,074 proportional to N, are going to give us different asymptotic accuracey, and 102 00:09:02,074 --> 00:09:06,580 that's one of the challenges with vivariant asymptotics, but we'll. 103 00:09:06,580 --> 00:09:11,010 Carry it in this form and see where we go. 104 00:09:11,010 --> 00:09:16,310 So just plugging in that formula and doing the math. 105 00:09:16,310 --> 00:09:21,110 is so there's a minus K over N, we're multiplying by N. 106 00:09:21,110 --> 00:09:24,550 And again, you can go ahead and do the math. 107 00:09:24,550 --> 00:09:29,990 not too much survives. there's K squared over two N minus K 108 00:09:29,990 --> 00:09:34,390 squared over N so that's minus K squared over two N. 109 00:09:34,390 --> 00:09:40,230 The K is canceled so all we get is even minus K squared over two N in the end. 110 00:09:40,230 --> 00:09:46,790 And then what's left over are the two error terms and those error terms are 111 00:09:46,790 --> 00:09:50,310 just doing the math. If you multiply N times. 112 00:09:50,310 --> 00:09:56,146 A of k cubed over over [INAUDIBLE] k cubed over n cubed you get k cubed over n 113 00:09:56,146 --> 00:10:04,170 squared and if you multiply k times sorry and then what's left is the O(k)/n. 114 00:10:04,170 --> 00:10:10,952 So those are valid formulas, but the interpretation of the formulas going to 115 00:10:10,952 --> 00:10:15,318 depend on the value of k. And it tells us a lot. 116 00:10:15,318 --> 00:10:22,285 For a small k, for a relatively small k, it says that it's going to close to 117 00:10:22,285 --> 00:10:22,471 e(-k^2/2*n). to the - K^2 / 2N. 118 00:10:22,471 --> 00:10:29,666 That's the curve that we see when so if we just, analyze, that there different 119 00:10:29,666 --> 00:10:35,954 values, if this, in fact if K is like N to the two fifths say, which is a pretty 120 00:10:35,954 --> 00:10:42,397 good sized value, then, K over N is going to be one over N into three fifths K 121 00:10:42,397 --> 00:10:48,762 cubed or ran squares one over into the four fifths, so that's the, error term, 122 00:10:48,762 --> 00:10:55,050 seems like we're shaving into, tiny dinstinctions but, the main point is one 123 00:10:55,050 --> 00:10:59,630 over into, positive power, that's going to be a big, 124 00:10:59,630 --> 00:11:05,280 A big distinction when K is square root of n they are about the same. 125 00:11:05,280 --> 00:11:12,017 Now k gets bigger and this term starts to starts to pick up but we can work with 126 00:11:12,017 --> 00:11:17,812 others different ranges and really the main point of this derivation is to show 127 00:11:17,812 --> 00:11:23,752 that for most of the curve, remember the plot showed up to square root of n its 128 00:11:23,752 --> 00:11:29,910 got a fine curve when description of that curve we have it its e to the -k squared 129 00:11:29,910 --> 00:11:35,316 over 2n. which is a simple function to work with 130 00:11:35,316 --> 00:11:41,324 as opposed to the original description involving factorials. 131 00:11:41,324 --> 00:11:46,150 a similar situation works for the binomial distribution. 132 00:11:46,150 --> 00:11:52,986 and again, this is just an exercise. using Sterling's formula, carrying 133 00:11:52,986 --> 00:11:59,626 through all the air terms and making sure that you get their cancellations. 134 00:11:59,626 --> 00:12:06,798 and its definitely worthwhile to close the book, turn off the computer and try 135 00:12:06,798 --> 00:12:13,527 to do this derivation, just as an exercise in Algebra perhaps, because you 136 00:12:13,527 --> 00:12:19,814 can see when you do that, how the cancellations happen and simplify the 137 00:12:19,814 --> 00:12:24,448 calculations. And, everybody who works in the That sort 138 00:12:24,448 --> 00:12:30,134 of field knows that, if you do a long calculation like this and you miss a 139 00:12:30,134 --> 00:12:37,002 term, you're going to get, something very exciting at the end, that, maybe, is, not 140 00:12:37,002 --> 00:12:43,058 relevant, or wrong simply by missing a term, because, you're, E to a power, high 141 00:12:43,058 --> 00:12:49,113 and you accidenttaly forget, to cancle out a an N term you get E to the enth, 142 00:12:49,113 --> 00:12:53,463 which is, probably is not there at all. ust as an example. 143 00:12:53,463 --> 00:12:59,122 So we'll do the calculations. I'm not going to explain every term on, 144 00:12:59,122 --> 00:13:05,149 on these calculations, but because they're actually very similar to the ones 145 00:13:05,149 --> 00:13:08,530 that we just did. You apply Sterling's Formula. 146 00:13:08,530 --> 00:13:18,556 and so that gives three lines, each with four terms, one for, each of the main 147 00:13:18,556 --> 00:13:24,100 term. and again, initially, we can just use 148 00:13:24,100 --> 00:13:32,711 O(1/n) for the whole range, where we start to have to carry terms that involve 149 00:13:32,711 --> 00:13:39,874 O(k/n) is, when we expand log n-k to be log n + log of 1 - K / N. 150 00:13:39,874 --> 00:13:45,000 And log of N plus K to be log of N plus log of one plus K over N. 151 00:13:45,000 --> 00:13:51,703 that's K over N's are 1's in those asymptotic series are the ones that give 152 00:13:51,703 --> 00:13:57,228 us some complication. so when we do this and do the algebra. 153 00:13:57,228 --> 00:14:03,911 the a bunch of things cancel. The two N cancels with the two Ns and so 154 00:14:03,911 --> 00:14:08,747 forth. and so these are the terms that survive. 155 00:14:08,747 --> 00:14:16,837 and again that's pretty much straight forward algebra with the additional 156 00:14:16,837 --> 00:14:20,970 proviso that we're doing that expansion log. 157 00:14:20,970 --> 00:14:24,899 N minus K equals log N plus log one minus K over N. 158 00:14:24,899 --> 00:14:30,070 The terms of [INAUDIBLE] most of them go. and so we're left with that. 159 00:14:30,070 --> 00:14:38,985 And then these two terms are kind of similar ones got a - K ones got a + K and 160 00:14:38,985 --> 00:14:45,370 just rearranging terms in terms of K x this difference. 161 00:14:45,370 --> 00:14:47,630 Of log(1-k/n), log(1+k/n), and (n+1/2)*(the sum). 162 00:14:47,630 --> 00:14:56,350 Those two, that sum and that difference, that's one of the first exercises that we 163 00:14:56,350 --> 00:15:01,086 did. And those things collapsed down to just 164 00:15:01,086 --> 00:15:07,949 one asymptotic term. so the sum of them is asymptotic to minus 165 00:15:07,949 --> 00:15:13,705 k squared over n squared. And the difference of them is asymptotic 166 00:15:13,705 --> 00:15:19,810 to minus two over n with again, big O terms involving k cubed. 167 00:15:19,810 --> 00:15:25,450 so substituting that in. gives us, 168 00:15:25,450 --> 00:15:33,929 E to the two N log two, minus natural log of square root of pi N, that's, the only 169 00:15:33,929 --> 00:15:41,264 of pi that's left over from all the math, minus K squared over N of plus, the big 170 00:15:41,264 --> 00:15:46,390 ol turn, and then just undoing the act log technique, 171 00:15:46,390 --> 00:15:50,446 E to the two n log two, that's four to the n. 172 00:15:50,446 --> 00:15:56,991 E to the minus log squared of pi n, that's one over square root of pi n. 173 00:15:56,991 --> 00:16:01,969 And then what's left is e to the minus k squared of n. 174 00:16:01,969 --> 00:16:06,912 So [COUGH]. One over 4n, 2n choose n minus k is e to 175 00:16:06,912 --> 00:16:10,542 the minus k squared over n over square root of pi n. 176 00:16:10,542 --> 00:16:15,080 And that's the normal approximation to the binomial distribution. 177 00:16:15,080 --> 00:16:20,945 and that's accurate for a broad range of values of k it's only, for this 178 00:16:20,945 --> 00:16:25,064 approximation. It's only when k gets bigger than N to 179 00:16:25,064 --> 00:16:30,579 the three-fourths that you know, the approximation doesn't work And again, 180 00:16:30,579 --> 00:16:36,723 remembering from the curves when k is that big we can use independent means to 181 00:16:36,723 --> 00:16:39,676 prove that the terms are very, very small. 182 00:16:39,676 --> 00:16:44,188 so there's certainly a lot of math on this slide. 183 00:16:44,188 --> 00:16:50,724 on the other hand the bottom line is a fundamental, classical resolve in 184 00:16:50,724 --> 00:16:53,525 mathematics. And the techniques used, 185 00:16:53,525 --> 00:16:58,660 what makes it complicated is really just elementary algebra. 186 00:16:58,660 --> 00:17:03,795 so it's an exercises in doing elementary algebra well. 187 00:17:03,795 --> 00:17:10,174 and it's interesting these kinds of calculations still nowadays most people 188 00:17:10,174 --> 00:17:17,033 do them by hand because it's difficult to have automatic calculations carry through 189 00:17:17,033 --> 00:17:21,140 on the bivariate to the extent that we'd like say. 190 00:17:21,140 --> 00:17:25,950 so a lot, lots of people still do these kinds of calculations by hand. 191 00:17:25,950 --> 00:17:33,147 And there is plenty of other examples in examples in the book and so I'm not going 192 00:17:33,147 --> 00:17:39,860 to go throw all those examples again. These functions arise, very often and we 193 00:17:39,860 --> 00:17:46,411 can go back to a table like this to get the approximations that we need later on 194 00:17:46,411 --> 00:17:50,454 when we encounter these functions in applications. 195 00:17:50,454 --> 00:17:54,897 so. again different arguments depending on 196 00:17:54,897 --> 00:17:59,910 different ranges of K in most cases will have a. 197 00:17:59,910 --> 00:18:05,849 [COUGH] An approximation that's true no matter what the value of k is, and then 198 00:18:05,849 --> 00:18:11,460 other times we'll have a more refined approximation that'll give us a, a little 199 00:18:11,460 --> 00:18:17,575 more accuray for near the center. So, that's the end result for the normal 200 00:18:17,575 --> 00:18:23,130 distribution, then there's the so called Pawson distribution, which I haven't 201 00:18:23,130 --> 00:18:28,966 talked about very much, but which falls to the very same kinds of techniques and 202 00:18:28,966 --> 00:18:33,818 I'll talk about it when we come to it in the context of applications. 203 00:18:33,818 --> 00:18:39,724 And again if you look at the derivation in the book or you can just, deal with 204 00:18:39,724 --> 00:18:45,630 that by using the X blog trick, a lot of things cancel and the end result is a 205 00:18:45,630 --> 00:18:50,200 famous result that for. [COUGH] 206 00:18:50,200 --> 00:18:58,334 nth of the that n choose k times that binomial for probability that's kind of 207 00:18:58,334 --> 00:19:04,434 small chance of occurring this lambda to the KE - lambda over KE factorial and 208 00:19:04,434 --> 00:19:08,586 we'll talk about applications of that later over. 209 00:19:08,586 --> 00:19:15,112 Now just in terms of the math its She should appreciate that, the very same 210 00:19:15,112 --> 00:19:20,680 techniques that we did on one slide will give this kind of approximation, these 211 00:19:20,680 --> 00:19:25,593 kinds of approximations. in the Q distribution that I talked about 212 00:19:25,593 --> 00:19:30,920 E to the minus K squared over N. to within one over square root of N 213 00:19:30,920 --> 00:19:37,382 uniform or more accurately, near the center, those are the kinds of bivariat 214 00:19:37,382 --> 00:19:44,151 approximations, that we can develop and they're extremely, important in, not just 215 00:19:44,151 --> 00:19:50,151 analysis of algorithms, but in many applications, it, it's far easier to work 216 00:19:50,151 --> 00:19:56,382 with the standard mathematical functions, like E to the minus K squared over N, 217 00:19:56,382 --> 00:20:03,033 then it is to, work with the factorial representations, which are exact but 218 00:20:03,033 --> 00:20:08,250 carry a lot of information that make calculations difficult. 219 00:20:08,250 --> 00:20:12,496 so, Most of the time, we'll be coming back to 220 00:20:12,496 --> 00:20:16,102 this table. and picking out these kinds of 221 00:20:16,102 --> 00:20:22,192 approximations when these sorts of functions arise in the analysis of 222 00:20:22,192 --> 00:20:26,358 algorithms. And we have similar functions that arise. 223 00:20:26,358 --> 00:20:32,849 we'll go back to the derivations. And see that they can be handled with the 224 00:20:32,849 --> 00:20:36,935 same basic method. Really, the ex-blog technique plus 225 00:20:36,935 --> 00:20:43,067 application to Sterling's formula So the, the next challenge that we're going to 226 00:20:43,067 --> 00:20:49,290 have now is though what do we have when we have a sum that involves one of these 227 00:20:49,290 --> 00:20:53,438 functions? and so the example that we'll do is the 228 00:20:53,438 --> 00:20:59,661 so-called Ramanujan Q function and that's a critically important function in the 229 00:20:59,661 --> 00:21:05,105 analysis of algorithms so. It's the Ramanujan distribution summed 230 00:21:05,105 --> 00:21:11,110 over all values of k and it's basically asking what's the area under the curve. 231 00:21:11,110 --> 00:21:17,857 and the challenge is that we're going to need again it's nearly one for small K 232 00:21:17,857 --> 00:21:23,271 and it's negligible for large K. So we're going to need to use different 233 00:21:23,271 --> 00:21:28,450 approximations and different parts of the range to get the answer. 234 00:21:28,450 --> 00:21:34,962 This is a very typical situation so that's why we need bivariate asymptotics. 235 00:21:34,962 --> 00:21:41,866 to make sure that we can have good estimates in the whole range that we can 236 00:21:41,866 --> 00:21:47,665 use to estimate the sum. the general method there is referred to 237 00:21:47,665 --> 00:21:53,493 as the laplace method. If you have to approximate a sum and this 238 00:21:53,493 --> 00:21:58,774 is just a, schematic representation of the situation. 239 00:21:58,774 --> 00:22:06,241 what usually winds up being effective is the tails are going to be small so we 240 00:22:06,241 --> 00:22:12,980 will restrict the range to an area that has what counts and then 241 00:22:12,980 --> 00:22:19,160 Find an approximation that works there and then 242 00:22:19,160 --> 00:22:24,159 What we can do is, Extend the range, so rather than, the, 243 00:22:24,159 --> 00:22:29,352 the point is that, that approximation usually is also going to be very small on 244 00:22:29,352 --> 00:22:32,837 the tails, so we can just extend the range back out. 245 00:22:32,837 --> 00:22:38,372 So we take out the original tails we put in the approximation, we use the, both of 246 00:22:38,372 --> 00:22:43,702 them are exponentially small, by comparison with the value of the whole 247 00:22:43,702 --> 00:22:46,913 sum, so it doesn't matter which one that we use. 248 00:22:46,913 --> 00:22:52,380 and then that gives us a way to get a concise approximation of the whole sum. 249 00:22:52,380 --> 00:22:59,567 That's called the Laplace Method and then usually one of the advantages of 250 00:22:59,567 --> 00:23:06,658 converting from a representation involving factorials to a representation 251 00:23:06,658 --> 00:23:10,300 like e^(-k^2/n) is that we can use an integral. 252 00:23:10,300 --> 00:23:15,843 For functions like that. And then you use that approximation to 253 00:23:15,843 --> 00:23:20,682 get the answer. Where integral with discrete doesn't do 254 00:23:20,682 --> 00:23:26,138 the job for us, usually. So let's look at how this method works 255 00:23:26,138 --> 00:23:29,940 for the Q function. And, and it's actually very 256 00:23:29,940 --> 00:23:34,438 straightforward. So what we're going to do is just pick a, 257 00:23:34,438 --> 00:23:39,278 a value. K0 and split into two parts for values 258 00:23:39,278 --> 00:23:45,942 less than K0 and values bigger than K0. You remember for small Ks where it's 259 00:23:45,942 --> 00:23:50,764 significant for large K it's going to be negligible. 260 00:23:50,764 --> 00:23:56,011 and going from the u, [COUGH] approximations that we developed 261 00:23:56,011 --> 00:24:01,320 before, for example, if you take K zero to be like N to the two-thirds and then 262 00:24:01,320 --> 00:24:06,630 the tail is going to be exponentially small, and I won't do the detail of that. 263 00:24:06,630 --> 00:24:11,260 And then for the tail's exponentially small, and not only that. 264 00:24:11,260 --> 00:24:16,327 We have a good approximation of the sum, and for k 00:24:20,342 For all of those values, it's not far from E(-k^2/2*n). 266 00:24:20,342 --> 00:24:24,166 to the K^2 / 2N. That's the approximation that we just 267 00:24:24,166 --> 00:24:27,800 developed. Very close to that, actually. 268 00:24:27,800 --> 00:24:33,961 so then we can, now we can just, but that one also for large k is going to be 269 00:24:33,961 --> 00:24:39,673 exponentially small, so we might as well just extend the range back to be an 270 00:24:39,673 --> 00:24:43,208 infinite sum. because the tail is also exponentially 271 00:24:43,208 --> 00:24:47,594 small for that one. And now that sum, we can just approximate 272 00:24:47,594 --> 00:24:51,687 with an integral. And if you do that, you get square root 273 00:24:51,687 --> 00:24:56,235 of pi, N / 2. So, and again that's the true value of 274 00:24:56,235 --> 00:25:01,977 doing asymptotic calculations. This function, q(n), well it's a precise 275 00:25:01,977 --> 00:25:09,023 description of some mathematical quantity that's going to be really difficult to 276 00:25:09,023 --> 00:25:12,329 compute. But if you know the sqrt(pi*n/2), then 277 00:25:12,329 --> 00:25:19,376 that's something that you can work with. And we'll be coming back to applications 278 00:25:19,376 --> 00:25:25,171 that use this function later on. that's an introduction to bivariate 279 00:25:25,171 --> 00:25:29,187 asymptotics. Now I want to finish up by giving a few 280 00:25:29,187 --> 00:25:34,350 exercises that how you might do, before the next lecture to test your 281 00:25:34,350 --> 00:25:39,669 understanding of asymptotics. so the first one has to do with, where I 282 00:25:39,669 --> 00:25:43,587 started with, is how small is, exponentially small. 283 00:25:43,587 --> 00:25:49,614 And this is just trying for a couple of values of Alpha and Beta comparing with 284 00:25:49,614 --> 00:25:53,155 the values of Alpha to the n and Beta to the n. 285 00:25:53,155 --> 00:25:58,957 And, really showing that Alpha to the n is, the larger ones is going to be really 286 00:25:58,957 --> 00:26:03,905 good [COUGH] approximation. So here's another one an opportunity to 287 00:26:03,905 --> 00:26:08,634 go through those calculations that I did at the in the last section. 288 00:26:08,634 --> 00:26:13,554 there's another Ramanujan function actually there's three famous ones but 289 00:26:13,554 --> 00:26:18,347 this is another called the p function it's also the r function which is 290 00:26:18,347 --> 00:26:20,840 discussed in the book. and that's 291 00:26:20,840 --> 00:26:25,955 this function, sum over K, of N minus K to the K, N minus K factorial run 292 00:26:25,955 --> 00:26:31,139 factorial, that one also, is approximated by square root of pi N over two. 293 00:26:31,139 --> 00:26:36,945 And you're going through the tech, the steps that I did for the Q function, for 294 00:26:36,945 --> 00:26:42,752 this function, will be a very instructive if you want to test your understanding of 295 00:26:42,752 --> 00:26:48,121 this material. [COUGH] so those are 296 00:26:48,121 --> 00:26:54,425 So, so, one thing that you might do just to get started is write a program that'll 297 00:26:54,425 --> 00:26:57,503 print. log base two of n [INAUDIBLE] k. 298 00:26:57,503 --> 00:27:01,931 and just use what we've talked about in this lecture. 299 00:27:01,931 --> 00:27:05,534 get that done. That's an intersting excercise. 300 00:27:05,534 --> 00:27:10,337 and write up solutions to the two exercises that I just gave. 301 00:27:10,337 --> 00:27:18,218 and again if you're not comfortable with, with using text tech, either on paper or 302 00:27:18,218 --> 00:27:23,252 with Math jackson HTML. That'll certainly provide some practice 303 00:27:23,252 --> 00:27:29,207 or I'll write it up by hand I don't write stuff up by hand anymore, but some people 304 00:27:29,207 --> 00:27:32,831 do. and then read the chapter on asymptotics 305 00:27:32,831 --> 00:27:37,750 in the text for much more detail on all the information we've covered. 306 00:27:37,750 --> 00:27:43,380 in the next lecture we'll put together all the things that we've talked about in 307 00:27:43,380 --> 00:27:47,716 the previous lectures. And see how they fit together to form the 308 00:27:47,716 --> 00:27:53,830 basics of analytic combinatorics. then we can then go on to apply to the 309 00:27:53,830 --> 00:27:55,600 analysis of algorithms.