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.