Video 2-6: Probability generating functions

0:03 In the previous section, we've kind of handwaved our way through to an expected value for this for this number of characters before we see a certain string appear for the first time. And uh that's good enough in in this case where the difference is so extreme to get a qualitative statement. But suppose you want to uh to assign a specific p value or a probability to um if if you found an open reading frame of length 400, is that significant enough or uh or not? It's substantially longer than the expected open reading frame in random DNA. Uh but the expectation alone is not strong enough to give you much more. you can uh you could use maybe marker's inequality but the the bounds are very weak from that. So in in some cases and in this very simple null model in specific specifically we can get more we could get uh almost the full distribution of the number of letters until the stop code on comes and I want to just um briefly introduce a bit the the mathematical tool you can use for that.

1:13 It's a cute tool in its own right so um maybe you enjoy it. Uh the the tool is a a generating function. Um uh I wanted to ask you about whether you've seen it, but it's only 5 minutes left. So I'm I'm going to just introduce it and uh not much more um that we can do today. It only works if you have a random variable that has integral values and non- negative values or at least you could maybe shift it. But say here it's only natural numbers that's the possible outcomes of your of your random variable. In our case this would be the number of characters right until we see the stop code on. So it certainly qualifies for this. Uh then we can write down this weird thing um the probability generating function. It's the infinite series where we sum over all possible values for this um random variable. Then we take the probability that X attains this value K and multiply that with a symbolic variable set to the K.

2:22 So in in principle this is just a power series or just some you can interpret it as a function of set um a real or complex function of zed. And we'll mostly treat these as just symbolic algebraic objects to calculate to calculate with and use some uh equalities that make life a bit easier. What do I mean by that uh specifically is is is this one that's one of the um simple consequences just of the definition. Uh if you have the generating function the probability generating function of such a random variable you can compute the expected value by taking the derivative and inserting uh one for said. That's wild. How's that? Why is that or where does that come from? Um that part is is very easy to prove. Uh we look at first of all the expected value of x by definition is just this this sum over all possible values. Then the probability that x attains this value times k right that's the expected value as you've defined it uh for discrete random variables.

3:38 Now uh let's also compute what this derivative is and let me uh first leave set symbolically. Now the the piece of knowledge that we use here is that power series if you uh you can either uh argue with function um theory or uh uh you treat it as a as an algebraic object or you treat it as a tailaylor series. Um either way you can take the derivative of a power series by taking the derivative of each term. is a bit like um for finite sums this is always true. The derivative of a sum is the sum of the derivatives. Uh it's not obvious whether that's always true if the sum is infinite. Sometimes these things break but here it doesn't. So you just take the uh the derivative ddz of this this term in the sum.

4:46 And what's this derivative? Well, this probability doesn't depend on zed. So that's just a constant. So this thing is the probability and this thing well that's a polomial. I know how to take the derivatives of that. It's k * set to the k minus one. Okay, that was easy. Now the sum in front stays. So you've turned one power series, this one, into a new power series, this one. And it just has slightly changed terms. And now if you insert zed equals 1, this guy just goes away. And what's left is exactly the sum of the expected value. So it's kind of duh uh obvious uh when you write it down. Uh the reason why it's useful is that if you can write a a closed form for this infinite sum, it might be much easier to use whatever computer algebra or your uh high school math uh um calculus knowledge to take the derivative of these functions and insert one. That's a simple operation.

5:59 And you can uh go further. You can also take to get the variance. Um this needs uh a slightly uh slightly longer calculation than this but only twice as long. Um but maybe we'll uh postpone that. And then you get uh the variance. All you need for that is the same ingredient first derivative at one and you need the second derivative at one as well. But these are usually also easy to get and in particular for our uh concrete ones. Um, we'll look more into this next time.

6:46 but let me just show you here again uh as a kind of preview how you could use this. Forget the calculation of how you get the generating function here. You can essentially go from the automaton again. And I'll explain this next time in a bit more detail. Sorry, super small. Eh, doesn't work.

7:06 Can I zoom in? No. Okay. Sorry. It's a bit small. Um, one thing about Mathematica is that the interface is not so great. You can you can calculate the generating function. It's this simple rational function. So, taking derivatives is not too hard. And you can take the derivative. you find the 64 over3 again as we've had and you can compute with this formula the variance which is well this number uh what what's more interesting or more intuitive is the standard deviation which here is is 18 2/3 and so from from these two you can already get a much stronger quantitative statement of how unlikely it is to see an open reading frame of length say 400