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.
Singularity Analysis
Loading...
From the course by Princeton University
Analytic Combinatorics
16 ratings
From the lesson
Singularity Analysis
This lecture addresses the basic Flajolet-Odlyzko theorem, where we find the domain of analyticity of the function near its dominant singularity, approximate using functions from standard scale, and then transfer to coefficient asymptotics term-by-term.
Meet the Instructors
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Now we're ready to t-, take a look at the basic approach of using singularity
analysis to develop asymptotic estimates coefficients from generating functions
and equations. so just to review the transfer theorems
that we've taken a look at if we have meromorphic function, we saw in the last
couple of lectures, then we've got an easy way, based on the theorem based on
contouring integration residues. But easy-to-apply theorem that gives us
the an approximation of the coefficient Z to the n, the ratio of two analytic
functions. by simply evaluating the derivative at
the closest pole to the origin. standard function scale lots of functions
fall in that range. then we can just immediately use the the
transfer theorem that I just gave for the standard function scale and that's based
on the gamma function. but if it's not either one of the those,
that, that's when we're going to talk about singularity analysis.
And here's the example of a type of function that might that that is neither
meromorphic nor falls in the standard function scale.
it's got a square root, but it's got a product of that a ratio that of some
other function. so, what we're going to do,the basic idea
is to, get an approximation of this function to functions in the standard
scale and then do the transfer. and the next lecture, by the way, we'll
look at what happens when there's no singularities at all.
So, but, now we're going to talk about Singularity Analysis.
Now, just a quick review of one of the keys to singularity analysis is our
ability to use the Taylor theorem to approximate functions at points that
aren't singular. That's a definition of an analytic
function is it's differentiable everywhere if it's analytic at a point,
it's differential everywhere at the point.
and that means you can expand it at the point just using Taylor's theorem.
So say if we have this function that I show before e to the minus z squared over
2 minus z squared over 4. And we want to expand it at z equals 1.
then we can just go ahead and compute the derivatives and evaluate them at 1.
So f of the function evaluated at 1 is e to the minus three quarters.
the derivative evaluated at 1 is plus e to the minus three quarters because 1
plus 1 is two, and then there's a minus that cancels out.
the second derivative evaluated at 1 you can get either minus three quarters over
4 and so forth. And just use Taylor's Theorem to develop
an expansion of the function at any point that it's not singular.
and that's a fine method that's been known for centuries and that's.
what we're going to do for singularity analysis is to exploit this ability to
approximate functions at non-singular points in terms of a po-, a power series
and that's what's going to take us to the standard scale as, as we'll see.
now nowadays we know people don't compute derivatives so much by hand anymore.
you can just use a computer and for a symbolic package and so this is Wolfram
Alpha, type in so say I want to know the series representation of square root of 1
minus 1 plus z over 2z at z equals one third.
I can just put it in that function at z equals one third and how many terms I
want and it'll tell me exactly the expansion.
So I don't have to compute that by hand. So people don't compute those things by
hand so much anymore. if you need to do it figure out how to
get a computer to do it, it's a much faster way to proceed.
actually, we're going to use these kinds of approximations in this lecture, only
early on to demonstrate the method. In practice, a great many of the
applications of singularity analysis are based on general schema, where we don't
have to do the expansion. it's all hidden underneath the covers in
terms of general schema. but still it's important to remind
ourselves what it's all based on. And Taylor theorem is definitely it.
okay, so here's an overview of the general approach to coefficient
asymptotics, for non-member functions. So again always we gotta locate the
singularities; in particular, we gotta find the one closest to the origin.
and that's what's going to give the exponential growth factor.
that's no different even when there's essential singularities.
There's one of them that's closest to the origin.
So, just running example, we'll use unary binary trees, so that's trees where all
nodes have degrees zero, one, or two. we develop this generating function for
it using the symbolic method. closest uh, [COUGH] singularity of the
origin is z equals one third. There's another one further out at minus
1, but that, that's the one that matters. So the exponential growth factor is
going to be 1 over that, which is 3 to the n.
so, that's the first thing. so then the next thing is to figure out
where the function is analytic near the dominant singularity, basically, where's
that slit? And then we're going to use functions
from the standard functions scale to approximated, near that dominant
singularity using Taylor theorem and we approximations that extend, in principal.
so, uh, [COUGH] we'll look at how to develop for, for this function an
approximation like this. and we can, can, carry it out like this.
as many terms, as we wanted. so that's, first key is, we have to know
where it's analytic. and, well we'll see how that comes out in
the proof. and then, the, the other basic idea in
singularity analysis is, Now we've got the thing expressed as
approximation using the standard scale. we can do term by term transfer and
immediately transfer this using the standard scale to the result.
And even transfer the big O to the corresponding result.
that's another key to the method, is term-by-term transfer is valid.
That has to be proved and that's one of the keys to the method.
and as I said, in the overview lectures, this paper was a real watershed in
analytic cognitorics. before that, people knew things kind of
like this. But after that, this is the scientific
basis for we can mathematically prove that we can do these kinds of
manipulations. and that's what led to the devlopment of
general schema and many other things that we won't have time to get to in this
course. So the whole idea of singularity analysis
depends on the function being analytic, in a region near its singularities.
in, so again for square root and log, usually talking about a slit and the key
idea is a thing called a delta domain. And they call it a delta analytic
function so that's one that's analytic in this particular shape where we take the
slit and we carve out a little v near the slit and then the other way other wise
it's a circle. so it's, it's a little bit weaker than
what the Hankle contour had which was a little circle cut out here and but that
that little difference makes a huge difference in allowing the transfers of,
of the type that we're going to consider. it may not not, people may not be able to
understand these kind of distinctions without really studying this derivation
in the book. but these, these distinctions are there.
and we'll look at just a sketch of that proof in just a minute.
just as a sideline, you might wonder why that particular shape what this is, is a,
a map of Paris And [INAUDIBLE] worked at in [INAUDIBLE]
which is in a suburb of Paris this is a blowup of the area a bit to the west of
Paris. Actually this is the palace of Versailles
down here. It's at the other end of the of the the
pool for the palace of, of Versailles. The, the big pool
And so there's an autoroute and this little area here is Rocquencourt, which
is where the Inrea research office was. And everybody working in this field, over
the 70's, 80's, 90's, and 2000's, would visit Rocquencourt for various periods of
times. And Philippe's office was centrally
located there. a little bit down the road there was a
place called corner bar. and maybe, many of you are too remember,
too young to remember the 80's people would go, we often would go to corner bar
for a quick beer. and at corner bar, there was a Pacman
machine, and and at that time that was quite a novelty.
And people spent many hours on the Pacman machine.
At corner bar having a beer and a smoke. and now Andrew Liska who's the co-author
of this paper denies that, that's where the shape came from.
But I know Phillip too well. Uh, [LAUGH] so I'm sure he was
persuasive. alright so back to the math.
let's look, take a look at how that, that domain shape matters.
now the key i, one of the key ideas is this idea that we can do transfers turn
by turn. even for big O, and little o terms.
And, there's a lot, a lot, of words here, but really this little table tells the
whole story. If you've got something in the standard,
function scale, so you have a big o term, You can transfer that function give that
approximation to that function from the standard function scale.
You can do the transfer for the coefficient asymptotics.
So, big O of 1 over [INAUDIBLE] c to the beta gives o of n to the alpha minus 1
log n of beta and so forth. So those
As long as it's delta, delta analytic within its delta dom, name, domain, you
can carry those transfers through. and it, this is just a really very be,
brief proof sketch just for big O-transfer, and again, you can spend some
time studying the, the details in the book.
But again, it's based on integration around an appropriately chosen contour.
So, if you know it's analytic in the Pacman region, then you can define this
more complicated region, which has a big circle and a little circle, and two
little lines connecting those circles. and in terms of re to the i theta, it's
technical, but not so difficult to characterize these curves.
This little circle, big circle, and two lines.
And then the question is to go 'head and do the estimate for each one of those
lines. and, half a page in the book for each one
of these showing that the line segments and the small segments are the ones that
really give the contribution. Again, starting from Cauchy's coefficient
formula and then the big circle becomes exponentially small, and so eventually
can prove that result. And again, Flageolet and [UNKNOWN] proved
that result it's a very. General result the rest of us can can use
it. so understanding the proof is not nearly
as important as understanding the application in, in the context of
analytic combinatorics. So then that gives us the three steps
that we need for coefficient asymptotics. we have to figure out where the
singularities are. we gotta establish that it's analytic and
a delta domain, a pacman domain. then [COUGH] we're going to do, we're
going to expand the function in this area, and then approximate it using the
standard function scale. And then do the transfer
Now, in this lecture we're just using the sim transfer, but it's very important to
understand, that the method enables an arbitrary asymptotic accuracy.
Uh, [COUGH], and then so turn by turn transfer, means taking each term in the
function expansion, to a term in the asymptotic expansion of the coefficients.
that's the Flajolet, Odlyzko singularity analysis paper where it's a great paper
to read if you're into reading classic math papers.
so we'll just take one example and sketch how singularity analysis.
Gives us coefficient asymptotics for this example, so that's unary, binary trees.
Every node has zero, one, or two children.
So, combinatorial construction is, it's a node and a sequence of zero, one, or two
nodes. trees.
which immediately translates to that generating function equation.
and if we solve that equation, just use the quadratic theorem, then we get this
explicit form. that is not meromorphic, that's the
square root of a polynomial. so it needs singularity analysis.
So, what we're going to do is well you can plot that function and figure out
that there's room for a pacman region. where it's analytic
[COUGH]. And so that singularity's at z equals 1
3rd, remember. and so, then, at z equals 1 3rd, the 1
minus 3z part is the the dominant singularity.
We're going to take the rest of the function, say 1 plus z over 2z that's the
one that I used the computer to expand so its square root of 3 plus uh,big O of 1
minus 3z or we could add more terms if we want at z equals one third.
then that's square root of three. and so then if you multiply that
expansion times square root of 1 minus 3z and then take care of this is z equals
one third. It's just 1 minus z over 2 z is 1 is
equal to one third. Then you have the square root of 3 times
square root of 1 minus 3 z. And then every term in the expansion has
another square root of 1 minus 3 z multiplied in.
So we have an asymptotic expansion in terms of n to the 1 minus 3 halves 5
halves 7 halves and so forth. All by the fact that it's n over this
part is analytic. And we can expand it in powers of 1 minus
3z, then we multiply by the square root of 1 minus 3z, and we have a term in the
half-power. But those half-powers are standard
function scale. So now we can do a term by term transfer
using the standard function scale, to take, well, you I'm going to change
variables to 3z to z to get to 3 at the end and then the rest of it comes out,
right from the table. Standard function scale, 1 over square to
4 pie over 3 turns into minus 3 halves. And then the next term is three to the n,
n to the minus five half, or you can get an asymptotic approximation.
Now, the next term is not exponentially smaller, it's just the factor of n
smaller, and that's why we need the ability to take more terms if we need
'em. but that's the basic process of
singularity analysis for unary-binary trees.
And it's a very general process that's going to work for a great many of the
functions that arise in analytic [UNKNOWN].
now one reason that we have confidence that singularity analysis is going to be
useful is that the set of functions that are immutable to singularity analysis is
closed. That is, if you have a couple of
functions and you add 'em or multiply 'em or compose 'em, differentiate or
integrate. Well, there's certain technical
conditions all the time. but it's easy to show that, so for
example, if f and z and g of z are delta analytic, then so is their product.
Well because you can approximate f say with in terms of one minus z to the alpha
and you approximate z in terms one minus g in terms of one minus e to the beta and
then you can pull out the approximations of their coefficients.
If you multiply those two functions together then you can immediately pull
out the coefficients of the product. It says if you can do f of z and g of z,
you can do the product. And you can show that for multiplication,
differentiation, other things like that. Well, the kinds of operations that we
perform on functions in the symbolic method are these kinds of things.
We add them, we multiply, we compose them, we differentiate.
Differentiate and integrate them, so we, we think that if you get your functions
in this way, then you're going to be able to use singularity analysis.
so that's a just a general observation. actually we can do even better and
develop a general schema that will free us from a lot of the details even of
singularity analysis for wide classes of functions.
that's just notice you don't multiply this way, you multiply that way.
You might think it's n to the alpha plus beta minus 2, but it's worth noticing
that it's not. that's for product and you can try doing
some or other things to prove that if two functions are amenable to singularity
analysis, their sum is also a composition.
so, the consequence is that the generate function's produced by the symbolic
method are generally going to be amenable to singularity analysis.
so that's a, introduction to singularity analysis and next we'll go on to schemas
and transfer theories.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
