Video 7-3: Probability theory recap

0:02 Before we continue the discussion of actual randomized algorithms, I'd like to take a step back and um uh for one uh it's kind of two steps back. Uh I'd like to properly define what it means if a randomized algorithm um runs and has a certain running time uh in the uh where the possibility is that it it doesn't ever finish. This is something we'll have to be we'll we'll be confronted with and we'll have to find some some proper solutions for that. And to properly handle randomization in general and this particular problem in in particular uh we'll need some background from probability theory. Much of this will be uh repetition from some kind of most computer science curricula have some un probability theory in them. uh they may differ in how formal they get um and so most of it will be repetition. I didn't want to include more than necessary but really there was there was this one bit where we need a little bit of a more abstract view on probabilities. Okay. So without further ado, I will visit revisit some key terms also to make sure the terminology is known to everyone also the English terms and um have a place to look up notation.

1:27 As always in computer science, uh we'll mostly deal with discrete things, but it turns out we can't fully avoid continuous or more general probability spaces. And sometimes uh continuous is just a convenient way to analyze things even if the underlying process is discrete. So what's um what's this all about? Uh if you want to formally speak about probabilities and what does it mean that something is random and how can you quantitatively make statements about it uh the first thing is you want to settle for some some framework where you can assign things a probability and that's what um a probability space is about. Uh the easiest case is the discrete case. You have some ground set. These are the things that can happen at the basic level. Um let's do a concrete example. Uh a fair die, standard six-sided die, no fancy uh roleplay things. Uh then the possible outcomes are just the number of let me let me draw it like a graphical way to just to make sure that these are effectively arbitrary objects. And that's not a nice five.

2:56 So represent these as like um abstract symbols. We're also in the city of the blind. So uh it's almost almost looks like braille, but of course it's not because it's three columns, but okay. Uh just um some some abstract objects. I guess I should have drawn some some uh shapes around this to make it even nicer.

3:22 Uh so this is this is the different sides that a six-sided die a cube can come up with. Uh that's the the underlying um uh uh event space or do we have a name for omega? Does anyone know? It's just the the basic events I think that's the one thing. So you have to say in a random process what what is the possible things that can happen and then the second important bit is we have to assign them probabilities. That's the whole uh the whole purpose of this. And so I I'll always denote probability by this uh double stroke um blackboard font P um just to have it a little shorter than than spelling out probability or something like that. In principle this is just a function. In the discrete case it maps subsets of our um uh ground set to probabilities.

4:23 But really um it's it's determined by giving the individual uh elementary events some probability weight. And so here uh in the case of our fair die, we would say the probability of each of those is just uh one over six if it's a fair one. Okay, I already regret drawing this uh in different colors just as one example. Now, of course, you can um in in this case, let's let's define it for all of the faces to be one over six. That's a fair die. But you could also have uh kind of cheating die where maybe the six comes up more often. Uh once you defined for the elementary uh outcomes what the probability is, you just sum up. If you have a a larger set in the general case, we have a set of these and you just sum up the weights. That's super boring and trivial, right? So, um uh the reason why I spelled this out is to contrast it to the general case.

5:31 Um not everything is discrete. Now, here already things are not necessarily finite. My example with the die was finite. Omega is a is a a fixed size, but it could be a countably infinite set. That's all right. Uh, but we would still call this discrete because you can bjectively map it to natural numbers. That's what countable means. But that's not all there is. Um, if you want to talk about real numbers, then trouble already starts brewing. And uh, while we're at it, we'll actually need it slightly more general. So um again like a kind of normally for much of statistics and what you do with um normal data science things it's fine to stick to discrete or uh real valued continuous random variables with some some density or so. Um there's one point where we need to go beyond that. So in the most general setting a probability space uh has has the following minimal requirements. Again omega is some some set of uh okay I called it points here so elementary events the things that can happen um and then we have to speak about more carefully we can't do all subsets if omega is a continuum so instead we'll take what is called a a sigma algebra which is just a a collection of sets with some properties so these are all um sets over omega in the discrete case just take the power set but uh in in general you want a restricted set. We always need that the empty set is in there and then we want that it satisfies closure properties. So whenever some set is in this uh set f then we want that the complement set is in f and any countable union of sets in f is also in f. So you can uh you can reason about what this kind of structure looks like and that's the topic for a measure theory class that I'm I'm not so interested in. So we'll just steal the results and don't worry about why they are true. Uh what people might have heard of is the boral sigma algebra.

