Transcription
Welcome back. Okay, so in the last lectures, we have introduced this exponential distribution, uh, uh, and related it to the Poisson process. So, roughly speaking, if you have a string of events, uh, that come in at some rate Lambda—like emails, let's say—and so these events happen at times T1, T2, T3, and so on, and there are waiting times or arrival times, uh, between each of these, um, these events. We know that each of these arrival times or waiting times are exponentially distributed random variables, and the number of events I expect, uh, to see in an amount of time T is a Poisson distributed random variable with a parameter Lambda times T. That's pretty straightforward, really intuitive, made a lot of sense.
Um, there is a generalization of the exponential distribution. So, exponential distribution gives me these waiting times between events; there is something called a gamma distribution. I'm going to write it over here. I think there's something called a gamma distribution. Sounds really cool. A gamma distribution, um, which essentially gives me the waiting time for the Rth arrival. The waiting time, uh, for the Rth arrival is going to be a gamma distributed random variable. Okay, so the—so I might know, you know, I know the waiting time for the next email is going to be exponentially distributed, but how much time do I have to wait for the 10th email from now? It's not just, you know, necessarily 10 times my exponential distribution; it doesn't work like that. So we have this, um, this, this variable T, and I'm going to call it—maybe I'll do it in blue because this is, you know, a waiting time—so this TR, the amount of time I have to wait for my Rth email arrival, is going to be the sum of R waiting times. It's going to be W1 plus, let's call them W, W2 plus . . . plus, uh, WR, and we are going to say that this random variable TR is distributed according to the gamma distribution. I'll write it down in a minute: Gamma of R, comma Lambda. So this has two parameters; the exponential distribution just had one parameter Lambda. Gamma has two parameters: Lambda and the number of events I want to be waiting for. Okay, pretty simple idea.
Now, deriving this gamma function is a little bit messy. I'm going to give you the broad brushstrokes, and I'm going to omit the nasty math in the middle, and if you like, you can do it yourself and derive this from, uh, from those steps, but you don't have to; you can just, you know, take my word for what this distribution is if you like. Okay, so the way that we compute, uh, this, um, distribution is again, we rely on a Poisson process. We say the probability that the waiting time is greater than some T, some little T, is equal to the probability of my Poisson process. Let me write this down: The probability that my, my waiting time TR is greater than some specific time T is equivalent—this is an equivalent statement—that the number of events that happened in T less than T is R, is less than or equal to R minus one. So this is equivalent, uh, to the probability of my Poisson process having a number of events NT being less than or equal to R minus one. Okay, and I'm going to, I'm going to clarify what I mean. This is a messy—so this is the probability that my, uh, continuous waiting time for an Rth arrival, for the Rth arrival, is greater than some time T. The only way that that can happen, that my Rth arrival is bigger than time T, is that the number of events in that time T, the number of Poisson events, the number of Poisson events, uh, events in time T has to be less than or equal to R minus one. If I have R or more Poisson events in time T, then my, my waiting time for R events is less than time T. This is kind of a topology; these are equivalent statements, and I'm relating this probability—I want to compute this gamma distribution—I'm relating it to something I already know, which is this Poisson distribution, and so I can actually write this guy down. This isn't that complicated. So my Poisson distribution, um, I'm adding up the probability that N is less than or equal to R minus one is just the sum of the probability that my number of events is 0, 1, 2, all the way up to R minus one. So I'm going to sum from K = 0 to R - 1 my Poisson probabilities, which is, uh, e to the minus Lambda T times, uh, K, Lambda T to the power K divided by K factorial. I think this is, this is the Poisson probability of getting exactly K events, uh, in time T, assuming that their, these arrival times are distributed as exponentials, and this is where I'm going to stop deriving because it's a mess. This expression here is, um, this is actually a cumulative distribution, um, here, and this is the expression for it. So you can do some math; you can expand this out; um, this is the cumulative distribution; you can take its derivative to get the probability distribution that TR is exactly equal to T. Okay, so this is related to the cumulative distribution, um, this expression here, and you can take the derivative of the cumulative distribution to get the probabil, probability distribution. So I'm going to say . . . I'm not lazy; it's just I don't think this is worth your time to see me do this on, on a whiteboard on YouTube. . . . So the probability density function f of T, the probability that my arrival, my Rth arrival happens exactly at time T, is equal to e to the minus Lambda T times Lambda to the R power T to the R - 1 power / R - 1 factorial. This is the gamma distribution; this is the PDF of, um, of the gamma distribution, and this is super, super useful. So I have phrased it as, at what point does the Rth email come in? That doesn't sound that super duper useful, but you can use this for lots of other things. Um, imagine that I have a parallel process. I have, let's say that I have a string of Christmas lights, and they are in, um, in series or in parallel. If they're in parallel, what's the chance of the first light failing if I have, you know, if I have three lights, and each of them, uh, is an exponentially distributed random variable? What's the probability of the, the first failure if I have three of them? Okay, things like that. So I'm going to, um, give you an example that's maybe a little bit more intuitive.
So we are waiting in line for our driver's license at the DMV. So we're waiting, uh, in line at the DMV, and we know that it takes forever to get helped at the DMV. Um, this is an exponential process; you might as well wait for your light bulb to burn out before you get your license at the DMV. This could also be the grocery store or the post office, the bank; it doesn't matter. But let's say now, instead of having one lane open, they open up three lanes. So there's three times as many paths, um, going through this DMV. This could also be passport control at an airport. Okay, so now let's say that I have three lanes, and each is exponentially distributed; each is exponentially distributed with a wait time, with a wait time of 15 minutes. So if you like, the Lambda, the rate is 1 over 15; the rate at which people get through is one every 15 minutes: 1 over 15. Okay, so the, the probability now that I have three lanes that are each exponential—I'm going to draw a little picture here—so now I have this kind of this, uh, parallel process. Now the chance of getting through with three lanes—this is gamma distributed—so now my waiting time, if there's three lanes open, this is gamma with, uh, three lanes and a 1 over 15 L. So this is Lambda, and this is R, and you can convince yourself—you can kind of slow down and really think—does that make sense? Does opening three lanes at the DMV where each of them is exponential, is that the same as this waiting time? And it kind of is. If I'm like, you know, if I have, uh, three of these lanes open, it should actually be, um, uh, you know, it should be this process here. Okay, so I want you to, um, go through this, really convince yourself of this. This gamma distribution is also super useful; it kind of generalizes the exponential distribution either for having, you know, multiple, uh, waiting times, waiting for the Rth event, or having like multiple lanes open. Um, I think there is a bug here because I actually think this is going to be longer than exponential 1 over 15, so I think somehow I need to correct for that, but maybe this will be a homework problem: is like really carefully go through this and figure out exactly how these are related if I open up lanes. Um, this is the rough idea though, is that if you have multiple, multiple—okay, maybe this is a better way—maybe at the DMV I have to talk to three different people. This is worse. So now I have to go to talk to person A that has a waiting time of 15 minutes; I have to go to talk to person B that's got another 15-minute waiting time, and I got to go talk to person C that's another 15-minute waiting time. This makes a lot more sense that if I have to do these exponential processes in series. Okay, so I have to talk to person A, then person B, then person C: A, B, C, and each of these is exponentially distributed with, uh, an expected wait time of 15, then my total expected wait time is this gamma distribution. So the homework problem is, um, okay, so this is for the series where I have to talk to three different people in three different lanes; I have to wait in three lanes. I want you to think about the other problem, which is what if I actually, you know, I'm at the grocery store, and the wait time of each lane is 15 minutes, but I, but now there, there's three lanes that open up. How do I, how do I adjust this to go from series to parallel? That's a really good homework problem. Um, I'd like you to think about—I know that's what I'm going to be thinking about tonight, Saturday night—it's gamma distribution night. Okay, thank you.