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.