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.
Saddle Point Asymptotics
Loading...
来自 Princeton University 的课程
Analytic Combinatorics
19 个评分
从本节课中
Saddle Point Asymptotics
We consider the saddle point method, a general technique for contour integration that also provides an effective path to the development of coefficient asymptotics for GFs with no singularities. As usual, we consider the application of this method to several of the classic problems introduced in Lectures 1 and 2.
与讲师见面
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Now we're going to talk about saddle-point asymptotics.
Which is the process of refining saddle-point bounds to get the more
accurate estimates that are available to us.
so again, in the previous segment, I talked about the basic idea of using a
cauchy coefficient formula. To just find the saddle point, use a
circle of radius equal of the saddle point.
And just bounding the interger everywhere on the circle with it's value at the
highest point. but now what we're going to do to get
better at symptotics is just to focus on the place near the saddle point.
So as as we saw early on the integrand is really low for most of the circle so what
we want to do is find a good bound on on the tail or the part that's really low.
in focus on the part of the path that's near the saddle point.
This is like Laplasas' method that we talked about very early on in that
sypathic analysis. Where you focus on the center and bound
the tails and bring the tails back. And with that kind of calculation we can
get very accurate asymoptotic estimates. so that is we're going to look at the
little part of the circle that is close to the saddle point and then rest of it
we're going to show to be negligable. with different estimates.
that's the saddle-point method. And just it's, it's easy to see how it's
going to, going to be effective. Because we saw that the bounds were off
by square root of 2 pi n, which is essentially the part of the circle, it's
low, and we were assuming it to be high. That's all it is.
It's a different factor. so we're going to do a little more
analysis to see that, we can we don't need to do that, and we can get an
accurate estimate with Laplasas' method. Now this, as with many of the transfer
theorems that we consider in analytic combinatorics.
There's going to be technical conditions, that need to be satisfied, for us to
apply this method. and just for completeness in this lecture
I'm going to call that susceptibility. That's just a name for the technical
conditions that's, that are going to be needed for saddle point approximations
to, to work. in, in you, you know, all, all it is, is
really some kind of formal statement that this process is, is going to work.
So that you can you know, find the saddle-point and that's the root of the
saddle-point equation. And the curve can be split into two parts
such that the tail part is negligible. and that the part that's not negligible
is the saddle point that is, there's a quadratic approximation just like we saw
from just an elementary anaylsis of what a saddle point is.
so it doesn't have to be precisely a saddle point but if it's near that saddle
point you have that quadratic approximation.
that's as general of the conditions, as, as the conditions as we can make them.
and as with many of our transfer theorems that we considered earlier on for
singularity analysis and other approaches these technical conditions you know have,
have to be checked. so, if there is a multiple saddle-point,
then maybe there will be some other part of the condition to worry about, but I'm
not going to worry about that, intellectually.
and also tails have to be negligible in the first place, and then however this
estimate works. It has to be negligible, to bring the
pails back. And we'll look at a detailed, example
but, this kind of a technical detail is more appropriate to read about that, in
the book. So, what this is going to lead to is the
so-called saddle point transfer theorem. and that, all it says if you have a
contour integral. and, we write it as f of z equals e, to
the f of z. e to the little f of z just to simplify
the calculation, a little bit. it's a singularity, there's no problem
with doing that. So if that's susceptible to this sort of
approximation, then the, integral is approximated by f of z over that square
root of 2pi factor. It tells us exactly how to compute that
missing factor. this is a general technique for contour
integration, it's not just for asymptotics, that's about any contour
interval. [COUGH] it, gives a, a way to approximate
it. so, for, and the proof is very similar to
the proof that we did for the, saddle point bound.
but, so, that's the theorem, but what we want to use it for is a transfer method
for generating function. so it just translating that over to, our
use of, cauchy's theorem, where we're looking for a coefficient of z to the m
in a generating function. Then what we're going to do is just apply
this theorem with g of z with f of g equals g of z or z to the n plus 1.
So in that, and so that all that do is, is plugging into the general theorem, f
of z equals g of z over z to the n plus 1.
So our, our saddle point equation is just modified slightly and the main point is
that we evaluate our function at the saddle point
And then we have this corrective factor which is just square root of 2 pi times
the second derivative. so it's a plug and chug method of getting
coefficients of z to the n out of entire functions that have no singularities.
now there certainly is technical detail in proving suceptability and I'll try to
illustrate some of that in an example. But in this lecture what I really want to
focus in on is the idea that this kind of approximation is available.
I can't claim that this is as clean as many of the other transfer theorems that
we've looked at because checking those technical conditions can be more
challenging. so anyway, the summary is that for our
generating function g of z, and this is just doing the math backwards,
We're going to use the saddle point equation.
G prime is z over g is z equals m plus 1 over z.
So that's, theta is the solution to that. And then following that, that's the
approximation where little g is a log or big g minus m plus 1 log z.
that's a relative simple calculation for getting asymptotic estimates of
coefficients. So let's go back to our examples.
So estimating 1 over n factorial. it's a saddle point approximation.
Coefficient is z again and then e to the z.
So, g of z equals e to the z. And so, un then taking logs, our saddle
point equation is 1 minus n plus 1 over z equals 0.
so that's zeta equals n plus 1. and then the saddle point bound is just
plug in zeta second derivative us 1 over n plus 1.
so the approximation that we get is e to the n plus 1 over n plus 1 to the n plus
1 squared of 2 pi over n plus 1. and again that one goes to 1 over e and
just simple asymptotics. gives us exactly stirling's
approximation, e, e to the n over n to the n over square root of 2 pi n.
So the, this extra factor in the saddle point approximation gives us the extra
factor that we were missing before. so the choice that we always have when
using saddle point is you can do all the detailed calculations to check that the
interval is suceptible and so forth. or you always have the option of just
using the bound and sacrificing that factor which certainly in many
applications, people will choose as an option.
Now if it becomes important to get the factor, we can can get it, but it takes
some work. and again, checking susceptability, you
have to check that the tails are negligible, that the central
approximation is quadratic. And then we can complete the tails back
in, in a reasonable way. And that's really doing the calculation
for a particular function that we have. Uh, [COUGH] so, at this level, we don't
necessarily have the, the general scheme of, but, this is an important starting
point for, limiting distributions that is something, advanced that we don't study
in this course. so, let's just look at,
And, and again, this is the last lecture in a long course.
So I'm not going to do these calculations in detail.
other to, other than to just, exhibit 'em.
And this is the kind of calculation that's needed to show that it's
acceptable, for this problem. so, what we're doing is, trying to do a
contour integral for either the z or the z over the n plus 1.
or just putting it all in 1 function, z minus n plus 1 log z.
around this this circle, z equals ne to the i theta.
so first thing is to, just switch to polar coordinates z equal to n e to theta
and just plug that in there and most of it comes up.
E to the n over n comes out. and all that's left is interval 0 2pi e
to the n e to the i theta minus 1 minus i theta that's that's just simple
subsitution. so now what these saddle point method
requires is that we're able to split it into 2 contours.
1 for a little part close to the saddle point and then the rest for the tail
which is all the rest of the circle. and so those are the 2 contours and the
point is. For we have to be able to prove that for
the tales gets exponntially small. and that you can look at the text for
that proof, but when we're away from the saddle point, remember, in a 3D diagram
that's when the curve drops all the way down and so exponentially small.
And then in the part close to the so we're going to just negelect the tails
and work with the part close to the saddle point.
and another thing to notice is that if we can slightly shift the saddle point.
If we want, it simplifies the calculation quite a bit.
As long as we have that quadratic equation approximation near where we are.
So now we're just focusing on the central part of the anagram.
And EWI theta minus 1 minus I theta, well it's minus theta squared over 2 minus
theta cubed. Just expand either the data subtracting
off the first terms. The leading term left is the quadtratic
approximation that we're talking about. And so by, restricting, theta 0 to be
less, than a certain value, then we can, drop the big O term, and get, an
approximation, of our integral. As, as long as say, theta 0 is into graph
with alpha less than minus 1/3 then we can drop the bigger term,
And there's a small calculation to check that.
and then we can change variable and do the integral and that's the intergal that
we have. And then we want to restrict theta the
other way to complete the tail so that we can get an integral that we can evaluate.
and then that integral is a regular, normal integral, squared of 2pie n.
2pi over n is the final result. And so we had to bound alpha 1 way to
complete the tails, and bound it the other way to drop the O term.
and we're left with finding a value in between minus 1 half and minus 1third.
So we pick into the 2 5th and that's the complete derivation that, that shows that
it's susceptible to a saddle-point. And again these are integrate
calculations but it's kind of always the same and it's a matter of where that
bound is and that depends on the function.
the the place where the estimate near the saddle point is accurate and there's a
place where the tails are negligable and you just have to find that place.
and and then in the end we're getting Sterling's approximation back from this
problem. so that's a Illustration of the
difficulty of proving susceptibility. and unfortunately, that's still there for
many problems. Again this transfer theorem is not at all
as simple as others we've looked at. And you might well ask, well, you know,
you're talking about the difference between n to the 2 5th and n to the 1
half. That's about n to the 1 10th.
wasn't there something in early lectures about this not being relevant unless n is
so huge that we wouldn't care about it? Is that a problem here?
well actually it's not because in these cases we are talking about estimates that
are in the exponent so n doesn't need to be.
So if n is like a billion and these estimates are still something we are
going to care about and are going to matter.
'Cuz it's in the exponent. the other thing is that I'm doing a quick
illustration here. we can get a full asymptotic series to
any desired precision using these methods.
and also, now when we get the answer out we can validate them numerically which we
usually do for problems of this sort. and we're still pushing towards the goal
of having a general, general schema that will cover a whole family of classes.
it's hard to that we're as far along for saddle points as some methods.
actually, when you look at the, extension to limiting distributions.
we actually, actually are but that's an advanced topic beyond the scope of this
course. so let's look again at the transfer for
the central binomial case. so now, we're estimating coefficient is z
to the n, and 1 plus z to the 2n. so that's our, g of z.
so, if we take log of 2z minus m plus 1 log of z, and then define that to be our
function for the saddle point equation, first derivative is 2n over 1 plus z
minus n plus 1 over z. Second derivative then we get saddle
point equation is set that 1 to 0, so the saddle point is n plus 1 over n minus 1.
And that's what we saw before. and so the approximation says plug in n
plus 1 over n minus 1, into this formula. and we, and we get a pretty ugly
equation. Then we can go ahead and estimate but
remember, it, it's okay to shift the saddle point.
and you wanted to simplify the calculation and this 1 is really close to
1. and so rather than go through an
estimate, of those, let's just use 1. so if we say the saddle point is 1, in,
plug it in, to this equation, then we immediately get out for the n over square
root of pi n, as expected. Making that choice early on and also
simplifies the check of susceptibility and so forth, which is uh, [COUGH],
something that you want to do. You're going to slightly shift the saddle
point as long as that doesn't disturb the idea that you have a quadratic
approximation and that you have a negligable pale, it's not going to matter
in. We can more easily complete a full
derivation after a problem like this. So again, another approach is to just use
the saddle point bound and sacrifice the pi n factor.
But then if it's an application where it's important and you can see what that
factor is then you need to prove that you can go in and do it using Standard
techniques. I think that, that's the the message.
Now, so that's Saddle-Point Asymptotics.
