Today, we're going to talk about applications of the rational and metamorphic asymptotics that we covered in the last lecture. This lecture is really a turning point in our study of Analytic Combinatorics. We've been doing quite a bit of preparation, both formal and analytic. Now, in this lecture, we're going to see how all that preparation pays off. as we'll really get to the heart of Analytic Combinatorics, where we can derive asymptotic results directly from combinatorial constructions. so we're at Lecture Five where we're finally at the point where we can do a specification, immediately get a generating function equation. And then, immediately transformed to an asymptotic estimate of the coefficients. Now, the bottom line from the last lecture, you remember, we saw the light at the end of the tunnel. And with all the complex analysis that we're prepared for in Cauchy's theorem and residues and so forth. we wound up with this rather simple procedure that it turns out will be effective for a great many of the generating functions that arise from combinatorial constructions. So, what we do is, first find the smallest real pole that's smallest real pole, that's a a root of the denominator of the meromorphic function. then we calculate its residue just by valuating the numerator at alpha and the derivative of the denominator at alpha. then our, our growth is a constant times beta to the n where the constant is the residue divided by alpha. And the exponential growth beta is just 1 over alpha. So, we're going to look at numerous applications of this simple procedure and we don't need to look back at the residues and so forth, where it came from. Although, as we'll see, it's sometimes really interesting to really look at what the, what the poles look like, and we'll talk about that somewhat. let's start with the easiest example, Bitstrings. And this is just to warm up and get the format. And we know that there's 2 to the n different bitstrings of length n. and the generating function's going to be one of our 1 minus 2z. From the stand point of Analytic Combinatorics we've seen many times this specification where a bitstring is empty, or it's a 0 or 1 bit, followed by a bit string. And that immediately translates to the generating function equation, 1 over 1 minus 2z. And now, we can expand that directly to get 2 to the n, but let's look at what it looks like as a meromorphic function. there's a pole at alpha equals 1 half. And this is the plot of of magnitude plot of the function 1 over 1 minus 2z, and things get big and alpha equals 1 half. Then, the residue, that's the f of z in this case, is 1 the g of z is 1 minus 2z. Derivative g of z is minus 2, the minus' cancel, residue is 1 half. and so again, the theorem says that our coefficient is those two things divided, which is just 1. and our exponential growth factor is 1 over alpha, which is 2 to the n. so that's the Analytic Combinatorics methodology applied to this simple problem that admittedly we knew the answer to, anyways. But, as we've seen many times, we can use the very same structure to do problems that we don't have the exact values of coefficients. And we can quickly derive asymptotic estimates of coefficients. So for example how many bitstrings of length in have no two consecutive zeros? and there's ways to show that this one is the Fibonacci numbers. And we saw it before, but let's look at it again from Analytic Combinatoric, and we saw this construction in Lecture One. So, class of all bitstrings having no 0,0 is either empty or it's a zero bit or a zero bit followed by a bitstring that starts with a 1 with no 0,0, and so forth. and so that immediately translates to that generating function equation. That's a rational generating function. It's also meromorphic. this one has two poles. It's a 1 minus so one of the roots is, is phi hat square root of 5 minus 2, and the other is minus phi where that's the golden ratio. so 1 minus that times Z1 minus that times Z well, I give the result. and these things are related phi hat equals 1 over phi and so forth, lot's of calculations we're familiar with. so, but the residue is f of l evaluated at the pole closest to the origin which is real. which is 1 plus phi hat. derivative of g is 1 plus 2z and minus that is 1 it's, sorry, minus 1 minus 2z minus that is 1 plus 2z valuated phi hat is that. and then, little bit of calculation, divide that by phi hat and do a little bit of calculation. we get the end result that the coefficient the coefficient asymptotics of that is going to be close to golden ratio to the n times the constant that we can calculate. so again, directly just by finding the singularity, the closest route to the origin then doing the calculations according to the normal procedure, we get the coefficient asymptotic. so and this generalizes in for this case. say we want to find the class of all bitstrings with no occurrence of four zeros in a row. The construction's easy. The translation down to the generating function just generalizes what we saw for, for the Fibonacci case. and now the singularity structure is a little more complicated. There's four poles but only one of them's on the real line. And we're only interested in the one that's on the real line, that's closest to the origin. so that's alpha, which we can calculate using a symbolic math system. then we can go ahead and compute the residue same as before. figure out what the coefficient is directly from the formula. and immediately, with just a little bit of calculation which again we can do with a symbolic math system get the precise and accurate asymptotic formula for the coefficient. And remember, this is very accurate that the terms we're forgetting about are exponentially smaller. And we'll see that in other examples. and it's just this is just interesting view of what the structure of the poles look like for this set of problems. So this is no two consecutive zeros that we saw. This is what three looks like. this is the one, the four that we just saw. here's 5. and you can see that we have, always have our dominant pole which is on the real line and closer to the origin of any of the others. I don't remember Pringsheim's Theorem. that's going to, that's going to happen for combinatorial generating functions like this. and then if you look at the, this is a big one with ten consecutive zeros. still you can very quickly infer the structure. And we can know that when we get our asymptotic result for the coefficients it's going to be very accurate because the contribution of these other terms are going to be exponentially smaller. They're much further away. So, that's bitstrings with restrictions on consecutive zeros. this generalizes and this material is from part one of Analytic Combinatorics in the next few slides. so I'll go quickly through it. for people that have taken that course and people that haven't taken that course. if you're confused by something on these slides, you might want to watch that lecture which goes through more slowly and in more detail. But I'll go quickly through it now. so, our generating function is the generating function for the number of bit strings that contain say no occurence of n consecutive 0s. And so and then we went ahead and calculated what that looks like, just using combinatorial construction. and it turns out to have that form. That's just a generalization of the Fibonacci that we got for no two consecutive zeros. and actually by multiplying by 1 minus z, both numerator and denominator, you get a slightly smaller form of that. that's the same function. now what's convenient about this particular generating function is if you evaluate it at z over 2 then it just divides by 2 to the n. And it turns into a probability generating function. so that if in, evaluated to z equals 1, so sorry, evaluated z equals 1 half is really what we're doing. so that gives some number of bitstrings with no runs of M0s divided by 2N, that's the probability that the first N bits of a bitstring have no runs of M0s. and we're summing those probabilities that's the same as the probability that the end of the first bitstring is bigger than N. and that gives the expected position of the N to the first occurrence of M0s. Just evaluating the generating function at 1 half. So that immediately, just evaluating this set at 1 half immediately tells us [COUGH] that the probability that in bet, bitstring has no zero and we know that. And if we just evaluated that at 1 half, we'd get 2 to the M plus 1 minus 2. So the expected position of the first run M0s in a random bitstring is a 2 to the M plus 1 minus 2. And that's a simple probability calculation. and this is interesting to think about because if we go to different patterns that are not necessarily all zeros we calculated the probability that a random bistring doesn't contain four zeros. And show that the expected wait time for four zeros is 30. what about for 001, or some other pattern? and what's interesting if you haven't thought about it is that it's, it's not true. The wait time is different and probabilities are different. and for example, 0001 occurs much earlier then 0000. And just to get a little intuition for that, just consider the first occurrence of three zeros in a row. So, it's equally, likely that 000 and 001 happen after that. but if if the next bit is a 1 then you know you're going to have to wait four more bits to find 000. but if you're looking for 001 and the next is a 0, it could give that the next set gives a match. So, you ought to find 0001 sooner than 0000. That's just the intuition we'll show this analytically in, in just a minute. so, we are interested in these problems and there's lots of practical problems where we care about when patterns occur in random bitstrings. So, what's the, what is the probability it doesn't contain 0001 if it's not that and what's the wait time for 0001? Well, the generalizing the techniques that we use with generating functions that we can actually generate, develop explosive formulas for these generating functions. And I'll just quickly go through this derivation again because it's from Part 1 Lecture Five. and what we do is we for any pattern, say this pattern 101001010 we define two combinatorial classes. One for the strings that do not contain the pattern, and one for the class of strings that end in the pattern and have no other occurrence of it. And then, what we do with that is we develop constructions, two different ways to construct these classes with in terms of each other. And that gives us simultaneous equations that we can solve to get the generating function. so first one is, for example, to notice that these things are disjoint. if it doesn't contain p, then it can't end in p that Sp has the empty string. And if you add a bit to the string in Sp, either you get the string that doesn't contain the pattern, or you get a string that ends in the pattern. And that just corresponds to this combinatorial construction. the second construction is a little bit more complicated. It's developed in terms what's called an auto-correlation polynomial, where we slide the pattern to itself over, to the left, over itself. and if the trailing bits with the leading bits match, then we include a term. So, zero shift makes a match. But after a while, if we shift five positions, then 1010 matches the leading bits and so forth. So we define this thing in this way called the Auto-correlation Polynomial. And with the Auto-correlation Polynomial, we can develop another combinatorial construction. And then, we'll go through the details of this. again, look in Lecture Five if you want to see them. that gives the construction of these two classes, Sp and Tp, in terms of the Auto-correlation Polynomial. So if we want to find the bitstrings that don't contain a specified pattern, we have these two combinatorial classes. they have their generating functions and we have the, two constructions. And those constructions by the symbolic method, immediately translate into two different generating function equations, involving our generating functions of interest and the correlation polynomial. Solving those equations then we get an explicit solution for the class of binary strings that do not contain a given pattern. A very simple rational generating function. so that's the ratio of two polynomials. And so, that means that we can use the general procedure to go ahead and find that the, an asymptotic estimate for the coefficients. just by plugging in, finding the dominant root of the polynomial that's closest to the origin and then getting the explicit formula for the coefficient. right from the, the basic procedure that we've used. Two polynomials, we know how to deal with two polynomials. I'll leave a specific example of the Analytic Combinatorics going right from the spec down to asymptotics for an exercise at the end of this lecture. so that's an introduction to the use of the Meromor, Meromorphic Transfer Theorem as a part of Analytic Combinatorics. To immediately derive asymptotic results for interesting practical combinatorial classes of interest directly getting to accurate asymptotic results.
