Conditional Probability

Definition

Let A and $B$ be events with $Pr [B] > 0$ $Pr [A ∣ B] = \frac{P r [ A \cap B ]}{P r [ B ]}$

Basic Properties

$Pr [A ∣Ω] = Pr [A]$
$Pr [A ∣ A] = 1$
$Pr [A ∣ \overset{ˉ}{A}] = 0$
$Pr [A \cap B] = Pr [A ∣ B] \cdot Pr [B] = Pr [B ∣ A] \cdot Pr [A]$

Bayes Formula

Let $A_{1}, \dots, A_{n}$ be pairwise disjoint events with $Pr [A_{i}] > 0$ , and let $B$ be an event such that

B \subseteq i = 1 ⋃ n A_{i} and Pr [B] > 0.

Then for every $k \in {1, \dots, n}$ ,

Pr [A_{k} ∣ B] = \frac{Pr [ A _{k} \cap B ]}{Pr [ B ]} = \frac{Pr [ B ∣ A _{k} ] Pr [ A _{k} ]}{\sum _{i = 1}^{n} Pr [ B ∣ A _{i} ] Pr [ A _{i} ]} .

Law of total probability

Let $A_{1}, \dots, A_{n}$ be pairwise disjoint events such that

A_{1} \cup \dots \cup A_{n} = Ω and Pr [A_{i}] > 0 for all i .

Then for every event $B$ ,

Pr [B] = i = 1 \sum n Pr [B ∣ A_{i}] Pr [A_{i}] .

This means: split the sample space into cases $A_{1}, \dots, A_{n}$ , compute the probability of $B$ inside each case, and then weight by the probability of the case.

Short proof

Since the $A_{i}$ form a partition of $Ω$ ,

B = i = 1 ⋃ n (B \cap A_{i}),

and these sets are pairwise disjoint. So

Pr [B] = i = 1 \sum n Pr [B \cap A_{i}] .

Using

Pr [B \cap A_{i}] = Pr [B ∣ A_{i}] Pr [A_{i}],

we get

Pr [B] = i = 1 \sum n Pr [B ∣ A_{i}] Pr [A_{i}] .

Example

Suppose:

$30%$ of students come by bike
$70%$ come by train
among bike commuters, $10%$ are late
among train commuters, $20%$ are late

Let:

$A_{1}$ = “student comes by bike”
$A_{2}$ = “student comes by train”
$B$ = “student is late”

Then

Pr [B] = Pr [B ∣ A_{1}] Pr [A_{1}] + Pr [B ∣ A_{2}] Pr [A_{2}] = 0.1 \cdot 0.3 + 0.2 \cdot 0.7 = 0.17.

Independent Events

Two events $A$ and $B$ are independent if

Pr [A \cap B] = Pr [A] Pr [B] .

If $Pr [B] > 0$ , this is equivalent to

Pr [A ∣ B] = Pr [A] .

Important

This is equivalent to saying that the indicator variables $1_{A}$ and $1_{B}$ are independent random variables.

For multiple events $A_{1}, \dots, A_{n}$ , the strongest notion is mutual independence: for every non-empty subset $I \subseteq {1, \dots, n}$ ,

Pr [i \in I ⋂ A_{i}] = i \in I \prod Pr [A_{i}] .

In particular (necessary but not sufficient),

Pr [A_{1} \cap A_{2} \cap \dots \cap A_{n}] = Pr [A_{1}] Pr [A_{2}] \dots Pr [A_{n}] .

For an infinite family of events $(A_{i})_{i \in J}$ , mutual independence means that every finite subfamily is mutually independent. Equivalently, for every distinct $i_{1}, \dots, i_{k} \in J$ ,

Pr [A_{i_{1}} \cap \dots \cap A_{i_{k}}] = Pr [A_{i_{1}}] \dots Pr [A_{i_{k}}] .

NOTE

Pairwise independence is weaker: it only requires $Pr [A_{i} \cap A_{j}] = Pr [A_{i}] Pr [A_{j}]$ for all pairs $i \neq = j$ . This does not imply mutual independence.

Useful Lemma

If $A, B, C$ are mutually independent, then

$A \cap B$ and $C$ are independent
$A \cup B$ and $C$ are independent.

Proof:

Pr [(A \cap B) \cap C] = Pr [A \cap B \cap C] = Pr [A] Pr [B] Pr [C] = Pr [A \cap B] Pr [C] .

So $A \cap B$ and $C$ are independent. Also,

Pr [(A \cup B) \cap C] = Pr [(A \cap C) \cup (B \cap C)]

= Pr [A \cap C] + Pr [B \cap C] - Pr [A \cap B \cap C]

= Pr [A] Pr [C] + Pr [B] Pr [C] - Pr [A] Pr [B] Pr [C]

= (Pr [A] + Pr [B] - Pr [A \cap B]) Pr [C] = Pr [A \cup B] Pr [C] .

So $A \cup B$ and $C$ are independent.

Multiplication Principle (Chain rule)

Pr [A_{1} \cap A_{2} \cap \dots \cap A_{n}] = Pr [A_{1}] \cdot Pr [A_{2} ∣ A_{1}] \cdot Pr [A_{3} ∣ A_{1} \cap A_{2}] \dots Pr [A_{n} ∣ A_{1} \cap \dots \cap A_{n - 1}]

Short proof: for $n = 2$ this is exactly

Pr [A_{1} \cap A_{2}] = Pr [A_{2} ∣ A_{1}] Pr [A_{1}] .

For general $n$ ,

Pr [A_{1} \cap \dots \cap A_{n}] = Pr [A_{n} ∣ A_{1} \cap \dots \cap A_{n - 1}] \cdot Pr [A_{1} \cap \dots \cap A_{n - 1}] .

Apply the same identity again to $Pr [A_{1} \cap \dots \cap A_{n - 1}]$ , and continue recursively. This yields the full product above.

Application: Balls into Boxes

Throw $m$ balls independently and uniformly at random into $n$ boxes. What is the probability that every ball lands in an empty box? Equivalently, what is the probability that no two balls land in the same box?

Let $A_{i}$ be the event that the $i$ -th ball lands in an empty box. Then

Pr [A_{1}] = 1, Pr [A_{2} ∣ A_{1}] = \frac{n - 1}{n}, Pr [A_{3} ∣ A_{1} \cap A_{2}] = \frac{n - 2}{n},

and in general

Pr [A_{i} ∣ A_{1} \cap \dots \cap A_{i - 1}] = \frac{n - i + 1}{n} .

This is because after $i - 1$ successful throws, exactly $n - i + 1$ boxes are still empty.

By the multiplication principle,

Pr [A_{1} \cap \dots \cap A_{m}] = i = 0 \prod m - 1 \frac{n - i}{n} = \frac{n ( n - 1 ) \dots ( n - m + 1 )}{n ^{m}} .

For $m ≪ n$ , we can approximate

Pr [A_{1} \cap \dots \cap A_{m}] = i = 0 \prod m - 1 (1 - \frac{i}{n}) \approx i = 0 \prod m - 1 e^{- i / n} = e^{- \sum_{i = 0}^{m - 1} i / n} = e^{- \frac{m ( m - 1 )}{2 n}} .

So the probability that all $m$ balls land in different boxes is approximately

e^{- \frac{m ( m - 1 )}{2 n}} .

If $m > n$ , this probability is $0$ .

Thomas Second Brain

Explorer

Conditional Probability

Basic Properties

Bayes Formula

Law of total probability

Short proof

Example

Independent Events

Useful Lemma

Multiplication Principle (Chain rule)

Application: Balls into Boxes

Graph View

Table of Contents