Saddle Point Bounds

Loading...

En provenance du cours de Princeton University

Analytic Combinatorics

22 notes

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

Princeton University

Analytic Combinatorics

22 notes

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. All the features of this course are available for free. It does not offer a certificate upon completion.

À 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.

Modulus Surfaces17:54

Saddle Point Bounds 9:15

Saddle Point Asymptotics 18:47

Applications 5:13

AC Wrap-up 11:43

Rencontrer les enseignants

Robert Sedgewick
William 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.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play