0:04

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.

Â 5:47

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.

Â