Slide 1ToolsTools: setsSigma-algebraprobabilityProbability: key takeawayscombinatoricspermutationspermutationscombinationscombinationsConditional probabilityBayes RuleRandom variablePMF/cDfJoint distributionsJoint distributionsExpectationExpectationExpectationvarianceVariance, standard deviationCovariance, correlationCovariance, correlationchebyshevDistributions: bernoulliDistributions: BinomialDistributions: GeometricDistributions: geometricDistributions: negative binomialDistributions: poissonDistributions: poissonDistributions: summaryProbability densityProbability densityProbability densityProbability densityDistributions: uniformDistributions: exponentialDistributions: exponentialDistributions: GammaDistributions: GammaDistributions: GammaDistributions: Gamma-PoissonDistributions: Gamma-PoissonDistributions: normalCentral limit theoremCentral limit theoremPopulation and samplePopulation and samplePROBABILITY AND STATISTICS IN COMPUTER SCIENCE AND SOFTWARE ENGINEERING Mid-Term Review1TOOLSA collection of elementary results, or outcomes, is called a sample space.In the previous example (coin flip), the sample space consisted of two outcomes: a heads or a tails. Any set of outcomes is called an event. An event is a subset of the sample spaceExample: Roll a dice. There are 6 possible outcomes (denoted by the numbers on the face of the dice)Events could be roll an even number, roll and odd number, roll a number less than 5, etc …2TOOLS: SETSCommon notation: = sample space = empty event (no outcomes included) = probability of event E occurring Consider a game between the Cowboys and the Giants … = {Cowboys win, Giants win, they tie}There are actually eight events associated with this sample space …Cowboys win, lose, tie, get at least a tie, get at most a tie, get some result, get no result•:3SIGMA-ALGEBRAWe will give a rigorous definition of probability and then look at some propertiesFirst, a definition: A sigma-algebra (denoted ) on a sample space is a collection of events such that(a) (the entire sample space is included in the collection)(b) (if an event is included, then so is its complement)(c) (if a finite or countable collection of events is included, then so is its union)Note that a sigma-algebra is just a collection of subsets with these three unique properties•:4PROBABILITYAssume a sample space with a sigma-algebra defined on it. Probability is a function such that:(a) (this is possible, since )(b) For any collection of mutually exclusive events , We can immediately conclude that There are a number of properties that can be deduced from this definition … we’ll look at pages 15-17 to see these•:5PROBABILITY: KEY TAKEAWAYS and : There will always be some outcome of the experiment.If an event is composed of mutually exclusive outcomes, then the probability of the event is the sum of the probabilities of the outcomes that make it upFor any event E, we have . In other words, the outcome will either be the event or its complement (heads or tails)Events are independent if the probability of their intersection is the product of their probabilitiesBe careful when computing the probability of the union of events – it is the sum of the probabilities only if the events are mutually exclusive•:6COMBINATORICSFor discrete sets of objects, we create events by sampling (i.e. selecting objects)Sampling with replacement means that every sampled object is replaced into the initial set; if there are n objects, the probability of selecting any one of them is 1/n.Sampling without replacement means every sampled item is excluded from further sampling – note this impacts the probabilities of the next selectionObjects are distinguishable if the order they are sampled in yields a different outcome or event; they are indistinguishable if the order is not important. Note this applies to the sample order, not the objects themselves7PERMUTATIONSPossible selections of k distinguishable objects is called a permutation.Note: Order matters in permutationsIf there are n possible objects(objects in the initial set), the number of possible selections of size k from this set with replacement is given byThis is because there are n possibilities for each selection, and there are k selectionsFrom a set consisting of upper and lower case letters and 10 digits, there are trillion passwords for size 8 that can be constructed•:8PERMUTATIONSIf there are n possible objects(objects in the initial set), the number of possible selections of size k from this set without replacement is given byThis is because with each selection, we reduce the “pool” by one objectNote that if , we have the classic formula for number of permutations: •:9COMBINATIONSWhen order is no longer important, the number of combinations uses a different formula …If we are choosing k objects from a set of n without replacement and the order is not important, the number of ways we can do this isThis is sometime called “n choose k”It is the same formula as the permutation without replacement, but we divide by k! (which is the equivalent of factoring out by the number of orderings)•:10COMBINATIONSFinally, we have the formula for the number of combinations possible when replacement is allowedThis formula is given by•:11CONDITIONAL PROBABILITYThe conditional probability of an event A given event B is the probability that A occurs when B is known to occur.The notation is .If we think in terms of sets, we know that It then makes sense to define the conditional probability as on the next slide …•:12BAYES RULEFinding may not be easy Notice that …If we use the formula on the previous slide, we can compute(Bayes Rule) In general, , but they are related by Bayes Rule•:13RANDOM VARIABLEA random variable is a function of an outcome, . It is a quantity that depends on chance. The domain of the function is the sample space We will assume that the range is a subset of the real numbers (could be integers, or an interval, etc.)Once an experiment is completed, and the outcome is known, the value of the random variable is determinedExample: Flip a coin three times, count the number of heads The outcome is the result of flipping the coin three timesThe random variable is the number of heads Note that for each experiment (3 coin flips), we will get a value for X•:14PMF/CDFIf we look at the collection of probabilities related to X, we have the distribution of X. The function defined by is called the
View Full Document
Unlocking...