Video 2-7: Probability generating functions part 2

0:02 Uh what I want to get back to is doing more than just the expected value because that here is maybe even good enough because the distance the difference between what we observe as open reading frames and actual genomes and this expected value is so large that you can possibly stop there and say um I'm uh it's qualitatively so big a difference I'm not going to do real statistics but suppose we want to do real statistics and calculate the probability that we see such a large reading frame under the null model. Uh a nice general tool to get more information about the distribution are these probability generating functions.

0:49 Uh we defined them last time already. So I'm going to quickly over uh if you have some random variable it has non- negative integer values only then you can write this kind of series could be infinite or could be finite both works and uh that's a formal power series or you can you can also say it's um um a representation of a function in terms of its power series and so that's a function in some variable said we'll mostly treat it as a symbolic object and that's where we left off. Uh one convenient thing is to compute the expected value of such a variable if you have the probability generating function in a convenient form. That's easier to do than from scratch because you can just take the derivative with respect to set only one variable. So just the ordinary derivative and then sets set to one and that's going to give you the expected value. And here's the proof. It's very simple calculation. Uh all you need to know is that the derivative of a sum is the sum of the derivatives.

2:01 And uh that means we take the derivative inside the sum here of each of these terms. And that gives us precisely uh this formula once it's set set to one that one just goes away. So if I was to insert one here instead of uh the general set after taking the derivative then uh this goes away. So the whole thing is kind of just gone. Let me if I strike it through. Can you still see it? I think it's clear what happens. And then this is just the definition. um of the expected value if you're keep the whole thing with the sum in front.

2:48 So that's that's cute. Um but maybe not so exciting because we knew how to get expected values even before this. Um the nice thing is it also works for for other moments and we'll look at the variance as an example. And there the formula looks a bit more more annoying to memorize but maybe you don't even have to. Uh the kind of trick that happens is the very same if I take my uh my derivative here but now I take the second derivative of this um inner part just the sums.

3:29 Well, I can't do this really in one shot, but we have the first ones uh here. So, it's not too bad not too bad to do.

3:39 That's just a constant factor if you look at it as a function of zed. Uh same for the k. Now, we have another polomial. Essentially, that's going to be uh the the same pattern. And I guess technically this is only true if k is greater or equal two. Um for the smaller ones we don't need to worry because then there's a factor of zero in front and the whole thing is zero right for those for those small powers of k the factor in front will will kill the thing.

4:17 Okay. Um so if you sum up just this part so again if you set to one this part goes away and we have the probability to be exactly to have value k and then we have some something that looks similarish to variance uh but not quite what we would want for the variance is you can say it's the expected value of X minus its expectation squared.

5:00 So we sum over all possible values for K say K greater equal zero again probability for X to be K and then this lovely thing and we already know what this is right this is uh exactly this term so that you can insert And uh the easiest now is is uh to move backwards. Um if we uh look at this this term on the right, let's let's expand this uh one more step. Okay. Going to write it again.

6:01 We have uh k^ 2 minus k 2 k Then uh you can expand this one out. That goes completely out of the formula. This last satan doesn't depend on on e of x. Uh this is a constant so it can go outside. Um so here we have the k squ. Um, And here this is already easy summing probabilities. So that's going to sum to one.

7:57 So this one's our expectation again, right? So we have uh 1 e x^2 - 2 e ex^ 2. That leaves us with a 1 - e ex^ 2. And and this one we can split up again to look a bit more like this one. k ^ 2 is the same as k * k * kus 1 + k.

8:28 And that's where we have another E of X from. Okay. Uh maybe there's a more elegant way to do it without as much uh calculation. Um the nice thing about this taking derivatives of the probability generating function is it generalizes to higher moments without much problems. As long as you can take derivatives, uh the rest is just some road calculation.

8:55 uh we'll leave it with um expectation and variance. Then you can uh you can use typical statistics on it or you can use uh chev inequality to get get bounds on large deviations these kind of things. uh you'll look at that in the tutorials a bit. Um let's also look at some example for concrete distribution where maybe I can convince you better that uh it can be convenient to use these pro these generating functions. Uh, sorry there's there's the view part on the slides missing it that I didn't copy. Good.

9:47 We don't want to do this from scratch. I'm sorry. that essentially is will be answered in the tutorials. So, while we're there, this depends a bit on your assumption. Um, one or the other could be more sensible. And, um, it's I think there's no definitive answer that says one or the other is more correct. Uh it depends what you assume whether you can reliably with the start code on detect uh the right position or if you also have to live with the fact that it might be offset and you still want to define reading frames. Uh so you look at both options. I did the one in lecture that gives the more interesting math as you'll see in the tutorials. The other one is is easier to deal with.