7:50 This is the solution for this problem in the continuous uh real case. If you have say uh omega all of the real numbers or the real numbers between zero and one then you can basically solve this um this question of what kind of elements can I look at or what kind of sets of real numbers can I sensibly look at uh by taking all the uh intervals uh say the open intervals from some number a to b and the closure under all these operations and that turns out to be a well- definfined sigma algebra. It has a name and you can define um probabilities on them. Why the whole thing? Well, in general there's sets where you can show you cannot sensibly define a probability uh by um designing them in a in a mean way. Again, this is this part of the theory is not relevant for us. So that's that's just listing the the minimal requirements and we'll be happy with those. Uh then the second bit as before we need a probability for all those um measurable sets. That's what they're called here. Probability in general is a measure. Measure just means it's a function that maps sets to uh real numbers.

9:12 And that also has some same same properties as above in a way. Uh but here it's only defined on those on this subset uh of sets. uh the solution for again for the real line is the leback measure where you assign an interval it's its length so the uh distance between the end points and everything else all the other sets in the boreal sigma algebra you can generate from these operations you can also express their probability using uh these operations and one property here is that if you have a disjoint set of events could be infinite but countably infinite only then the probability of their union has to be the sum of the probabilities that's for disjoint sets um okay is that uh questions up to this point so far I mean this is this just the most abstract definition um it's a bit hard to show in a concise way why this is needed. I'll I'll show you the example where we need more general probability spaces soon.

10:36 Then based on that a bunch of terminology this this will be repetition for sure. Um we have events. Events are just any of these sets that we can assign a probability to. They're called measurable sets in general. This is um just the requirement that but that that we want something that we can assign a probability to and straight from the properties because we required them. This is all straightforward to show. Um we define the complement of an event as just the event that this event the first event does not happen and that has the inverse probability. uh if we take the union of events that are not necessarily disjoint then the sum of the probabilities is an upper bound this is called the union bound it basically just follows from the definition of sigma algebbras but it's a very useful tool in analyzing algorithms because here you have virtually no requirements about these sets they can be arbitrary they can overlap the events can can be dependent and everything um but we can still upperbound their probability So we'll often use this to bound in an algorithm uh that something bad happens and that there's several ways in how something could go wrong.

11:50 But if you can just uh have an upper bound on the sum of the individual probabilities for what else what whatever thing could go wrong that's an upper bound for uh having anything go wrong.

12:10 Uh okay. So um if we have some events we can talk about independence and this is really uh just defined via their probabilities. Um events are independent if the probabilities factor. So if you take the the intersection that all these events happen at the same time then that has to be the product of their probabilities.

12:32 Um the usefulness of this definition is really that it doesn't need any intuition what independence means. It's it's a purely algebraic thing. We just uh check if the probabilities factor.

12:49 I'm not sure if we ever need this for infinite sets of events. I guess we do for for sequences. So whenever uh whenever we talk about an infinite set to be mushially independent what this means is that every finite subset is independent. Um the mushially independent is important. There's weaker versions where you just say every uh so here all the case sets together are independent which means they're uh the intersection of all the events at the same time has to factor. You could also take say pair-wise independence where you only take two out of these elements and check if their intersection is the product of these two probabilities. That's a weaker notion. Um and you can say in general a kwise independence. Um the higher the k the more restrictive and mushi means k is all of them. Uh that that sometimes plays a role. Uh it's just important to not mix those up but they're really an easy thing. So just again pair-wise independent would mean that uh for all I and J in our index set I'm talking about the same events a up a one up to a k here the probability for a i intersected aj has to be the product of their two probabilities.

14:17 But this does not in general imply mushial independence. There's examples easy examples you can um you can construct. I don't know. Do we need one?

14:37 Uh there was a cute one with the colors of edges in a triangle. Um so you color the edges uniformly at random in one or of two colors either red or blue and then you ask uh whether uh I think the vertices and then you can ask for each of the edges um does it have two different colors at its end points. And if you take any two of these edges and you ask um are my endpoints colored in different colors, then these are pair-wise independent. But if you take all three of them, they're not mutually independent. Um because if you know um the if you know one color you fix one color arbitrarily and you know these two then you know what the color is and then the third edge is determined.

15:46 So the events here would be A1, A2, A3. AI is at just two colors at end points and then um among this set A1 A2 A3 it's two wise independent or pair wise independent Okay, just just a a small example to make that point. This is you've probably seen some examples before.

16:38 The last bit we can do with events is talk about conditional probabilities. And uh in the end this all kind of just boils down to uh sets and subsets and kind of vin diagrams. Um so the probability that a happens given that we know that b happens if you think of the events as some subsets which really is what they are. uh if you if you know that B happens right then if in in general the size of A was its probability now it only becomes the size of A intersected B versus the overall size of B and that's exactly what's uh what's written here right I guess uh I could for all of B.

17:36 And of course, we have a problem here. If the probability for this event B is zero, conditioning on H B happening sounds like a bad idea. It's algebraically certainly a problem. Uh but also intuitively, if you uh if you think about this, you're kind of you're betting on B to happen and then you talk about how likely is it that A happens. If B has probability zero, this shouldn't make sense. Now, this is easier said than uh done. It sometimes could could um look very promising to condition on something and then you find out it it has measure zero, which is not always obvious. In the discrete case, it's obvious. In continuous cases, it sometimes isn't.

