Unit 4-Lecture 1：Intro to Discrete Probability

1 The Four Step Method to Solve Problems like “What is the probability that… ?”

Step 1: Find the Sample Space:

Every possible combination of these randomly-determined quantities is called an outcome.The set of all possible outcomes is called the sample space for the experiment.A tree diagram is a graphical tool that can help us work through the four step approach when the number of outcomes is not too large or the problem is nicely structured.The leaves of the tree represent outcomes of the experiment, and the set of all leaves represents the sample space.

Step 2: Define Events of Interest A set of outcomes is called an event. Step 3: Determine Outcome Probabilities

Step 3a: Assign Edge ProbabilitiesStep 3b: Compute Outcome Probabilities Specifying the probability of each outcome amounts to defining a function that maps each outcome to a probability.

Step 4: Compute Event Probabilities

2 The Strange Die

There are arbitrarily large sets of dice which will beat each other in any desired pattern according to how many times the dice are rolled.

3 The Birthday Principle

If there are d days in a year and 2d−−√ people in a room, then the probability that two share a birthday is about 1−1/e=0.632

4 Set Theory and Probability

A countable sample space S is a nonempty countable set.An element ω∈S is called an outcome.A subset of S is called an event.A probability function on a sample space S is a total function. Pr S→R such that: Pr[ω]≥0for allω∈S and ∑ω∈SPr[ω]=1

Probability Rules from Set Theory:

Sum Rule: Pr[⋃n∈NEn]=∑n∈NPr[En] Union Rule: Pr[E1∪E2...∪En∪...]≤Pr[E1]+...+Pr[En]+...

Uniform Probability Spaces: A finite probability space, S, is said to be uniform if P[ω] is the same for every outcome ω∈S .

---

Reference

[1] Lehman E, Leighton F H, Meyer A R. Mathematics for Computer Science[J]. 2015.