11:28 Okay, with the slides that have the update that is not online yet um I don't have to write this example from scratch. I'll use this notation throughout. So uniform and then the set just means the uniform distribution over this discrete finite set. Uh here it's the first n integers where obviously we start counting at zero. So every value with every value with probability 1 / n. Then the probability generating function is just a polomial is a finite sum of powers of zed and the common factor the probability is always 1 / n. So I can write this like that. Now that's just by definition. Uh the the power of this comes in because I can do algebraic reformulations of this term in particular. Uh just in case people might have forgotten about this, there's the TCS cheat sheet and there's a formula for summing up powers um from zero to n. So that's exactly the form we need.

12:40 And if you do that here, take these the first um n power. So uh the formula on the sheet went until n. So I had an n plus one here. In our case, it's even more even more convenient. It starts stops exactly at n. So we can rewrite this sum in closed form. Okay. Uh so it's shorter to type. And now we can take for example the derivative of this thing and set it to one or I take the limit as set goes to one and retrieve tada the expected value of a uniform distribution. Um what is a little less easy to do in your head is the variance. I never I never I can never remember. I always have to look this one up. But if you're say stuck in a lecture room and would have to reconstruct it and that would be the one that I think is most foolproof so that you can do it without making calculation errors. Um okay uh let me just for the sake of the argument show that you can do this in in Simpai if you wanted.

13:46 Um, it's the same we started with before. That's this one. So, just to show you that very little code suffices is a little bit of a a plug for for Python here. There's this symbolic computation module in Python. And we import some functions that we're using here in and the next few cells. You have to define symbols. That's what you're working with in the formula. But then you can write down terms in a very natural form like this uh generating function here. You just express it as a standard Python expression and you can take derivatives and you can set things to one with the subs function that we've seen last time and is used here as well. Now if you do this in this one uh you get a zero by zero because you have this uh z minus one. Uh there's a a root in the denominator and a root in the numerator but they actually cancel if you look at it carefully. Uh a simple way to do this is to compute limits which sai also is uh for this simple for these simple cases is doing uh very well.

14:56 I'm just showing this also to bit to educate you about um tools that are convenient to use and you can take derivatives twice um add the expectations subtract the square of the expectation that's just from this variable here and then you get the variance of uh the uniform distribution of the first n integers okay I find this cool I don't Now if uh enthusiasm sprang over there's one more cool thing that I wanted to show there was this is if you have the probability generating function of some random variables you can um and they're independent stochastically independent you can get the generating function of the sum of the two very simply as the product of the generating functions. If you write this down this is nothing but the convolution. So uh what does it mean to to um multiply products of this form? Uh let's let's take the symbolic general form.

16:06 I have two generating functions. They'll be of this form in some for some sequences ak bk. The product is also a a series and at the kth term it has a sum of all the options how I can build k and think about this as uh the finite case is two polomials you multiply every combination of terms and you combine all of the terms where the resulting power is exactly k right so you can have from the first series one contribution ution set to the L then you get a L and you multiply that by b K minus L and uh that's one of the terms that you're summing up for the resulting uh sum where the power of set is K.

17:09 In a way, this is just the definition of how you multiply power series. Anyways, it follows from the usual laws of how we do this for finite cases and it works just the same if the sums are infinite series. Um, and for the probability generating functions, what you get here, A L and B K minus L, that's the probability that X is equal to L. That's the probability that Y is equal to K minus L. If they're independent then the probability that they jointly have these two values factors and then you get exactly that uh this is the probability for x to be l and y to be k minus l of course then their sum is k and there's all you sum up over all different options for the value of x say okay simple uh that formula is also somewhere on the cheat sheet um if you can't remember it. Let's do a quick example here as well.

18:12 This one I also find very useful to memorize stuff. Uh say you have rely random variables. So just coin flips with a bias. So they come up with probability P to be one and zero otherwise. Uh then the probability generating function of this of this simple coin flip is very easy. P * Z for the one case and the other case. Now standard binomial distributed variables are the sum of N of these things and that means independent uh burly trials I should stress. Um this is not on the slide anywhere. Okay, I guess all need to be mutually independent. Um but standard stuff uh I'm not telling you much new. The probability generating function of this binomial random variable though is then the product of all these individual ones. The product of these is all the same. So it's just the nth power of that uh generating function. Okay. Uh I I rewrote this here so that it's clearer how you take derivatives because that's of course what we want to do next. uh if you want to compute the expected value of of y, I know that's a bit silly. You just want to go via the definition, but you could just take the derivative in in this guy and set set to one. So what you get is uh the inner derivative is p and the outer derivative is the n the power goes down and then the inner with power n minus one. If you set set to one in this one, you notice that the p here and the minus p always cancel and you get a one to some power which just goes away. So n * p as is obvious from this uh stochastic representation.

