LIVE_An Introduction to Probability in Computing – Session 1



so as the session started nominal good so welcome everybody this time I'm going to be taking the live session from my so hopefully that should be no technical glitches so let's get started so again my interest is to basically address the questions that you have maybe you know some general topics so let's let's go one by one so there are some questions that they put least and even last weeks and I am trying to I try to address them as best I could in last week's situation so I thought this bore it again a little bit maybe bit more carefully and then few other questions raised so let's get started if you are able to ask a favor of you if you if everything is clear if you are able to view this just go to the chat the live session chat and just by saying everything I am able to follow what is going on that even give us some feedback to let us know that you know this live session is going on and if there is any issue it's not reaching you you're not able to access it then some things is there's a glitch then let us know so we will try to see what can be done the situation okay so now let me share my speed so that we can start working with it the folks let me just test it out yeah that works perfectly good so first things first so last week there was a question on linearity of expectation and the question was can we have some intuition for the linearity of expectation and without a device to write on and show it was a little bit difficult but let me so though I thought we'd start by addressing this issue so one nice thing I did was that I found at least is that there was an alternative proof of the linearity of expectation that may just be a little bit more intuitive so this by the way I've taken it from the source here it's it's taken from open courseware from MIT if so you have two random variables R 1 R 2 and the linearity of expectation is just to show that the expectation of R 1 plus R 2 is the sum of their individual expectations so this is classically linearity of expectation and the question was why not just I think the person who asked the question I'm just go through the lines of the but in some sense we wanted to know why that is this is even false and what is the intuition behind this linearity of expectation so let's actually look at what is going on essentially what is going on is that the so let's notice one one thing about this proof here you're creating this new random variable T that's the sum of the start Hey so now you can think of the expectation of R 1 plus R 2 which is which was the left-hand side of what we want to say like the equation that you might have true and so now interpreting what you're doing is you're combining our motto and look in this look at it as a single random variable so now it's become the expectation of this animatable now it is the random variable T then each value that he can take so that's all these values s that he can take has probability associated so you apply the formula or expectation in and so now you get the sum over all the individual values that a and times the probability of those values and so you apply that and now each so suppose he takes the value s s is really coming from two sources it's it's there is an Associated yes the two added together was what led to this value s so think of it as R 1 of s r 2 s and so so this so that's what they're doing the separating it out yet so P the inclusion here is the following so this problem would not be associated with that value s no can can be taken into each one of these can be associated with each one of these random variables R 1 and R so this is this is really the crux of why you can even apply I mean why any of expectations true regardless of what dependencies exist between r1 and r2 the probabilities associated with it can be somewhat separated up so what what happens now is this one big summation because the probability can be taken in can we separate it into two summations so there is that one summation here and there is this other summation here and you might be asking so what is the intuition here at all if there are some dependencies between these two random variables r1 and r2 why does it not matter and so the best way to think about it is take an example and try to work it out for yourself we do that in just further the key thing to keep in mind is the probability spreads into both r1 and r2 so in some sense it's applied to r1 and r2 separately and then each of these boxes that I've drawn is essentially the formula for expectation of r1 and expectation of r2 and then you get the linearity of expectation so this is this is the formula let's look at an example so let's take the case where r1 is equal to let's say plus 1 with probability equal to minus 1 minus 1 with probability a and now I'm gonna see a random variable R to be completely independent enough in I'm going to say that r2 is minus 1 whenever r1 equal to plus and plus one whenever r1 equal to minus one okay so this what does this mean r1 plus r2 will always be equal to 0 so R 1 is what art is going to be minus so this still completely dependent on each other right so now it's it's easy to see right so let's let's look at the expectation of r1 plus r2 well this r1 plus r2 is never going to be any value other than 0 so that's equal to 0 and similarly the expectation of R 1 is equal to also so that's coming straight from the fact that it's plus 1/2 minus 1/2 now are those completely dependent on mine but still this is the probability of R 1 equal to plus 1 is 1/2 and I want equal to minus 1 is 1/2 so expectation of R 2 equals so you see this course now let's flip things so let me cut small modification just to see know what happens what I'm going to do remember this are not to where what is going to negatively correlated ornament but when one of them is one the other one becomes a minus so they kind of cancel each other what happens when they do when they know they're positively correlated so let's make this so it's minus 1 when R 1 is minus who would need to make this a plus 1 and this – so basically yeah so we just correct that yeah so now they're both going to take on the same night so when R 1 is plus then our to velocity plus when R 1 is minus 1 then our to also be minus me hey so they are now positively correlated now again you can see that R 1 plus R 2 is in this case is going to be let's try it's always going to be plus 2 or minus and again both the plus 2 and the minus 2 will happen with equal like a good so again you have expectation of R 1 plus R 2 is 0 and these expectations the individual expectations don't change because the probabilities of plus 1 and minus 1 don't change so you hopefully this example effect you sort of see that as long as the individual probabilities are whatever they are however whichever way they are coordinated with each other whether the two random variables are positively correlated negatively correlated or not completely independent so you can also think of R 2 has been a completely different random variable with bus or minus 1 with equal probability then also this whole thing will really cool right and it goes back to the you know the fact that the probabilities the probability of each combination kind of can be taken into this expression and so then it leads to these individual random variables I think in summation acting by ourselves in summation so they are they could be dependent if you so for example if I know that R 1 X plus 1 I may know that R 2 X minus 1 but when you look at these boxes that are these red boxes that I've drawn they are not based on individual values that one not the other takes the summation over all possibilities and so the dependencies if so that's a long unfortunate bit of a long answer to a short question so but I hope that gives some intuition so let me pause now and check with my dear to see whether there is any questions other people what's the at least are there people logged in ok so there are people often so now let me take this moment to pause and remind you that if you have any specific questions you have to type in the questions in the chat window so that my ta but in help out with leading of the question to me and then I will be able to hopefully address ok so now the next question that asked was the principle of effort so one of the questions was what is the mathematical basis for the principle of different decisions essentially it is it goes goes back to the law of total probability so let's let's look at the law of total probability in this context what we do is we take the universe we have a good push and we we partition the universe into destroying events a 1 e 2 and so 3 a 4 5 a 6 and now this is some partition and that we are interested in some other even let's say E and the B takes something like this it is a chain so what we are interested in is the probability of but the probability of B could be complicated except every condition on a particular VI so let's say we are able to somehow get this probability is it meaning we are able to get the probability of e conditioned on eat and we're also able to get that not only for eaters we are also able to get that for probability of B conditioned on 1 and so on of the probability of B conditioned on B say so somehow we have all of these probabilities if we're able to if you think about it it often happens that when you condition on some e to that means you've broken down the problem and focused on a very limited setting with whom e 2 has occurred so that's the intuition here so if you put these probabilities and you also have the individual probabilities of these events probabilities in events then you are able to compute probability of B because that's just equal to this Plus this plus and so on you just add up all the English probabilities but then you will get the probability of e what has happened so let us look at one specific boss you have no one specific term here so that's this term that is nothing but probability of B given e2 in just a second so so now there are these individual terms here right so now let's look at this one box here so that essentially captures this part of the probability so each of these summation so for example the very first one will actually be 0 because there is no intersection between a 180 so that will be 0 in this particular case but each term basically captures its own portion of so I think the probability itself is fairly clear but I just want to remind you of them because now it's cool with this reminder of the law of let's go back to the principle of deferred decisions so what happens now is that there are several variables several let's say let's let's acting create an example a simple example let's suppose that we have some end point offices and we want to argue that the probability that the number of odd means of the number of heads is e is is odd so let's assume that in so we want to be able to prove this you want to argue that that not probability that the number of heads is art is exactly 1/2 so we don't know anything let's say for example n equal to 3 then you can have a this object right T DT DT a hdhd eh-eh and so you want to argue that the number of so one thing you can do is you can you can you can work through all the 2 power n options right there are could be other ways to do it but let's try to use the principle of therefore decisions so here what are we doing we have n variables and in events basing the outcomes of n pine process some of them were going to artificially set and then focus on somehow and specifically in this context what we're going to do is let's say that C 1 C 2 and so on up to see at the end point of system at the end find cox's so what we're going to do is we are going to assume that these first n minus 1 coin tosses for all the knees down and then we going to focus our attention on scene now how does this relate to the the the law of total probability so what are we doing when we set C 1 and through C n minus 1 what we do is we are taking the universe and we are breaking it into or partitioning to be partitioning into two ways to the n minus 1 thoughts so let's look at one such part what is that one such part I'm going to look like it is going to be the assignment of value C 1 to C n minus 1 as some specific sequence so so let it could be specifically say HD p88 blah blah blah something this is the this is n minus 1 outcomes kind of outcomes so so now if you consider all such possible n minus 1 outcomes you're basically partition the universe into to the N minus 1 plus B now what we need to so essentially what I'm gonna do is just gonna draw all such parts I'm not going to draw it like it's a partition you have to assume that it's a partition and that's I'm just for simplicity I'm gonna draw it or some sort of a thing like now what I'm going to do is draw another event which is the probability that the number of heads is so now let's focus on this I was the the claim is that this shaded portion is going to be why is that the case and that's easy to see because what we have done is when we are focusing on disability this we have specified the first n minus 1 outcomes we have specified the first n minus 1 outcomes and but but whether the final number of heads is even our God is therefore dependent only on this last point does this is the one that we have defer the rest we have fixed so when we are focusing on this one outcome we have fixed the first n minus 1 and the very last one we have not focused on but that is the one deciding event that decides whether the final number of hits is or dirty so let's now think about so let me isolate that portion so basically what we've done this is that say this particular event so let me call that some e I I'm going to draw that right so what is the problem what is that what is the probability given given right what is the probability that it's going to be or I mean the total of its will be correlated well that will depend on two things what is the number of heads in first n minus 1 tosses and then the second thing is we depend on is the what is is the last toss it's so these are the two things that we matter but because I have fixed e di this is already fixed this is already fixed we don't the number of remember we have we have fixed this portion this is the portion that is already fixed so we have already that it means that we're conditioning on this di so this this portion is already fixed okay but regardless of what that is the this portion is the last thoughts heads or tails is going to be it's going to all with probability ah but regardless of the previous number of so let's let's take an example so let's say that the CI here the number of heads was 52 then the last point us is what is going to dictate what is going to happen because now with probability 1/2 the last fine class is going to be heads in which case the total number of dogs will be 53 and therefore the it's going to be odd the number of number of heads or it's going to be a tails with probability half in which easily remain 50 and you can work it out regardless of what this was it the final outcome of odds hard versus even is going to be a half based on whether the last coin toss was a it's or a fix going back to this picture what is the intuition here so because we when we when we fix these essentially what we're doing is we're fixing on one of these partition the right this this protecting the universe and which is partitioning it into little pieces and then we're focusing on that one piece because we are conditioning on this allows us to forget about this so and then focus on whatever is happening and so this is even though it you will see that X that X is the random variable denoting the number of process required to attend to get a bit unique I would like to can be mathematically prove that probability of X is equal to I plus K here is greater than this probability of X ok so we get this be given this information what is the expected number of society before see before a seat open certificates any generalizes to n consecutive hits is this X which measures the okay I think a little bit about this Fe so let me let me see let me start with the simplest form of the question until the simplest form of the question is let's you have a point and let's even start the people to 1/2 and the question is and you also have a K value a to begin with in so the question is I want to define a random variable X to be the number of tosses on a in this case okay and we want to understand the expectation of okay so so yeah let's try to think about the buttock you had an idea that may be something that will work so the people about this for a second so now they what does it mean for X equal to well X cannot be one exclude to be two or more it's unjust thinking out loud here three and so on so which means that the outcomes are let's see taken significance so now okay so what your love is multiple tails tails heads tails and so on but when you have two heads that's when you stop in so I think we need I think we really need to formulate our answer before we can do that so my apologies but I don't think that I'll be able to give a very quick answer because I have not thought about the specific question and would be better if I the tea and I had a chance to discuss we also have a chance to figure out how exactly to communicate the answer so it might be better if we effort this question either a little bit later today itself it's already about 540 so possibly not today but certainly one thing we can do is we can send out an email or an announcement but I don't think we should try to answer it at this point in time what I do is I try to instead answer the questions other questions that came up there was one more specific question assignment assignment for question yeah so assignment for one of the questions that was asked was problem number yeah so problem number 5 in assignment I think that would be something like answer the time frame now so here we are given a point of the bias 1/3 + X I equal to 1 if the ayat' the flip of that point is it's 0 adults and of course we tossed this end-time so capital X is the total number of X so that's given by summation I and which implies that the expectation of X is equal to using linearity of expectation it's the sum of individual expectations and that's nothing but and I think this part is easy now what question is asked in just one thing keep in mind is this n the number of flips coin flips is equal to n1 and this is an unknown in fact this is what we want and we thought we want to ensure so let's let me read the question is that part of the question we wanted to find the determine the smallest value of n so that the probability that at least half the coin flips come out it is less than 0 point 0 0 so in other words you expect to see n over 3 heads if n is small so let's say for example Enis let's take an example n equal to 3 okay in which case you would expect to see 1/3 of the time pips to come up heads but now what is the probability of getting two heads out of those three-point causes well that's going to be n choose n choose 2 so basically you you choose two of them tie one thirds for for those two coin flips and then 2/3 you can have the tails so if you work this out so here and this is in this 3 but if you it works out to something like if I'm in my math that's not a big leeway off it's going to be something like 1 by 3 raised to the 4 times 2 and sorry so this is not this was going to be 3 times 1 by 3 square times 2 so that's going to be 2 over 9 so this is this is significant probability okay so when n equal to 3 obviously this is not working so what we want is the probability of having more than n over 2 number of heads we want that probability to be less than 0.001 and we can achieve this by increasing the number of mind process we by suitably increase in the number of coin tosses and bad if you look at all the exam I mean answers if it is 198 249 307 349 so these we basically want to show that fine you know give the number such that you know if you toss back many times this the number of heads exceeding n over 2 we now become very very small say 0.0 something less than zero point zero in this question we are also specifying what approach you take in order to solve this problem and we particularly want you to apply turn off that specific general form that is given there so for that journal point we already have we require a few things be higher than mu so will require mu is n over 3 we will also require Delta and if if we have these two then we'll be able to compute the appropriate value and so let's see how that works out Hey so now what we want to ask is the probability that X is what probably that X is greater than n over 2 this probability we want that to be less than or equal to zero point zero right strictly less than 0.001 so let's focus on on this probability that X is greater than n over 2 and we we want that to be written now we want to apply a check upon so we want that to be written in the point X is greater than or equal to 1 plus Delta x and that the times mu nu is n over 3 so I'm just going to write that as n over 2 hey so this means that I need to compute the profit value of Delta so and then we knew that on the side here one plus delta x in over three should be in over two so solving that basically i think 1 plus Delta will be which implies that Delta equal to 1 so now we even have the value so this probability so that's equal to 1 plus 1/2 which we know by applying this formula is e to the minus mu is n over 3 Delta is 1/2 so 1/2 squared is 1/4 times 1 over and we want the whole thing to be less than and remember this is we want the swapping to be less than zero point ok and that's zero point zero zero a and that's now now we just have this inequality and we just have to solve for and and this part I think you can possibly do it so now that we take the long well maybe first we should do is remove the negation from the top so it becomes e to the N 30 it's 36 yeah 36 is greater than 1,000 and now I can take the log on both sides so it's going to be and by the pitch six is greater than 1,000 and so the 36 can go here so what we want is the smallest value and such that this inequality close and that you can just punch it into a calculator and we come out to something like two forty eight point something something so the integer value that will that will satisfy this condition is to ignite which is the answer so that addresses all the specific questions that people had raised in the in the in the Google right she so in the know might be a good time so it's about ten minutes to to the closing time today so I don't know if we have time to answer any more technical issues but maybe I should address the final exam so the final exam is going to be out of fifteen mom's so this will be from the questions and the pattern is going to be basically a lot of multiple selections and one thing to keep in mind a lot of the problems we have multiple correct choices so what does that mean so if we if there are four choices it's not a you know you might have been used to multiple choice questions in which case exactly one number for questions is but what we have as much to the selection questions meaning you need it might well be the an example of this is which of the following let me try to think of an example an example might be virtual following statements are true and one of the statements would be given two random variables the expectation of there's some expectation of some of those two random variables is the sum of their individual and the second in the option let's say is something like what is the variance of variance of two random variables maybe some of the random variables is always equal to the sum of their individual variances and maybe the third one could be another statements also the first one let's say first one was essentially if you just show you the ricotta was the linearity of expectation XI the second one the claim was the variance of X 1 plus X 2 equal to variance of X 1 plus the variance of X 2 and let's say the third one was something like let me let me just just to illustrate the point the the probability of heads heads heads in 3-point doses is we look at the unbiased point process is 1 over 8 and then the fourth one is the probability of heads tails tails heads in for coin tosses is 1 so I think these are the four selections available obviously this is true this is true this is not true and here because I have not specified that X 1 and X 2 are independent this one also is not true so it's you notice that there can be multiple correct answers and so all of the correct answers will have to be chosen since I just want to emphasize that you have to read through all the choices and then make your selection so this sum of the assignment questions this picture but not all of them in the sand we have more so you need to be watchful for the second thing I want to point out is that there will be reaction questions so there will be portions of the textbook either our textbook or some other textbook where like so again you'll be asked question is based on that portion of the picture so you have to comprehend it and sometimes the questions will be slightly spraying from there not only the questions but just to understand the questions of that so so the 20% of the questions maybe even more maybe like 30 percent of the questions will be straight from the assignments but you will need to still read and carefully understand the question there might be some very minor changes so that's that's why I have to say for the final exam so let me it's all going to be selecting but mind that it's not just gotta cancel the female select you may have to select all the correct answers so that's there any other questions okay so there is okay so what we do in the next few weeks sample final exam we will still be monitoring the discards over I think but the PA part will be monitoring that and also if you have any specific questions you can also yeah so basically the probably be the right place to raise any questions with you if you feel that there is some topic that I need to teach again I'm and you raised up in Maine and a few more life sessions but you will have to tell me in advance what topic you want me to cover okay so I will come prepared for those topics alone and I try to address those questions so take advantage of that you ask your questions any doubts just make sure you erase it and then we will try to address it and so there is a one pending question that we require a bit of time for me to formulate the answer and posted so I will probably post it Alaska Senator Barbara propose that we you should be able to anything any final questions concerns issues before we wind up so thank you very much for all those who patiently listened through this session let me three I think now yeah so thank you very much I appreciate your patience and with this I'll stop the broadcast for today and any questions just raise it up in the Dysport and if you want to tell me send email I mean posted in this part requesting for that we will find out comedy thank you

One Comment

  1. Chandan Hegde said:

    One of the best Professor.

    June 30, 2019
    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *