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 Bounds
Loading...
En provenance du cours de Princeton University
Analytic Combinatorics
17 notes
À partir de la leçon
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.
Rencontrer les enseignants
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Now we're going to look at the development of saddle point bounds for
generating function coefficients using [INAUDIBLE] integration.
the basic idea is very simple. Now, we start with Cauchy's coefficient
formula, which says that given an analytic function G of z.
The coefficient of z to the N and G of z is one over two pi i integral over a
circle that contains the origin, G of z, dz over z to the N+1.
so, just to look at an example, let's look at the function post G of z is e to
the z and we're looking for coefficient z to the fifth.
So that means the function that we're integrating, the e to the z over z to the
sixth. that's a plot of that function.
it's got a pole at zero, and then as the real part gets large it starts to get
large and there's obvious saddle point in there.
now, this plot is actually scaled substantially.
I think that it's only a point, a thousand pi or something.
We'll see some of the numbers in a minute.
But still that's what it looks like. so, the idea of a saddle-point bound is
to find a saddle-point and we always use zeta the Greek letter zeta for the
saddle-point. and then, for our circle we use the
circle of radius zeta. and that, so this is what the integral
will be, be adding up, the height under that circle.
And as you can see, for most of the range it's very, very small.
but even so, if we just take the highest point of the circle, which is the
saddle-point the integrand is going to be less than the value of the function
evaluated at zeta everywhere on that circle.
So then the value of the integral is just going to be as if we had that constant
and that will give us a, a very strong bound.
Now what's zeta it's the solution to the derivative this function equals zero.
and that's just doing the math. it's G prime over z to the N+1 minus N+1,
G over z to the N+2 multiplied by z to the N+2, we get z G prime over G is N
plus 1. That's known as the saddle-point
equation. so that's the idea.
Find zeta and just use the bound of G of zeta over zeta to, to the N+1.
So let's take a, a look at a couple of well here's a formal statement of the
bound. so if G is analytic finite radius of
convergence R with non negative coefficients which are generating
functions from analytic combinatorics always do.
Then the coefficient of z to the N and G of z is less than or equal to G of zeta
over zeta to the N, where zeta is the saddle-point.
Now, that's just a formal statement of the equation.
and again, it just is by Cauchy coefficient formula you take z to be
circle of a radius zeta, and change to polar coordinates.
then we're getting an extra zeta and then if we integrate and everything is
constant then the two pi goes away, and all that's left is G of zeta over zeta to
the n. so, so that's a, of, effective bound that
we can use to at least understand something about the growth of generating
functions coefficients. so for example in our example we're
trying to find a coefficient z to the 5th in E of z so that's we're looking at e to
the z. what's the saddle point?
the saddle point is zeta equals 6. so saddle point equation is G prime over
G which comes out to be 1, leaves us zeta equals 6.
and so the saddle point bound says that we know that coefficient of z to the 50
is z is 1 over 5 factorial. The bounds says that that's going to be
less than or equal to e to the 6th over 6 to the 5th.
and if we just compute those down the left side, it's, you know, 0.008, and on
the right side, it's 0.009. Pretty good bound, even for just the
small value. Five.
So, in general, just doing that same calculation.
let's see how well the saddle point method works for estimating one over N
factorial. so that's coefficient of z to the N and e
to the z. E to the z is the generating function
with no singularities. We're trying to estimate coefficient of z
to the N and e to the z. so saddle point methods, we take G of z
equals z to the z. Solve the saddle point equation.
Saddle point equation is G prime over G times Z equals N plus one so it's going
to tell us that the saddle point is zeta equals N plus one.
And then the bound is Just e to the zeta over zeta to the N, which is e to the N
plus one over N plus one to the N. so it's a saddle point bound.
now if since n plus one to the n if you if you want to do a little more accurate
asymptotics on that, 1 plus 1 over n to the n goes to e, so that's about e to the
n over n to the n. and I'm just doing this sketch now cause
we're working with [UNKNOWN], and we can be more precise and carry it out there
[UNKNOWN] accuracy if we wanted. and so this is just to check how close
this bound is to what we know. Well, what we know is from Sterling's
approximation, one over N factorial is about e to the N over N to the N squared
of 2 pi N. So we're off.
This bound is too high, just by a factor of square root of 2 pi N.
which is not bad considering it grows exponentially.
So we get a pretty good approximation to Of the function with this really simple
bound. So that's a saddle point bound.
And the saddle point method, what is going to be just about getting rid of
that factor or finding a proximation that's more accurate and brings that
factor back in. Now let's look at another example.
suppose we want to estimate 2N choose N. so that's the coefficient of z to the N
in 1 plus z to the 2N. so so now we'll just take G of z to be 1
plus z to the 2N. the saddle point equation is to take the
ratio G prime over G and set equal to N plus one so in this case that works out
to 2NC equals N plus 1 times one plus C. Or the saddle point is N plus 1 over N
minus 1. so that's where the exact saddle point is
and then the saddle point bound is to take 1,
To is to G of zeta over zeta to the N, so N plus 1 over N minus 1 to the N and then
G of zeta, 1 plus that 2N and work it out, then we get 4N squared over N
squared minus 1, to the N. And again that's about 4 to the N.
And how close is that to what we know? Well we know that 2N.
Is about 4dN over square root of pi N. Of what we did from Sterlid's
approximation earlier on. So, again, the bound is off too high,
only by a factor of about square root of pi N.
so, s,s, simple method for estimating the value of coefficients just by determining
the saddle point. and then plugging in that value to the
function divide that by the Nth power. and, it's off by a little bit, but not
much considering the exponential growth. That's the development of saddle point
bounds.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
