0:04

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.

Â 1:48

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.

Â 9:14

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

Â 11:57

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.

Â 14:58

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.

Â