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.
