In this segment, we're gonna continue with a few more tools from discrete probability, and I want to remind everyone that if you wanna read more about this, there's more information in wiki books article that is linked over here. So first let's do a quick recap of where we are. We said that the discrete probability is always defined over a finite set, which we're gonna denote by U, and typically for us, U is going to be the set of all N bit binary strings, which we denote by zero 130 N. Now a probability distribution P over this universe U is basically a function that assigns to every element in the universe a weight in the interval zero to one, such that if we sum the weight of all these elements, the sum basically sums up to one. Now we have said that subset of the universe is what called an event, and we said that probability of an event is basically the sum of all the weights of all the elements in the event and we said that probability of an event is some real numbers in the interval zero to one And I would remind everyone the basically probability of the entire universe is basically the one by the fact that sum of all the weights sums up to one. Then we define what a random variable is Formally, a random variable is a, is a function from the universe of some other sets But the thing that I want you to remember is that the random variable takes, values in some set v And, in fact, the random variable defines the distribution on this set v. So the next concept we need is what's called independence And I'm gonna very briefly define this If you want to read more about independence, please go ahead and look at the wiki books article. But essentially we say that two events A and B are independent of one another if When you know that event A happens, that tells you nothing about whether event B actually happened or not. Formally, the way we define independence is to say that, the probability of A and B, namely, that both events happened, is actually=to the probability of event A the probability of event B So mult iplication, in some sense, the fact that probabilities multiply under conjunction, captures the fact that these events are independent And as I said, if you wanna read more about that, please take a look at the background material. Now the same thing can be said for random variables. So suppose we have two random variables x and y. They take values in some set v. Then we say that these random variables are independent if the probability that x = a, and y = b is equal to the product of these two probabilities. Basically what this means is, even if you know that x = a, that tells you nothing about the value of y. Okay, that, that's what this multiplication means And again this needs to hold for all A and B in the space of values of these random variables So, just again to job your memory If you've seen this before, a very quick example. Suppose we look at the, set of, of two bit strings So, zero, zero, zero, one, one zero and, one, one And suppose we choose a random, from this set. Okay so we randomly choose one of these four elements with equal probability. Now let's define two random variables. X is gonna be the least significant bit that was generated, and Y is gonna be the most significant bit generated. So I claim that, these random variables, x and y, are independent of one another. And the way to see that intuitively, is to realize that choosing r uniformly, from the set of four elements is basically the same as flipping a coin An unbiased coin twice. The first bit corresponds to the outcome of the first flip and the second bit corresponds to the outcome of the second flip And of course there are four possible outcomes. All four outcomes are equally likely which is why we get the uniform distributions over two bit strings Now our variables X and Y. Y the independents Basically if I tell you result of the first flip namely I tell you the lest signify bit of R So I tell you how the first coin you know whether it fell on its head or fell on its tails. That tells you nothing about the result of the second flip. Which is why intuitively, you might, you might expect these random variables to be independent of one another. But formally, we would have to prove that, for, all 01 pairs, the probability of, x=0 and y=0, x=1, y=1, and so on. These probabilities multiply. Let's just do it for one of these pairs. So let's look at the probability that x is = to zero, and y is = to zero. Well, you see that the probability that x is equal to zero and y is equal to zero is basically the probability that r is equal to zero, zero And what's the probability that r is equal to zero, zero? Well, by the uniform distribution, that's basically equal to one-fourth. What it's one over side of the set which is one fourth in this case And well low and behold that's in fact these probably provability multiply Because again the probability that X is equal to zero. The probability that lest signify bit of R is equal to zero. This provability is exactly one half because there is exactly two elements that have their, lest signify bit equals to zero. Two out of four elements gives you a provability of one half And similarly the probability that Y is equal to zero is also one half so in fact the provability multiplies. Okay, so that's, this concept of independence And the reason I wanted to show you that is because we're gonna look at an, an important property of XOR that we're gonna use again and again. So before we talk about XOR, let me just do a very quick review of what XOR is. So, of course, XOR of two bits means the addition of those bits, modular two. So just too kind of, make sure everybody's on the same page If we have two bits, so 0001, ten and eleven. Their XOR or the truth table of the XOR is basically just the addition modular two. As you can see, one+1 is= to two, modular two. That's=to zero. So this is the truth table for [inaudible] XOR And I'm always going to denote XOR by the circle with a + inside And then when I wanna apply XOR to bit strings, I apply the, addition modular two operation, bitwise. So, for example, the XOR of these two strings would be, 110, and I guess I'll let you fill out the rest of the XORs, just to make sure we're all on the same page. So of course is comes out to one, one zero one. Now, we're gonna be doing a lot of XORing in this class. In fact, there's a classical joke that the only think cryptographers know how to do is just XOR things together But I want to explain to you why we see XOR so frequently in cryptography. Basically, XOR has a very important property, and the property is the following. Suppose we have a random variable y. That's distributed arbitrarily over 01 to the n. So we know nothing about the distribution of y But now, suppose we have an independent random variable that happens to be uniformly distributed also over 01 to the n. So it's very important that x is uniform. N's independent of y. So now let's define the random variable which is the XOR of x and y. Then I claim that no matter what distribution y started with, this z is always going to be a uniform, random variable. So in other words if I take an arbitrarily malicious distribution and I XOR with independent uniform random variable what I end up with is a uniform random variable. Okay and this again is kind of a key property that makes x or very useful for crypto. So this is actually a very simple factor to prove, let's just go ahead and do it, let's just prove it for one bit so for n = one. Okay, so the way we'll do it is we'll basically write out the probability distributions for the various random variables. So let's see, for the random variable y. Well, the random variable can be either zero or one. And let's say that P0 is the probability that it's = to zero, and P1 is the probability that it's =to one. Okay, so that's one of our tables. Similarly, we're gonna have a table for the variable x. Well, the variable x is much easier. That's a uniform random variable. So the probability that it's=to zero is exactly one half The probability that's it's=to one is also exactly one half. Now, let's write out the probabilities for the join di stribution. In, in other words, let's see what the probability, is for the various, joint values of y and x. In other words, how likely is, it that y is zero, and x is zero. Y is zero, and x is one. Y is one and x is zero, and eleven. Well, so what we do is, basically, because we assume the variables are independent, all we have to do is multiply the probabilities. So The probability that y is equal to zero is p zero. Probability that x is equal to zero is one-half. So the proximity that, we get 00 as exactly p zero over two. Similarly for zero one we'll get p zero over two, for one zero we'll get p one over two And for 1-1, again, the probability that y is=to one, and x is=to one, Well, that's P1 the probability that x is=to one, which is a half, so it's P1 over two. Okay? So those are the four, probabilities for the various options for x and y. So now, let's analyze, what is the probability that z is equal to zero? Well, the probability that z is=to zero is basically the same as the probability that, let's write it this way, xy. Is=to 00. Or xy is=to, eleven. Those are the two possible cases that z is=to zero Because z is the XOR of x and y. Now, these events are disjoint, so, this expression can simply be written as the sum of the two expressions given above. So basically, it's the probability that xy is=to 00, plus the probability that xy, is=to eleven. So now we can simply look up these probabilities in our table. So the probability that xy is equal to 00 is simply p zero over two, and the probability that xy is equal to one, one is simply p one over two. So we get P0 over two +P1 over two But what do we kn-, what do we know about P0 and P1? Well, it's a probability distribution. Therefore, P0+P1 must =one And therefore, this fraction here must= to a half. P0+P1 is =to one. So therefore, the sum of these two terms must = a half And we're done. Basically, we proved that the probability that z is = to zero. Is one half, therefore the probability that z is equal to one is also one half. Therefore z is a unif orm random variable. So the simple theorem is the main reason why x o is so useful in cartography. The last thing I wanna show you about discreet probability is what's called the birthday paradox And I'm gonna do it really fast here Because we're gonna come back later on, and talk about this in more detail. So, the birthday paradox says the following suppose I choose n random variables in our universe u. Okay And it just so happens that these variables are independent of one another. They actually don't have to be uniform. All we need to assume is that they're distributed in the same way. The most important property though is that they're independent of one another. So the theorem says that if you choose roughly the square root of the size of u elements, we're kind of this one point two here, it doesn't really matter. But if you choose square root of the size of u elements, then basically there's a good chance that there are two elements that are the same. In other words, if you sample about square root a few times, then it's likely that two of your samples. [inaudible] will be equal to each other. And by the way, I should point out that this inverted e, just means exists. So there exists in [inaudible] I and j such that r I is equal to r j. So here's a concrete example. We'll actually see many, many times. Suppose our universe consist of all strings of length of one hundred and twenty eight bits. So the size of you is gigantic it's actually two to the hundred and twenty eight. It's a very, very large set But it so happens if you sample say around two the sixty four times from the set. This is about the square root of U then is very likely that two of your sample messages will actually be the same. So why is, this called the paradox? Well, traditionally it's described in terms of people's birthdays. So you would think that each of these samples would be someone's birthday And so the question is how many people need to get together so that there are two people that have the same birthday? So, just as a simple cal culation you can see there are 365 days in the year, so you would need about 1.2 times the square root of 365 people until the probability that two of them have the same birthday is more than a half. This if I'm not mistaken is about 24, which means that if 24 random people get together in a room it's very likely that two of them will actually have the same birthday. This is why it's called a paradox, because 24 supposedly is a smaller number than you would expect. Interestingly, people's birthdays are not actually uniform across all 365 days of the year. There's actually a bias towards December. >> But, I guess that's not, that's not relative to the discussion here. >> The last thing I wanted to do is just show you the birthday paradox a bit more concretely. So, suppose we have a universe of about a million samples, then you can see that when we sample roughly 1200 times, the probability that we get, we sample the same number, the same element twice is roughly half But the probability of sampling the same number twice actually converges very quickly to one. You can see that if we about 2200 items, then the probability that two of those items are the same, already is 90 percent and You know, 3000 then it's basically one. So this conversion is very quickly to one as soon as he goes beyond the square root of the size of the universe. So we're gonna come back and study the birthday paradox in more detail later on, but I just for now, wanted you to know what it is. So that's the end of this segment, and then in the next segment we'll start with our first example of encryption systems. [sound]
