Lecture 01 : Introductory examples

[Music] [Music] welcome to this course on probability for computer science so this is an eight weeks long course only which we call in iit modular course ok so instead of 12 weeks this will be for 8 weeks and this is compulsory for ca students so students especially our students who have given je they have already learnt probability and how to apply it in fairly complex problems so you already know some of the concepts so why do you do this course again well because this will consolidate those concepts and this will give you far more examples to think about and to remember and then to apply so the course will consolidate those concepts and give many examples so these examples will obviously require understanding of math but they will not be purely mathematical they will be inspired from real life situations that appear in computer science problems inspired from also it is a compulsory course because it is useful in it is in fact required for more advanced courses future courses like machine learning randomized algorithms of course so randomized algorithms obviously they use probability both to run the algorithm and then to analyze its complexity and success or failure how good is it and randomized methods in complexity ok so whether you are interested in theory or in practice in both kind of courses probability will be omnipresent i would start by thanking the previous instructors who have taught this course so professor surinder baswana and professor rajet mittal so much of the material will be based on the standard syllabus of this course ok so just to start off what is probability or what is chance so probability or what we simply call chance of an event is so for now we will not define it very properly what is an event what is a probability but you since you already have some idea so let us just continue with this intuitive notation so probability of an event e which is p of e is essentially number of favorable possibilities divided by all possibilities right so it is the ratio of favorable over all so if you see this as a diagram venn diagram to be proper then it's just so there is this universe or the whole sample space which we call omega and in this there are these favorable possibilities which is the event inside the circle okay so you are interested in this so how big is this space in comparison to the whole sample space omega okay so this ratio is is probability so if things were if your experiment was completely random there was no bias whatsoever then whatever this venn diagram says mathematically is what you will expect intuitively to happen in practice right so theory and practice will meet if everything was ideal then this probability is correct which is size of u over size of omega so it is event over the sample space right which in numbers is size of e over size of omega like this is what you know from your school days so there is nothing new in this no surprises so lets start with the some examples which will become more and more interesting as we proceed ok so what is the most basic example in fact the example which must have started probability which comes from gambling you go to a casino and you play a game which is a game of chance so somebody flips a coin and based on what appears in the coin either you win or you lose right so that is really the starting point of probability itself historically so it starts with a fair coin so a fair coin when tossed gives heads or tails with equal probability right which means that since there are only two possibilities and say you want heads so if you want the probability of heads in the experiment where you have flipped a coin single coin fair coin which is also called unbiased coin so that will be e over omega which is one over two right so this you can also write as fifty percent chance right but we'll always use fractions so we will call this half or 0.5 probability but sometimes we just multiply it by 100 and we call it 50 right so this is coming from equal probability that's the definition of unbiased what you remember already is that probability is at most one because it is a ratio of favorable overall right so it cannot be more than 1 and it is always non negative it cannot be negative because you are actually counting so that's the first property and second property from the again look at this diagram venn diagram from this you can see that e and its complement fill the whole space which we write as probability of e and probability of e complement that sums up to one right which is essentially saying that one of the two things will happen in an experiment exactly one of the two happen that is the way you can interpret physically this equation right so these two things are both intuitive and easy to show by whatever definition you use of probability let us make it slightly more interesting and let me say that a dice has six sides for me so numbered one to six so roll two dices to get numbers x and y okay now what is the probability that these two numbers are co prime right co prime means they do not share a factor other than one so for example 1 and 2 are co-prime but 2 and 4 are not co-prime because 2 and 4 share 2. so you get 2 numbers between 1 to 6 what is the chance that they are co-prime so how do you solve this right given your basic understanding you count you count all the possibilities so probability that x y co prime so you look at the case let us divide this into x equal to one x equal to two x equal to three x equal to four x equal to five and x equal to six right so there are six values x can take and then we'll later on count how many y's are possible okay that will give us the favorable possibilities or favorable outcomes what are the total outcomes so total is x up to 6 y up to 6 so it's 6 times 6. so now if x is 1 then y can take any value right so there are 6 values if x is 2 then y can take 3 values then if x is 3 it's only 3 and 6 which are bad everything else y can take so it's 4 possibilities for y ah if x is 4 it is like 2 which is again so y cannot be 2 4 6 right so its 3 possibilities like before and if x is 5 y can be anything and finally if x is 6 then y can be only 1 or 5 so that's 2. so this divided by 6 times 6 which is what so that gives you 24 6 times 6 which gives you two thirds right which is around 67 percent so when you roll to a two dices the chance is actually very high that the numbers will be co prime okay that which is something you would not have guessed immediately you get that only after doing this rigorous calculation so you can see that probability in these examples is just counting right you have to count carefully and then you get a sense of how probable the event is so let me ask a question here in this calculation so in this calculation did we assume the two dices to be distinguishable or indistinguishable ok what do you think when we wrote the favorable possibilities what did we assume about the dices are these two dices the same or are they different okay so think about that ah accordingly so in one case you will get one answer in the other case you will get a different answer work this out as a homework exercise now building on this we can ask the question becomes our third example ah that suppose from this infinite expanse of numbers we pick two numbers at random what is the chance that they are co prime so suppose you pick random numbers a and b ah they are positive integers so 1 2 3 dot dot that is what this n denotes what is the chance that they are co prime so what is the probability that the gcd of a b is equal to 1 right so this is a question similar to what you just saw but difference is that their a and b are between 1 and 6. so you picked something out of the 36 possibilities and you did the explicit calculation but what will you do here here now it's not just six possibilities it's infinitely many possibilities right so does it make sense to even talk about probability uh which forces you to formalize probability in a more general way right so it is not somehow at this point the intuition breaks down and math then has to take over so this is tricky because of the infinite space right so if you look if you just do one over infinity that will be zero right then everything every event seems to be probability zero so can we make a more refined definition of probability than just ratios so this means that more formalism is more careful formalism is needed which you may not have done in your high school ok so that is where this course will depart from your earlier knowledge so we have to be careful in defining p the value of probability an element or subset so think of every event as a subset of some space but when that space is infinite then you have to be more careful about how to define p so here is a here is a paradox we will see some problems that happen with infinity so that becomes our example 4. so let us draw a picture first so that is a circle centered at o it states a unit circle ah equilateral triangle abc right so if you look at the radius since this is one and since the radius is one ah the angles are 60 degree so you can use sine and you can reduce that this this distance a b from the center o will be half ok and you can also deduce what is the length of a b all that is pretty standard so what is the question the question is that given this picture if you draw a random chord right so let me draw it that is a random chord two end points d n e what is the chance that this chord has length more than a b okay what is the chance that this random chord is longer than the edge of the equilateral triangle okay this is what you have to calculate now the number of possibilities here is mind boggling because it is we are really talking about the real picture so infinitely many d's infinitely many e's infinitely many lengths right so the traditional definition of ratio will just give you something over infinity right all possibilities infinity so this is like always zero you would think but we can still make sense of this as follows we will actually compute probabilities now of this event an equilateral triangle abc in a unit circle centered at o draw a random chord we called it d e so what is [Music] the probability that the length of the random chord is more than the length of a b let us say at least okay what is this probability does it make sense first of all to ask for this probability and then second how will we calculate this thing where the possibilities are endless literally infinite we will make sense of it not in one way but actually three ways ok you will see it now so let me define process one process means how are you selecting randomly the chord right there are many ways ah so you can pick d n e in a random fashion let us do that now ah since this is a symmetric picture and you are selecting two random points so without loss of generality you can assume that dna are the same and then you only have to select e randomly ok so with this picture in mind what are the goodies right the good e's are the ones which are in so for example if you take e in the a b arc then the chord will be smaller than the the edge and the symmetrically a c arc will be bad so the only good arc is b c right so these are all good favorable possibilities so let us write that down so pick d e randomly and to work this probability out it should not matter if we fix d right because the picture is symmetric so without loss of generality d we can take to be a then favorable e fall on the bc arc so then you just have to compare the circumference right which means that the probability of d being at least a b this is equal to the circumference of bc over the circle which is clearly one-third so we have a we have a probability right in if you do if you follow this process of picking dne randomly then without going into the formalism of probability it seems that one third is the correct answer because selecting bc arc should correspond to its length right and length is not infinite length is just you can get it by two pi formula right so length is just two pi by three so from that you you get this finite number but this is not where the story ends so you could have chosen the chord in a different way so for example what you could have done pick the midpoint of d note that if you pick the midpoint of d ah then you all then it specifies d and e uniquely it specifies the chord right because the end points are defined by the intersection with the circle so picking the midpoint of chord is also a valid selection process so then what happens what are the favorable possibilities from that point of view in this case i leave it as an exercise that this inscribed circle so what is the radius of this circle so the radius is half so the inscribed circle is radius half circumscribed is one so if you pick a point here for example this point so then you draw the chord that's your d okay so uh and let's call this point f so by first picking a random point f and then picking that chord whose midpoint f is the chord will be longer than a b if and only if f falls in this inscribed circle the favorable f fall in the inscribed circle okay so this you can prove geometrically it's a simple exercise to do i will not do it rigorously here but it looks believable if you look at the picture then f which is outside the inscribed circle those chords will be smaller okay and if inside the inscribed circle since it is closer to the center o the chords will be longer okay that's basically the visual insight visual proof and by that so inscribed circle whose radius is half right this half came from sine 30 degrees so which means that the probability that the cord is at least the the edge a b this comes out to be the areas of the circus right so f favorable is in the area pi r square and total area is pi which gives you one by four right so now you are getting a this gives you a different probability right this is this now comes out to be smaller than before although each of these processes they seem valid they seem a good way to pick a random chord but then the way you are picking it you are getting different probabilities and even this is not the end we could do it in a third way which is pick the distance of d e from the origin so randomly pick the distance which will be o f so that means you will this distance of o from f ok this is what you are picking in a random way so not the point f but the distance okay which is which is o f so it seems that its the same as picking f but you will see that probability will come out to be different [Music] do [Music] [Music] you