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.
Moment Calculations
Loading...
來自 Princeton University 的課程
Analytic Combinatorics
19 個評分
從本節課中
Combinatorial Parameters and MGFs
This lecture describes the process of adding variables to mark parameters and then using the constructions form Lectures 1 and 2 and natural extensions of the transfer theorems to define multivariate GFs that contain information about parameters. We concentrate on bivariate generating functions (BGFs), where one variable marks the size of an object and the other marks the value of a parameter. After studying ways of computing the mean, standard deviation and other moments from BGFs, we consider several examples in some detail.
與講師見面
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Next we're going to talk about how to use ordinary, bivariate, generating
functions, to calculate moments. now this sections has quite a bit of
calculation in it. Got a quite a bit of math on the slides,
and they're a little bit more for reference than for me to talk about.
but still, many of the calculations are, are familiar, and I think you'll see that
it's, that it's worthwhile to, include all the details.
But really I don't want all that math to obscure the bottom line, that actually
it's very easy for us to calculate moments.
once we have a good expression for the ordinary bivary generating function, in
many cases. so I'll go through the details in this
section, and then in the next section, we'll see lots of details that illustrate
how simple the calculation can be. So we start off with the ordinary binary
generating function that we defined for uh,[COUGH], combinatorial classes with
parameters. [COUGH] we sum over all objects in the
class z to the size of the object, u to the cost.
and we have our elementary identity that I'll write over on the right.
I'll write more classic probability expressions just you know for reference
and for checking. the kind of manipulations that generating
function manipulations that we'll be doing.
so first thing is enumeration. so how many objects are there of size n?
[COUGH] That's the sum on K of PNK. so some over all costs are the ones that
size n you get the number of objects of size n.
From the ordinary binary function how do you get that?
Well it's just the coefficient of z to the n in the binary generating function
evaluated with z equals one. So that pz1 then the u goes away and it's
all one it's just sum on p everything in the class, z to the size of the class.
but again, that's can be collected with uh,[COUGH] all the ones of the same size
that's exactly the same as piece of nz to the n.
So piece of n is the coefficient of z to bn in the[COUGH] ordinary bivariate
generating function evaluated at u equals one.
Or you can do the sum, and substitute p and k in there again and get back to p of
zu. Okay, so that's enumeration.
And again, this math over here is not really needed except to check your
understanding of what's going on. Now let's look at the cumulative cost.
the way that we compute averages when using generating functions is take the
total cost in the objects of size n and divide that by the number of objects of
size n. That's the average.
that's a little bit different calculation than working with probabilities but since
we have this powerful mechanism for counting, I am forgetting counting
results, it's natural to do it and we can see from the ordinary bjf how this works.
So we're interested in the total cost in objects to size in.
So, again, that's for all values of k, we multiply, the number of objects, the
size, and the cost k, by k, that gives the cost for all of those objects, then
we sum over all values of k, we'll just call that, q sub n.
what's that value in terms of the Generating Function?
Well what we do is we differentiate with respect to u, that's the marker variable
for the cost and then evaluate it, z equals 1 and u equals 1.
So that's the partial with respect to u of the ordinary bi-variate generating
function. A value at it u equals 1 just from the
definition that's the sum on all objects, cost times z to number of objects and
again if you collect all the objects of a given size n.
That's, exactly the same as q sub n z to the n.
So it's the coefficient of z to the n in the partial with respect to u of the OBGF
evaluated at z equals 1. or you can look at this representation on
the right of the generating function. when we, sorry this one at the top.
If you differentiate with respect to u, it brings down a k.
So that you get k, p and k. and that's the familiar way to think of
the total cost. but in terms of the, bivariate generating
function, it's a simple partial derivative and then evaluate at 1.
So that gives us what we need to calculate the mean cost of objects of
size n. we take the coefficient of z to the n, in
the partial with respect to u, of the OBGF.
Evaluate at u equals 1. And divide by coefficient of z to the n
in the OBGF evaluated at u equals 1. and that's in many cases, a simple
calculation. And again, that's the average, which
maybe you're more familiar in the form over here, kp and k over, over pn and we
can calculate then the variance in the same way.
definition of the variance is the sum on k, k minus the means squared times the
probability in, in terms of the ordinary bi-variate generating function.
it's not hard to check but that's the second partial with respect to u
evaluated at z equals 1. n subtract of at the mean, subtract of
the mean squared just as with normal probability calculations.
So that's a overview of calculating moments from an ordinary bi-variate
generating function. just using partial derivatives with
respect to the variable that marks the cost and then evaluating at that variable
equals 1. And we'll look at an example next.
So this is our bit strings example for what's the uh,[COUGH] number of zero bits
in a ran, a random binary bit string. we talked in the last section about our
construction In the OBGF equation 1 over 1 minus z times plus u.
So now we'll start with this equation and calculate the average number of 0 bits in
a bit stream. And again we know the answer to this it's
going to be half. but this will illustrate the calculation
and we'll use the very same straight forward method for more difficult
problems. so how many binary bit strings are there?
Well we evaluate at u equals 1. So that's 1 over 1 minus 2z, and then
take the coefficient of z to the n. Now that's 2 to the n, so that's as
expected. to do the cumulated cost, the total
number of zero bits in all bitstrings of length n, we need to compute the partial
with respect to u of the OBGF. So to compute the partial with respect to
u, it's 1 over 1 minus z minus z u. all that's relevant is the minus z u, so
it's that to the 1 minus z minus z u to the minus 1 power.
so it's minus that squared and then uh,[COUGH] times the minus z.
The two minuses cancel, so the partial, with respect to u of that, is over here
on the right, z over 1 minus z minus z squared.
and to calculate the accumulated cost, we just evaluate that, at u equals 1.
So if u equals 1 that's z minus z, 1 minus 2z squared.
So we want for the accumulated cost, the coefficient of z to the n, and z over 1
minus 2z squared. and that's an elementary calculation.
from s, power series that, that it's n times 2 to the n minus 1.
And so now the average is just divide those 2.
and that's n over 2 as expected. so it's just computing the partial with
respect to u, which you know, once you've practiced a few times and remembered the
definitions, it's not so difficult a calculation at all, and it's certainly
one that can be done automatically nowadays.
so we're not going to compute the variance because there's an easier way to
do it that we'll talk about in just a second.
[COUGH] Okay now I mentioned the idea of horizontal, and vertical generating
functions that go with bi-variate generating functions, and so now, I
want to take a look at moment calculation using these methods.
so, let's look at the moment calculations in terms of the horizontal, ordinary
generating function. So that's a generating function that
gives the cost for an object of a given size.
So what we do is we take the coefficient of z to the n, in the bi-variate
generating function, and we'll call that little p sub n of u.
It's a generating function for the cost and all the objects of size n.
and it's just the sum over all objects that are of size n, u to the cost of that
object. and again that cheat sheet over here in
the terms of, of p and k that's that's a sum on kp and k, u to k.
So it's the generating function for cost. and so that's only got one variable, and
since we're interested in knowing the number of objects of size n and the
average number of zero[UNKNOWN] an object of size n, we can use that generating
function directly to get the answer that we want.
So the first numeration if you evaluate that, u equals 1, you get the number of
objects of size n. so that's just evaluating the UV 1 that's
summing the for all values of k the number objects of size n cause k, that's
equal to the number of objects of size n. So this paying use the useful thing both
the numeration and for accumulated cost. If you just differentiate the function
and evaluate it at 1. Then at some kpnk, which is your
accumulated cost, qn. So if we know that pnu evaluated at 1 to
enumerate, differentiate evaluate at 1 to get the accumulated cost, and just divide
those 2 to get the mean. and even simpler calculation usually.
And then the calculation for the variance just involves the second derivative.
And again, that's easy to check from the definition, of the variance.
So this method, using horizontal ordinary generating functions, is the one that we
use most often, to calculate average values and other moments of parameters.
So let's look at using this example for 0 bits and bit strings.
So again, that's our starting point, the 2 variable ordinary binary generating
function. the horizontal version is the coefficient
of z to the n in that. The coefficient of z to the n in that is
1 plus u to the n. It's equal to sum of over n of z to the
one plus u to the n and so that the coefficient of z to the n.
That's our horizontal ordinary generating function.
So now we can do the two steps to get our average.
First, enumeration, evaluate at one, you get two to the n immediately.
U equals one, two to the n. To get the accumulated cost we
differentiate with respect to u and then evaluate at one.
So differentiate with respect to u brings down an n.
and then evaluate at one to the n minus one immediate.
And so the average is the ratio of those two, which is n over 2, as we expect.
And then taking the second derivative, and then, adding mean subtracting the
mean squared, immediately get, n over 4. and that's an easy calculation that tells
us that the standard deviation, is square root of n.
the average is n, and what that means is that the distribution is concentrated.
A typical value is going to be close to n over 2, and I'll talk to you, in just a
minute, about what that means. For now, the point is that, given a 2
variable obgf, if you can extract the coefficient, of, us, z to the size, then,
you get a generating function that's easy to work with to, calculate moments.
Now we can also do moment calculations with vertical ordinary generating
functions. I put this slide up for completeness.
I'm not going to spend a lot of time on it because actually I, in the lectures,
we're not going to do any derivations this way.
but it's the. same idea, just on the other variable,
the vertical instead of the horizontal. If you take the coefficient of u to the k
in the ordinary bivariate generating function, you get the generating function
for the cost of objects of size k. And it's the same idea, you're just
holding the cost constant. And that's sum of p and k z to the n.
And so to enumerate we do it the same way, with the the bi-variate generating
function. But, accumulated cost is a coefficient of
z to the n in sum of kqk of z, where. q k of z is the bivariate generating
function. So we're, have to extract another
coefficient but there's some problems where it's easier to do the calculation
this way. and so, and it gets down to the mean
again, and you could do the variance the same way but I'm going to skip it.
so and again this is just for completeness this is not the way to
determine the average number of zero in a bitstring but and some mechanical as you
might do it and it illustrates the idea. So if we pull up the coificant of u to
the k, we get the vertical generating function.
In this case it's z to the k over 1 minus k to the k plus 1, and then we enumerate
same way as before to get the 2 at the end, but the cumulated cost is
coefficient of z to the n in sum on k, k times the vertical ogf...
and that's a familiar, geometric series, with with an extra factor, and here's the
details, for those of you who are used to those sums, that sum evaluates to z over
1 minus 2 z squared. the coefficient of z to the n and that is
n to the n minus 1 so we get n over 2 as before.
And again, in this case there's more work to get the same answer, but in some case
is where it's less work. And it's just a matter of the order in
which we extract the coefficients, usually, it's better to use the
horizontal where we extract the coefficient z to the nth first.
and in this simple example, we're always getting N over 2.
So why the, the focus on the moments? Well we're always interested in the
average, what value can we expect. and, this is classical in probability, so
I'm just going to then take a slide to mention these.
These classical results. So, if we have a random object of size N
with mean use of N and standard deviation sigmus of N.
Then we have these famous inequalities, the Markov inequality and Chebyshev
inequality. It, it says that the probability of being
much larger and small, or smaller than the mean, must decay.
And an upper bound on the rate of the decay is measured in units given by the
standard deviation. That's why the standard deviation is
important. The Markov inequality says, you're not
going to be, too many standard deviations away from the mean.
the Chebyshev inequality, says that the probability that you're, t standard
deviations away from the mean is less than 1 over t squared.
so actually, we can get much more accurate results than these for many of
the things we study cause we have the full distribution.
But still the basic idea is the same and what we say is that if the standard
deviation is of smaller order of growth than the mean then we call the
distribution concentrated because the means that as in gets larger the average
value tends. Towards the mean.
We can think of the mean value as a typical value.
We can calculate out some specific bounds but usually it suffices to, in the
analysis, to learn that the distribution is concentrated.
And we move on knowing that we could do more detailed analysis if we want.
So that's, this is just a formal statement of that.
If a distribution is concentrated, then then your value of your random value over
the mean approaches one in probability, in a very specific sense.
so, when it's concentrated we say the expected value is typical.
That's the one that you really do get expected to get.
And this is just, an example for a random bit.
If you have 100,000 random bits. You expect about half of them to be one
bits and about half of them to be zero bits.
the standard deviation is, of that, it's square root of N over 2, so this, it's
only about 5,000. So that says that the probability that a
value, the random value that you get Is between 49,900,000 and 50,100,000 is
better that 99%. That's a kind of result every one in
practice with really high probability. We have a good idea of what the value of
the random variables going to be. That's what we care about or
concentrated. Uh[COUGH] so this is just a plot of this
distribution, which is the binomial distribution.
as n increases, there's another curve. and so what it shows is that as n gets
higher, the curves comes tighter and tighter together towards the mean.
and so that's just true in many, many cases.
In fact, this particular curve describes lots of distributions.
we'll get to that later. Alright so here's just another example
really generalizing our number of zero bits example.
so let's talk about the class of all M-words.
so that's just Uh,[COUGH] strings with every you know, integer between one and m
or sequence of sets as we talked about last time.
so the size again is going to be the number of letters of a length of the word
but let's take as a parameter the number of occurrences of a particular letter in
the word. So that's our bi-variate generating
function, so to now construct that we use u to mark one the letters, a particular
letter, and then we don't mark all the others.
So that's n minus 1z. So we had m equals 2 before, we had to
use z plus z. Now we have general m.
It's in minus 1z. And that immediately translates to 1 over
1 minus, N minus 1 plus u z. We have N minus 1 z N u z, and that's it.
So now that's our ordinary bivariate generating function, if we want to
enumerate, we just evaluate that at u equals 1.
Evaluating that at u equals 1, then we want the coefficient as z to the n and 1
over 1 minus mz. That's m to the n.
So that checks. and if we want to the accumulated cost,
we differentiate with respect to u, and find the coefficient of z to the n.
and that's the same kind of calculation that we just did for 2.
and we get n m to the m minus 1 So the average number occurences of a given
letter, in a random n word, within n letters, is n over n.
And again, that's as expected. and we can also go ahead an compute the
variance, and it's n over n minus n over m squared.
and the square root of that, then, is proportional to the square root of N, so
,uh, it's concentrated. And that's a, direct analysis, using the
symbolic method, followed by, calculations using partial derivatives,
the basic method that, we're going to use to evaluate parameters.
And, I mentioned the practical application of hashing algorithms, and
this is from, our algorithms books, or Kanuth book, or, any, book on algorithms.
Where uh,[COUGH] we, organize a table of values, by, hashing them to random values
between 0 and N Input are n items into m keys interested into length of all the
list because we are going to have to search the list sequentially.
so that's the strategy, I was never interested in was the average number of
keys on the list. and again it's trivial that the average
is N over M but that's also what we just proved with the symbolic method.
Uh[COUGH] but the extra analysis to get the standard deviation.
tells us that it's concentrated which means as n increases it's going to that
values going to be typical. and that's useful to know in practice.
And we're not likely to have that case where they all fall on one list and
nobody falls on the others. So[COUGH] that's just one practical
example in many-many of the applications that we look at.
What we want to do is find the average value, show that the standard deviation
is of small order and that's the case in many-many-many of the applications that
we study. So that's the process of calculating
moments from the ordinary binary generating function.
and again, with the illustration, from familiar binary numbers, but, also one,
practical application. next, we'll look at applying these same
kinds of calculations in other applications.
[BLANK_AUDIO]