18:22 Okay, last bit is the um the law of total probability. is just a way of um reform formulating the the definition but it's is often useful uh as a tool to compute things. If you want the probability for some event A, you can rewrite that as uh conditional probabilities involving some other events. Now it's important that these other events form a partition of the entire space and then uh the proof of this equation is completely boring. You just plug in the definition. uh but it's it's useful to think about it as a kind of case distinction and whenever these conditional probabilities are easier to uh compute or evaluate um the law of total probability can help can help determine or compute things.

19:21 Okay, last um last very important uh terminology maybe not the last term are random variables. So so far we have set up the general universe probability spaces. What are the things that we can sensibly assign probabilities to without running into uh paradoxes and we've defined events which are really the things that we can assign probabilities to. Uh things really get interesting once you talk about uh random variables which are functions mapping these elementary events to some um some other uh some other universe. It could be anything. Often times we think of it as numbers so that we can um compute with these. And remember um I said earlier in our toy example here for the for the die um this omega was just some So if you if you define it like this then you couldn't be you couldn't sensibly talk about uh say adding up two dice but of course we could map all those to numbers.

20:39 So we could have x is the mapping to uh one to six in the natural way. You just count the dots. And that way we you can talk about the numerical value.

21:41 so boring example of a random variable. uh think of it as um a random variable can throw away information and then it can become um a more versatile tool. It could say we could also have y which maps uh this just to even and odd in the usual way. That's another random variable not mapping to uh the real numbers but yeah we'll see many examples where this will become clear. Uh now we have a new type of event namely that a random variable has a certain value. Um with the obvious definition it's um the set of all primitive events that map to the right value. Uh and we can define um so this was going from a random variable to an event. We can also go the other way around from an event to a specific random variable which is the indicator just saying yes or no zero or one does this event happen or not. So again this is this Iverson bracket which is uh one if the event happens if omega is in a and zero otherwise.

22:53 Okay then we can define a few terms. Most of these you'll you'll have seen. So if you have a random variable X and this is some real number here or at least something where it makes sense to talk about lesser or equal you can define the a cumulative distribution function as just the probability that this is below a certain value.

23:21 Uh if if X is discrete then necessarily also the the range you map to will be discrete. um for a continuous random variable where you start with something um that's not discreet, you could map it to something discrete or you could map it to something continuous. And if you map it to a right okay that's that's still the for the discrete case you can define the probability mass function is just for all the values in your universe here suppose that's discrete. So um if uh say that calligraphic x that's an h is the natural numbers then you could define something like this. Uh just the the probability of to have a certain value and that completely describes the probability distribution that random distribution. Um if you have some continuous random variable, you can still define this cumulative distribution function. And it's often useful if this is smooth enough to look at the derivative instead. And uh the derivative of the cumulative distribution function if it exists is the probability density function. That's again uh things you'll you'll have seen um the standard way to deal with most most continuous random variables.

24:55 Um uh and a slightly non-standard piece of notation is this equals with a d above it which I'll use to denote that the two random variables on the on the up on the sides of the equality have the same distribution. Formally, it just means that their uh that their CDFs are the same. Um this is there's there's many many ways people use notation for the same thing. I think this is it. It turns out to be very convenient if you um if you combine random variables. Now you can you can say uh x is equal in distribution to y + zed and if these are mapping to real numbers, it's clear what that means. Uh so you but it's a it's a fairly sophistic if you if you express this via the distribution function you're already talking about some convolutions and so on. It's is a nice way to express um what we want here equality and distribution without uh requiring special notation for standard operations.

26:01 All right. Uh we've talked about independence for events. You can also talk about independence for random variables and there the way to think about this is random variables here they can map to any kind of set x often we'll think of that as real numbers but it could also be multi-dimensional it could be mapping to uh r to the k and then we can um for for this vector x the vector random variable we'll just call these uh functions that we just defined the cumulative distribution function or the probability mass function or the probability ility density function. We call those the joint versions. And we can look at individual components of the vector and then uh look at the marginal distribution of that or the marginal functions. And now um a set of random variables or a collection of random variables is independent if they're joined distribution um their PDF or their PMF factors. For example, uh X and Y are independent if the probability that they together have the certain value. So X capital X is the the random X is equal to X random Y is equal to some Y that has to factor into the probabilities of the two events.