20:08 The expected value of one of the x i is p and we got the sum of n independent copies. Okay, that's not hard to do otherwise. But the variance I can never quite remember. Uh and you don't have to. You can take the formula from before. Um if you take the the second derivative and plug in then you get this this lovely term and the other two are the expectation minus expectation squared. And you can rewrite this in the somewhat more typical form. N * P * Q when you set Q to 1 minus P. It's the the one I learned in school. Uh yeah, maybe in school. I don't know. Also here very briefly like um it's a proof of concept. There's the calculation. Uh and you can even um you can use simplify to do the combination of terms I showed you. Uh simply immediately gives gives this representation as the shortest.

21:12 Okay. That's all on on the generating functions uh that um directly connects that that directly like um goes from the definition. Um I promise that we come back to this automaton. So, let me take a a copy of this one.

22:03 We can apply the same approach that we did for the expectation um with the full distribution. If we say that uh our our x and then the state say uh p for prefix um that is now the generating function of the number of steps from this state till you reach an absorbing state.

22:32 We can write that down. It's the probability generating function of the number of steps. X is a strange letter. Let's say this is the number of steps as the random variable to some absorbing state. And that's a random variable now. And we could say GP offset as the generating function and then you can do the same kind of reasoning as before. Uh let me do an example. So the g ua which is a an absorbing state there's no further steps to be taken. So it's the deterministic constant zero uh which means the probability generating function is just a one z to the zero and let's do the ua for example.

23:47 Maybe this doesn't need to be quite as small. If you look at the UA, there's some chance with probability 1/2 it goes to one of these absorbing states. But let's write it down um explicitly. So we do one more step. There was a plus one in the original formulation. Now we have to uh treat this as the sum of two independent random variables. One of which is the deterministic constant one and the other is as many steps as I'm taking from the target state. So the constant one has a generating function of just set set to the power one. The product of the probability generating functions corresponds to the sum. So I'm I'm multiplying and here I'm going to just take G UA that's uh what I get in this first case. Then I get symmetrically for the second UAG. Now I know it's silly these are just one. I could have inserted them straight away. But here this is showing the general pattern. If you go with a u back to this place, then uh you get the same pattern and just the there's a gu now instead of this one. And the last term goes back to the start state.

25:19 And you see how you can read this off from the automaton without thinking like the first part here is even the same all the time. Okay. So you can equally form um a system of equations. Don't be scared because there's a variable set flying around. It's not biting. You can just uh symbolically solve the equation the same way and you'll get some solution for uh the gaps um as a function of of zed. All the others can can be eliminated because you have as many uh equations as variables. So you can you can determine the exact representation for all of the states but we're interested in the one from the start state. Um again uh this this I prepared. So here's the full list of equations is again written in this uh simp convention where an equation has to be rewritten so that the right hand side is zero and then you just give the left hand side that's the start state and I'm subtracting well there's 1/4 chance of going to U and there's three4 uh of a chance of staying in the start state and you You can check in the automaton that that's what happened. Let's do the um the UA one was the one we did. We you really see how these are very regular and essentially just giving the automaton edges.

26:50 Um if you solve that that's the same code as last time. So I'm not going to explain the simp specifics again. is a sol function where you give equations and variables and then you can get the uh the solution is is a map from the symbols to the solutions. What we care about is the one for t. So it's t as a function of set. Uh you can set set to one. What should be the result of this one?

27:24 Double checking if people are uh are here. That's the solution for the probability generating function of the start state. So the number of steps we take from the start state. Um but I'm just inserting set equals to one. So that thing will just sum up all the probabilities. It has to be one.

27:44 Um if I uh okay if I substitute zero uh I guess I get the probability that it takes zero steps which should be zero in this case because from the start state we have to take at least one step. Then we can take derivatives and insert one in the derivative that gives us the expected value. That's what we already know but we should double check. And then uh we can take the second derivative and compute the variance. I don't know why this is underlined. Um I think the code runs fine. This is the generating function. The way it's determined it's from a set of linear equations. So it's always going to be a rational function. This is uh maybe not not so obvious but you can prove this is always leading to a function polomial divided by another polomial. And you can these are very tame to work with but we're not going to dig deeper into this here. So t of one was one summing up all the probabilities.

28:45 probability to use zero steps was zero as we said uh that's the expected value same as we had last time if you uh if you look it up and the variance is well whatever some number but uh more more intuitive I think is the standard deviation and so if you do this um cowboy statistics of saying expected value plus minus one standard deviation is a reasonable confidence interval then um you're still far away like you're still within a couple of dozen bases in an open reading frame of a random DNA far away from the length of actual genes which was usually thousands of bases.