0:03

Now we're going to talk about the analysis of random mapping.

Â this is something we've been promising for a while and actually it uses, a lot

Â of the things, pretty much everything we've talked about, so far.

Â For the analysis it's a very elegant and compelling application of analytic

Â combinatorics. So mapping is a function from the set of

Â integers, from 1 to n, unto itself. this is from, a lecture two.

Â and we can, represent every map thing with a diagraph, where every node has out

Â degree one. it goes, there's an arrow from every node

Â to some other node. and the N degree could be anything from

Â zero to N. In some mapping, some, the mapping

Â divides up into components and the components are cycles, or they're cycles

Â of labeled trees. And the, lots of applications where we're

Â interested in studying properties of mappings and, natural questions that come

Â up are, how many different components are there on average in a random mapping?

Â how many of the nodes are on cycles and how many are on trees and so forth and

Â several other parameters that come up. And these are all handled in fairly

Â straightforward manner, with the schemas that we've been considering.

Â so first question is enumeration, how many mappings are there of length N.

Â and we talked about this in lecture two. in one sense it's easy.

Â You're mapping N images onto themself for each of the N.

Â position, needs to be in nods. As in impossibilities as of where good

Â points, so it's into the end. but, the internal structure, is of

Â interest in plenty of applications, so this is another way, to, a, break out the

Â number of mappings. And we're going to let it come to torks.

Â We're going to take a look at the structure and that also allows us to

Â analyze every values of perimeters. And so we looked at this basic setup in

Â lecture two. it starts with trees, Kaylee trees,

Â labeled rooted unordered trees.A Kaylee tree is a node and a set of trees.

Â Root in the set of trees. and that translates by the symbolic

Â method immediately to c of z equals zc of z.

Â a component in a mapping is a cycle of trees.

Â So, y equals the cycle of trees, where c is the class of trees.

Â So, y is log of 1 over 1 minus c of z. Where c of z is defined that way.

Â And then a mapping is a set of cycles of trees.

Â It's a set of mapping components. and that translates to the EGF equation,

Â e to the log of one over one minus c of z, or one over one minus c of z.

Â so that's the basic structure of the symbolic method for mappings, and now

Â we're going to see how that has implications for the analysis of the

Â enumeration of each one of these items. and, and for enumeration of parameters of

Â mapping. so this is from earlier in this lecture,

Â we just did this one that's a Cayley's tree, labeled ordered trees.

Â We went from the construction to the generating function.

Â And then it's a simple variety of trees, so we went to immediatly to the

Â coefficient asymptotics. that was our last example of a simple

Â variety of trees. This exactly this class C.

Â but, remember at the beginning of the lecture, I pointed out that we not only

Â can get coefficient asymptotics from singularity analysis.

Â We can also get approximation to the function.

Â so, I've been leaving this off but that's, in theorem we get approximation

Â to the function. it's lambda minus the same constant,

Â times squared one minus z [UNKNOWN]. so, in this case where lambda is one and

Â they're all e, it says that the generating function for Coyley Trees is

Â [UNKNOWN] to. at 1 over e, which is where the near

Â single error of the origin is. That's asymptotic to 1 minus square root

Â of 2, square root of 1 minus ez. And so, we can make use of that

Â approximation later on in the analysis. So, for example, we want to know the

Â number of cycles of trees. that's the components in a mapping.

Â the generating function equation we get is immediately log of 1 over 1 minus c of

Â z. But the last slide c of z is asymptotic

Â to 1 minus root 2, square root of 1 minus c of z.

Â 1 minus that is root 2 square root of 1 minus ez.

Â so that comes out to half log of 1 minus ez minus log root 2.

Â just plugging that in so that's approximation for the generating function

Â for the number of mapping components. but this one is just standard scale.

Â Just as log 1 over 1 minus c z is e to the n over n.

Â So that immediately gives the asymptotics of the coefficients, or number of cycles

Â in trees is e to the n over 2 n. or another way to look at that is to

Â apply Stirling's formula and get square root of Pi over 2 and then to the N.

Â so then there's two different expressions for, for that, or that's factoring in the

Â N factorial to get the number of different mapping components of size N.

Â So that cycles of trees, and now we want the class of all mappings.

Â Mapping is a set of cycles of trees. So that's e to the y of z.

Â y of z on the previous slide, we show that y of z is [UNKNOWN] to half log, 1

Â over 1 minus z, e z minus log of square root of 2.

Â 8:13

But more generally if we want to look at problems like what's the average number

Â of components, in random mapping. Or how many of the nodes are on, on

Â cycles, in average. use their calculations for the small

Â examples. then, we can get those, just by, the same

Â process just, extending the transcript there slightly.

Â Well components come for free because we have the corrolary to exp log saying that

Â you have an exp log setup, the number of components is alpha log n.

Â we had alpha equals a half, so average number of components in a random mapping

Â is one half log n. again, it comes immediately through by

Â the same process that we use for a simple problem like permutations.

Â or nodes on cycles where we can use [UNKNOWN] generating functions, mark the

Â nodes on cycles with U, so then we get a [UNKNOWN] generating function X block one

Â over one minus U. and now we can put in to get the expected

Â number of nodes and cycles we have to differentiate with respect to u, and

Â evaluate at 1, so that gives us an expression in terms of the generating

Â function for a Cayley trees. But now, at this point, with singualrity

Â analysis, we had that approximation for that generating function so we can plug

Â in that approximation. So C of Z equals one minus square root of

Â two squared one minus CZ, one minus C of Z equals just that and then if you square

Â it, you get two times one minus CZ. And C of Z over one minus C of Z square

Â [UNKNOWN] to one half [UNKNOWN]. Ez.

Â So, you can check that, but that's not too difficult.

Â So that gives us, an approximation for, the, generating function, for, the

Â expected number of nodes on cycles. So I might want to get the coefficient of

Â z to the n on that, but that's just an expansion.

Â It's just e to n over n to the n. And then applying applying sterling

Â formulas the, the pi comes back pi or the, pi over square root of two pi comes

Â back. And so the average number of nodes and

Â cycles is square root of pi over you know, over 2.

Â very straight forward calculations based on singularity analysis.

Â and this, this graph for example, the, it, it predicts that there'd 12.5 nodes

Â and cycles and actually there's 9 in that but for bigger graphs it'll be more

Â accurate. these estimates are accurate to one over

Â n. So and we can get more terms if we wanted

Â because everything that we do is extended and sendable to any acitotic accuracy.

Â So that's the use of singularity analysis to study mappings and their

Â characteristics.

Â