27:20 It it seems like it's the same thing as for events, but um I guess formally it isn't. uh but it naturally follows and um this is this I guess for discrete you can do the same for the probability density function and it does the right thing okay here's here's an important bit that's what we'll come back to many times iid sequences of random variables iid stands for independent and identically distributed and the independent stands for mushially independent Nobody says that, but it's implicitly there. So, this is often the starting point of some theorem. You have an iID sequence of random variables. Maybe they're all uh fair coin tosses. So, heads or tails or zero or one. Uh but you have an infinite countably infinite number of those and then you can work on from those. So, that's just what that formally means.

28:32 Okay. Uh I guess I lied earlier. This is another important term the expected values but you you will see you'll have seen about this. Uh if you have some random variable you can take its expectation and um for this really you need you need to be able to map this. This only works if you um map to some number or something where you can compute because here you're taking sums of of values that uh x can take.

28:59 Of course, the definition of expected value of x is the sum of all possible values times their probability. If that's the discrete case, if you have a density, then you take the integral. It looks very similar to the sum case. I guess that's a is nice here. Shows the analogy. uh you can also define this in general set measure theoretic terms where now the integral uh becomes a libec integral we won't actually need that so I think we don't need to talk about it could happen that a random variable does not have an expectation whenever that sum or integral doesn't converge then it just doesn't have a random uh well- definfined expectation that can Okay, important properties of the expectation are just following from the definition. Remember that it is a sum or an integral and these are linear. So if you scale a random variable by multiplying its outcome by a constant factor, the same will happen to the expectation. If you add up two expect the if you add up two random variables, the expectation of the sum is the sum of the expectations. you know this but it's uh good to keep in mind and uh as an important special case if two random variables are independent then their expectations factor. This again uh follows strictly from the definition but you need to do the math I guess to see it. Um if you can factor their probabilities then you can split away the sums and it becomes um becomes the product of two sums.

30:49 Uh note that here um this doesn't this doesn't imply the other direction necessarily. Uh don't know if there's a nice there's there's certainly an example but not one I can come up with now. Conditional expectations are a slight twist on what we had before. It's essentially the same thing. You just take whenever you had probabilities before, you now take conditional probabilities.

31:15 Um yeah, conditional expectation for an event I think is um there's somehow there's an x missing here should be multiplied by x. uh more important is uh the conditional expectation where you have um take the expectation of some random variable and the event that you condition on is another random variable having a certain value. This this often pops up. So it's worth mentioning as a special case here. And uh if X and Y are discrete, the obvious definition works. The um just replace the probability for X having a certain value by this conditional probability. Um if X and Y are continuous then in general you have to be careful with these kind of statements. Um because you're conditioning on an event of probability zero. If you have a continuous random variable that the f the probability that it takes one specific value measure of a point set is usually zero. But you can still sometimes define things via densities.

32:40 So if you have two continuous random variables x and y with a a joint density function um then you can define the marginal density of y by integrating x out. So just what it says here, you take the joint one, you integrate over the entire domain of x, but you keep y as a a variable and then you can define this conditional expectation properly using this uh marginal density. If you just go from the definition up here, you would be conditioning on an event of of probability zero. So this would not work. But if you have densities, you can give a sensible definition to this uh conditional expectation here.

33:28 Um the last thing I want to point out here is if you have some um conditional expectation of either kind discrete or or continuous uh you can actually um turn that into a a new random variable itself. So first of all, if you fix the value of of y, the little little y, you fix the value that you conditioned the random y to have, then that's a function. And now you could say I'm I'm uh I'm taking one random variable. I'm applying a function that's just composing two functions. That's again a random variable g of c of random y. And so we can denote this by this. But this this notation as as widespread as it is um you should keep in mind it really stands for one of these two things and um for example if it stands if if x and y are continuous but they don't have a nice density it might not make sense to write this could be uh not well defined.

34:31 uh but if it's well defined you can use the law of total expectation which is expressing some expected value by averaging over y and then inside taking the conditional expectation. Uh that's a one of my favorite tools because sometimes you can evaluate uh a hard hard to compute expectation by first conditioning. It's a bit similar to the law of total probability. Um the power can be a powerful tool. All right.

35:07 Uh pinky prom is last slide on this. Some famous distributions. Um there's no esoteric ones. You'll know those. I just wanted to have the notation somewhere written. So just a b with p will be uh the bernoli distribution. It's a a biased coin flip where p is the probability for having a one and otherwise it's zero. Then we have the binomial uh distribution which is the sum of uh n such coin flips where n and p are parameters. Uh then we can have the discrete uniform distribution. That's what the die was. So our random die again the random die has uniform distribution between one and six.

35:53 the obvious way. Let me just write this sloppily like this. Another thing that pops up um is the geometric distribution which is uh you have some some coin with a probability P of coming up as a one and you have now you count you keep flipping until it shows a one and the number of coin flips you needed in total is the geometric distribution.

36:31 Okay, the only continuous distribution that I um I'm using for sure is the uniform distribution for example over the unit interval. There's of course many many others but uh I don't think we need any of them.