Module 7 Vocab

Question 1

Probability Space (words)

7.1

Answer 1

1. a set of outcomes
2. a probability distribution function

Question 2

Outcomes

7.1

Answer 2

A finite non-empty set Ω

Question 3

Probability Distribution Function (words)

7.1

Answer 3

assigns probability to each outcome
such that the sum of all probabilities equals 1

Question 4

Probability Distribution Function (symbols)

7.1

Answer 4

Pr: Ω→[0,1]
for each outcome w∈Ω
maps to its probability Pr[w]
such that w∈Ω Σ Pr[w] = 1

Question 5

Ω

7.1

Answer 5

set of outcomes

Question 6

Pr

7.1

Answer 6

probability distribution function

Question 7

(Ω, Pr)

7.1

Answer 7

probability space

Question 8

Probability Space (symbols)

7.1

Answer 8

(Ω, Pr)

Question 9

Event

7.1

Answer 9

a subset of the probability space
E ⊆ Ω

Question 10

Event (symbol)

7.1

Answer 10

Pr[E] = w∈Ω Σ Pr[w]

Question 11

Probability of an outcome (symbol)

7.1

Answer 11

Pr[w]
real number between 0 and 1 inclusive

Question 12

Uniform

7.2

Answer 12

a probability space where all the outcomes have the same probability
“equally likely”

Question 13

Probability of each outcome in a uniform probability space

7.2

Answer 13

n = |Ω| (n represents the number of outcomes)
Pr[w] = 1/n

Question 14

Probability of an event E in a uniform probability space

7.2

Answer 14

Pr[E] = m/n
where m=|E| (remember E is a subset)
and n=|Ω|

Question 15

Pr[w] = 1/n

7.2

Answer 15

the probability of each outcome in a uniform probability space

Question 16

Pr[E] = m/n

7.2

Answer 16

the probability of event E in a uniform probability space

Question 17

Fair

7.3

Answer 17

uniform probability space

Question 18

Biased

7.3

Answer 18

non-uniform probability space
outcomes are parameterized

Question 19

Probability for biased coin

7.3

Answer 19

Pr[H] = p
Pr[T] = 1 - p

Question 20

Bernoulli Trial

7.3

Answer 20

probability space with two outcomes
success = p and failure = q
parameterized such that q = 1 - p

Question 21

Random Permutation
(of n distinct objects)

7.3

Answer 21

an element of the uniform probability space whose outcomes are all possible permutations

Question 22

Probability of a random permutation

7.3

Answer 22

1 / n!

Question 23

Probability that object i occurs in position j in a random permutation

7.3

Answer 23

(n-1)! / n!

1 / n

Question 24

P0

7.4

Answer 24

Pr[E] ≥ 0

Since it’s the sum of non-negative numbers.

Question 25

Pr[E] ≥ 0

7.4

Answer 25

P0

Question 26

Pr[Ω] = 1

7.4

Answer 26

P1

Question 27

P1

7.4

Answer 27

Pr[Ω] = 1

Since it adds up the probabilities of all the outcomes in the space.

Question 28

P2

7.4

Answer 28

If A,B are disjoint then
Pr[A∪B] = Pr[A] + Pr[B]

Addition Rule

Question 29

If A,B are disjoint then
Pr[A∪B] = Pr[A] + Pr[B]

7.4

Answer 29

P2

Question 30

If A⊆B then Pr[A] ≤ Pr[B]

7.4

Answer 30

P3

Question 31

P3

7.4

Answer 31

If A⊆B then Pr[A] ≤ Pr[B]

Monotonicity

Question 32

Complement

7.4

Answer 32

if E ⊆ Ω is the event, then
the complement of E is the event Ē = Ω \ E

Question 33

P4

7.4

Answer 33

Pr[Ē] = 1 - Pr[E]

Think: probability of not E

Question 34

Pr[Ē] = 1 - Pr[E]

7.4

Answer 34

P4

Question 35

P5

7.4

Answer 35

Pr[∅] = 0

A sum with no terms

Question 36

Pr[∅] = 0

7.4

Answer 36

P5

Question 37

Pr[A∪B] = Pr[A] + Pr[B] - Pr[A∩B]

7.4

Answer 37

P6

Question 38

P6

7.4

Answer 38

Pr[A∪B] = Pr[A] + Pr[B] - Pr[A∩B]

Inclusion-exclusion for two events

Question 39

P7

7.4

Answer 39

Pr[A∪B] ≤ Pr[A] + Pr[B]

Union bound. Follows directly from P6.

Question 40

Pr[A∪B] ≤ Pr[A] + Pr[B]

7.4

Answer 40

P7