Module 7 Vocab Flashcards
Probability Space (words)
7.1
- a set of outcomes
- a probability distribution function
Outcomes
7.1
A finite non-empty set Ω
Probability Distribution Function (words)
7.1
assigns probability to each outcome
such that the sum of all probabilities equals 1
Probability Distribution Function (symbols)
7.1
Pr: Ω→[0,1]
for each outcome w∈Ω
maps to its probability Pr[w]
such that w∈Ω Σ Pr[w] = 1
Ω
7.1
set of outcomes
Pr
7.1
probability distribution function
(Ω, Pr)
7.1
probability space
Probability Space (symbols)
7.1
(Ω, Pr)
Event
7.1
a subset of the probability space
E ⊆ Ω
Event (symbol)
7.1
Pr[E] = w∈Ω Σ Pr[w]
Probability of an outcome (symbol)
7.1
Pr[w]
real number between 0 and 1 inclusive
Uniform
7.2
a probability space where all the outcomes have the same probability
“equally likely”
Probability of each outcome in a uniform probability space
7.2
n = |Ω| (n represents the number of outcomes)
Pr[w] = 1/n
Probability of an event E in a uniform probability space
7.2
Pr[E] = m/n
where m=|E| (remember E is a subset)
and n=|Ω|
Pr[w] = 1/n
7.2
the probability of each outcome in a uniform probability space
Pr[E] = m/n
7.2
the probability of event E in a uniform probability space
Fair
7.3
uniform probability space
Biased
7.3
non-uniform probability space
outcomes are parameterized
Probability for biased coin
7.3
Pr[H] = p
Pr[T] = 1 - p
Bernoulli Trial
7.3
probability space with two outcomes
success = p and failure = q
parameterized such that q = 1 - p
Random Permutation
(of n distinct objects)
7.3
an element of the uniform probability space whose outcomes are all possible permutations
Probability of a random permutation
7.3
1 / n!
Probability that object i occurs in position j in a random permutation
7.3
(n-1)! / n!
1 / n
P0
7.4
Pr[E] ≥ 0
Since it’s the sum of non-negative numbers.
Pr[E] ≥ 0
7.4
P0
Pr[Ω] = 1
7.4
P1
P1
7.4
Pr[Ω] = 1
Since it adds up the probabilities of all the outcomes in the space.
P2
7.4
If A,B are disjoint then
Pr[A∪B] = Pr[A] + Pr[B]
Addition Rule
If A,B are disjoint then
Pr[A∪B] = Pr[A] + Pr[B]
7.4
P2
If A⊆B then Pr[A] ≤ Pr[B]
7.4
P3
P3
7.4
If A⊆B then Pr[A] ≤ Pr[B]
Monotonicity
Complement
7.4
if E ⊆ Ω is the event, then
the complement of E is the event Ē = Ω \ E
P4
7.4
Pr[Ē] = 1 - Pr[E]
Think: probability of not E
Pr[Ē] = 1 - Pr[E]
7.4
P4
P5
7.4
Pr[∅] = 0
A sum with no terms
Pr[∅] = 0
7.4
P5
Pr[A∪B] = Pr[A] + Pr[B] - Pr[A∩B]
7.4
P6
P6
7.4
Pr[A∪B] = Pr[A] + Pr[B] - Pr[A∩B]
Inclusion-exclusion for two events
P7
7.4
Pr[A∪B] ≤ Pr[A] + Pr[B]
Union bound. Follows directly from P6.
Pr[A∪B] ≤ Pr[A] + Pr[B]
7.4
P7
