Probability recap

Question 1

What is a finite probability space?

Answer 1

A finite probability space is defined by a sample space of possible outcomes and probability masses for each outcome such that their total sum is 1.

Question 2

What is the formula to compute the probability of an event E in a finite probability space?

Answer 2

Pr[E] = Σ p(i) for all i in E, where p(i) is the probability mass of outcome i.

Question 3

In a finite probability space where all outcomes are equally likely, how do you calculate the probability of an event E?

Answer 3

Pr[E] = |E| / |Ω|, where |E| is the size of event E and |Ω| is the size of the sample space.

Question 4

What does the complementary event E represent?

Answer 4

E represents all outcomes not in E. Pr[E] = 1 - Pr[E].

Question 5

Define conditional probability.

Answer 5

Conditional probability of E given F is Pr[E|F] = Pr[E ∩ F] / Pr[F], assuming Pr[F] > 0.

Question 6

What is the union bound?

Answer 6

The union bound states Pr[∪Ei] ≤ ΣPr[Ei], for any events E1, E2, …, En.

Question 7

When are two events E and F independent?

Answer 7

Two events are independent if Pr[E ∩ F] = Pr[E] × Pr[F].

Question 8

How do you determine the probability of a union of disjoint events?

Answer 8

If events are disjoint, Pr[∪Ei] = ΣPr[Ei].

Question 9

What is an example of a finite probability space?

Answer 9

Flipping a fair coin: Sample space Ω = {heads, tails}, p(heads) = p(tails) = 1/2.

Question 10

Problem: If a fair die is rolled, what is the probability of rolling an even number?

Answer 10

Pr[even] = |E| / |Ω| = 3 / 6 = 1/2.

Question 11

Problem: A biased coin has p(heads) = 2/3. What is p(tails)?

Answer 11

Pr[tails] = 1 - Pr[heads] = 1 - 2/3 = 1/3.

Question 12

Describe the Process Naming problem sample space.

Answer 12

The sample space is the set of all n-tuples of integers between 0 and 2^k - 1, with 2^kn outcomes, each with probability 2^(-kn).

Question 13

Problem: What is the probability that processes p1 and p2 choose the same identifier in the Process Naming problem?

Answer 13

Pr[E] = 2^(k(n-1)) × 2^(-kn) = 2^(-k).

Question 14

What is the key idea of the union bound in randomized algorithms?

Answer 14

Decompose complex events into simple ones whose probabilities are easy to compute, then use the union bound to estimate the overall probability.

Question 15

Define an infinite sample space.

Answer 15

An infinite sample space consists of all sequences of outcomes from a fixed set X, with weights assigned to each symbol.

Question 16

Problem: Compute Pr[E] for the event that all sequences in Ω begin with ‘1’ in an infinite sample space where X={0,1}, and w(1)=1/2.

Answer 16

Pr[Eσ] = w(1) = 1/2.

Question 17

What happens when an event in an infinite sample space has probability 0?

Answer 17

An event with probability 0 might still occur; it just has an infinitely small likelihood.

Question 18

Problem: Show that the probability of at least one head in infinite coin flips is 1.

Answer 18

Pr[at least one head] = ΣPr[Eσi] = Σ2^(-i) = 1 (geometric series).

Question 19

What does independence mean for a collection of events?

Answer 19

A collection of events E1, E2, …, En is independent if Pr[∩Ei] = ΠPr[Ei] for all subsets of events.

Question 20

Problem: Suppose three coins are flipped. Are the events A (1st coin heads), B (2nd coin heads), and C (3rd coin tails) independent?

Answer 20

Yes, because Pr[A ∩ B ∩ C] = Pr[A] × Pr[B] × Pr[C] = 1/2 × 1/2 × 1/2 = 1/8.