Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.
Bitstrings
Loading...
Del curso dictado por Princeton University
Analytic Combinatorics
16 calificaciones
De la lección
Applications of Rational and Meromorphic Asymptotics
We consider applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes that we encountered in Lectures 1 and 2. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction.
Conoce a los instructores
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
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.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
