0:04

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?

Â 4:00

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.

Â 8:19

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.

Â