1

Lecture 3:

Independence

Chris Gregg

Summer 2026

Learning Goals of Today

Mutually Exclusive

Independent

Makes AND easy:

Makes OR easy:

Review

Notation

4

And

Or

Given

Relationship Between Probabilities

5

Law of Total�Probability

Definition of�conditional probability

Chain rule�(Product rule)

Bayes’�Theorem

Review: Chain Rule

Piech, CS109, Stanford University

Definition of conditional probability:

The Chain Rule:

​

10

Bayes’ Theorem

7

SARS Virus Testing

• A test is 98% effective at detecting SARS (*the test comes back positive for someone who has SARS)
• However, test has a “false positive” rate of 1%
• 0.5% of US population has SARS
• Let E = you test positive for SARS with this test
• Let F = you actually have SARS
• What is P(F | E)?
• Solution:

​

≈ 0.330

Bayes’ Theorem and Spam

9

posterior

likelihood

prior

normalization constant

• 60% of all email in 2016 is spam.
• 20% of spam has the word “Dear”
• 1% of non-spam (aka ham) has the word “Dear”

You get an email with the word “Dear” in it.

What is the probability that the email is spam?

Bayes’ Theorem and Spam

10

• 60% of all email in 2016 is spam.
• 20% of spam has the word “Dear”
• 1% of non-spam (aka ham) has the word “Dear”

You get an email with the word “Dear” in it.

What is the probability that the email is spam?

Bayes’ Theorem and Spam

11

• 60% of all email in 2016 is spam.
• 20% of spam has the word “Dear”
• 1% of non-spam (aka ham) has the word “Dear”

You get an email with the word “Dear” in it.

What is the probability that the email is spam?

.2

.6

.2

.6

.01

(1-0.6)

= 0.968

Intuition Time

Bayes Theorem Intuition

All People

Bayes Theorem Intuition

All People

People with SARS

Bayes Theorem Intuition

All People

People who test positive

Bayes Theorem Intuition

All People

People with SARS

People who test positive

Bayes Theorem Intuition

Conditioning on a positive result changes the sample space to this:

≈ 0.330

People who test positive

People who test positive and have SARS

Bayes Theorem Intuition

Conditioning on a positive result changes the sample space to this:

≈ 0.330

People who test positive

P(F)P(E|F)

P(F)P(E|F) +

P(F^c)P(E|F^c)

People who test positive and have SARS

Let E = you test positive for SARS with this test

Let F = you actually have SARS

Bayes Theorem Intuition

All People

People with positive

test

People with SARS

Bayes Theorem Intuition

Say we have 1000 people:

5 have SARS and test positive, 985 do not have SARS and test negative.

10 do not have SARS and test positive.

≈ 0.333

Bayes Theorem Intuition

Conditioned on just those that test positive:

5 have SARS and test positive, 985 do not have SARS and test negative.

10 do not have SARS and test positive.

≈ 0.333

Notice that all the people with SARS are here, but the group is still mainly folks without SARS

Why it is still good to get tested

​

​

​

• Let E^c = you test negative for SARS with this test
• Let F = you actually have SARS
• What is P(F | E^c)?

​

≈ 0.0001

End Review

Law of Total Probability

Sample Space

F

E

F^C

Law of Total Probability

Spam

Not Spam

Sample Space

Email

F

E

F^C

Law of Total Probability

B₁

B₂

Sample Space

E

B₃

B₄

Thm

are mutually exclusive

partition events:

Background event. Where is the person in San Francisco?

San Francisco, CA

Background event. Where is the person in San Francisco?

San Francisco, CA

From Google’s Perspective:

There are 18 different “districts” in San Francisco.

​

Know:

​

​

​

​

Want:

It rains tomorrow

Person is in district i

Background event. Where is the person in San Francisco?

San Francisco, CA

From Google’s Perspective:

There are 18 different “districts” in San Francisco.

​

Know:

​

​

​

​

Want:

Background event. Where is the person in San Francisco?

San Francisco, CA

From Google’s Perspective:

There are 18 different “districts” in San Francisco.

​

Know:

​

​

​

​

Want:

Monty Hall Problem

31

Monty Hall Problem

32

Monty Hall Problem from Let’s Make a Deal

• Behind one door is a prize (equally likely to be any door).
• Behind the other two doors is nothing
• We choose a door
• Host opens 1 of other 2 doors, revealing nothing
• We are given an option to change to the other door.
• Should we switch?

Doors A,B,C

Note: If we don’t switch,

​

P(Win) = 1/3

In the world where we switch

A: Prize in Door A

• Host opens B or C
• We switch
• We always lose
• P(Win | A) = 0

B: Prize in Door B

• Host must open C
• We switch to B
• We always win
• P(Win | B) = 1

C: Prize in Door C

• Host must open B
• We switch to C
• We always win
• P(Win | C) = 1

34

Without loss of generality, say we pick A (out of Doors A,B,C).

1/3

1/3

1/3

You should switch!

Marilyn Vos Savant

35

Monty Hall, 1000 envelope version

• Start with 1000 envelopes (of which 1 is the prize).
• You choose 1 envelope.�
• I open 998 of remaining�999 (showing they are empty).��
• Should you�switch?

36

No: P(win without switching) =

Yes: P(win with new knowledge) =

Learning Goals for Rest of Today

Mutually Exclusive

Independent

Makes AND easy:

Makes OR easy:

Probability of “OR”

Review: OR with Mutually Exclusive Events

P (E [ F ) = P (E) + P (F )

If events are mutually exclusive, probability of OR is simple:

7/50

4/50

Review: OR with Mutually Exclusive Events

If events are mutually exclusive, probability of OR is simple:

7 4 11

P (E [ F ) = ₅₀ ⁺ ₅ ⁼

7/50

4/50

Piech, CS109, Stanford Uversity

What about when they are not

Mutually exclusive?

AKA

Inclusion Exclusion

OR without Mutually Exclusive Events

AKA

Inclusion Exclusion

OR without Mutually Exclusive Events

More than two sets?

Inclusion / Exclusion with Three Events

E

F

G

P (E or F or G) =

or

Inclusion / Exclusion with Three Events

E

​

1

F

G

Piech, CS109, Stanford University

1

1

1

P (E [ F [ G) = _{P (E)}

or

or

Inclusion / Exclusion with Three Events

E

​

1

F

G

Piech, CS109, Stanford University

2

1

2

1

1

P (E [ F [ G) = _{P (E) + P (F )}

or

or

Inclusion / Exclusion with Three Events

E

​

1

F

G

Piech, CS109, Stanford University

2

1

2

1

1

P (E [ F [ G) = _{P (E) + P (F )}

or

or

1

2

3

2

Inclusion / Exclusion with Three Events

E

​

1

2

2

3

1

1

2

F

G

Piech, CS109, Stanford University

^{P (E [ F [ G) =} P (E) + P (F ) + P (G)

or

or

Inclusion / Exclusion with Three Events

^{P (E [ F [ G) =} P (E) + P (F ) + P (G)

—P (EF )

E 1

1

2

2

1

1

2

F

G

Piech, CS109, Stanford University

or

or

Inclusion / Exclusion with Three Events

1

1

1

2

F

G

Piech, CS109, Stanford University

1

1

^{P (E [ F [ G) =} P (E) + P (F ) + P (G)

—P (EF ) — P (EG)

E 1

or

or

Inclusion / Exclusion with Three Events

E

Piech, CS109, Stanford University

F

G

1

1

1

1

1

1

1

^{P (E [ F [ G) =} P (E) + P (F ) + P (G)

—P (EF ) — P (EG) — P (FG)

+P (EFG)

or

or

Inclusion / Exclusion with 3 Events

Inclusion / Exclusion with 4 Events

General Inclusion / Exclusion

n

Piech, CS109, Stanford University

P (E₁ [ E₂ [ · · · [ E ) =

n

X

r=1

X

r+1

(—1) Y

r

* Where Y_r is the sum, for all combinations of r events, of the probability of the union those events.

Y₁ = Sum of all events on their own

i

i

P (E )

X

i,j,k

P (E_i \ E_j \ E_k)

s.t.i =6 j, j 6= k, i =6 k

X

i,j

P (E_i \ E_j )

s.t.i =6 j

Y₂ = Sum of all pairs of events

Y₃ = Sum of all triples of events

Where Y_r is the sum, for all combinations of r events, of the probability of the intersection of those events

or

or

and

and

and

Learning Goals of Today

Mutually Exclusive

Independent

Makes AND easy:

Makes OR easy:

Probability of “AND”

Piech, CS109, Stanford University

Independence

Two events A and B are called independent if:

​

Piech, CS109, Stanford University

Otherwise, they are called dependent events

Knowing that event B happened, doesn’t change our belief that A will happen.

Alternative Definition of Independence

Piech, CS109, Stanford University

Chain rule

Since B is independent of A

If you show this is true, you have proved the two events are independent!

Notation for and

If events are independent

probability of AND is easy!

*You will need to use this “trick” with high probability

Dice, our misunderstood friends

What is P(E), P(G), and P(E G)?

• P(E) = 1/6, P(G) = 4/36 = 1/9, P(E G) = 1/36
• P(E G) ≠ P(E) P(G) → E and G dependent

​

Piech, CS109, Stanford University

Roll two 6-sided dice, yielding values D₁ and D₂

• Let E be event: D₁ = 1
• Let F be event: D₂ = 1
• Let G be event: D₁ + D₂ = 5

​

​

{(1, 4), (2, 3), (3, 2), (4, 1)}

What is P(E), P(F), and P(E F)?

• P(E) = 1/6, P(F) = 1/6, P(E F) = 1/36
• P(E F) = P(E) P(F) → E and F independent

Intuition through proofs:

Independence is reciprocal

If A is independent of B, then B is independent of A

Piech, CS109, Stanford University

Proof:

Bayes’ Thm.

Because A is independent of B

Independence

So if A and B are independent A and B^C are also independent

Piech, CS109, Stanford University

Given independent events A and B, prove that A and B^C are independent

We want to show that P( AB^C) = P( A)P(B^C)

P (AB^C ) = P (A) — P (AB)

= P (A) — P (A)P (B)

= P (A)[1 — P (B)]

= P (A)P (B^C )

By Total Law of Prob.

By independence Factoring

Since P(B) + P(B^C) = 1

Independence of a complement

What does independence look like?

Independence

A

B

S

|AB| ₌ |A| _⇥ |B|

|S| |S| |S|

Independence Definition 1:

P (AB) = P (A)P (B)

0

Piech, CS109, Stanford University

Independence

A

B

S

|AB| ₌ |A| _⇥ |B|

|S| |S| |S|

Independence Definition 1:

P (AB) = P (A)P (B)

0

Piech, CS109, Stanford University

Not independence!

Independence

A

B

S

|AB| ₌ |A| _⇥ |B|

|S| |S| |S|

Independence Definition 1:

P (AB) = P (A)P (B)

0

Piech, CS109, Stanford University

Not independence!

This is mutual exclusion!

Independence

A

Piech, CS109, Stanford University

B

AB

S

Independence Definition 1:

P (AB) = P (A)P (B)

|AB| ₌ |A| _⇥ |B|

|S| |S| |S|

Independence Definition 2:

P (A|B) = P (A)

|AB| ₌ |A|

|B| |S|

Independence

A

S

B

Piech, CS109, Stanford University

AB

This ratio, P(A)…

… is the same as this one, P(A|B)

Independence

A

Piech, CS109, Stanford University

B

AB

S

Independence Definition 1:

P (AB) = P (A)P (B)

|AB| ₌ |A| _⇥ |B|

|S| |S| |S|

Independence Definition 2:

P (A|B) = P (A)

|AB| ₌ |A|

|B| |S|

Dependence

A

|AB|

|B|

|A|

|S|

=

Piech, CS109, Stanford University

B

AB

S

Independence Definition 1:

P (AB) = P (A)P (B)

|AB| ₌ |A| _⇥ |B|

|S| |S| |S|

Independence Definition 2:

P (A|B) = P (A)

Generalized Independence

Piech, CS109, Stanford University

General definition of Independence:

Events E₁ , E₂ , ..., E_n are independent if for every subset

with r elements (where r ≤ n) it holds that:

​

​

Example: outcomes of n separate flips of a coin are all independent of one another

• Each flip in this case is called a “trial” of the experiment

Math > Intuition

Two Dice

Piech, CS109, Stanford University

Roll two 6-sided dice, yielding values D₁ and D₂

• Let E be event: D₁ = 1
• Let F be event: D₂ = 6
• Let G be event: D₁ + D₂ = 7

2. Are E and G independent?

• P(E) = 1/6, P(G) = 1/6,

P(E G) = 1/36

[roll (1, 6)]

• P(F) = 1/6, P(G) = 1/6, P(F G) = 1/36

​

[roll (1, 6)]

Yes!

1. Are E and F independent?

3. Are F and G independent?

4. Are E, F and G independent?

• P(E F G) = 1/36 ≠ 1/216 = (1/6)(1/6)(1/6)

​

​

Yes!

Yes!

No!

When you impose a 1 and a 6, the sum is redundant

New Ability

Properties of Pairs of Events

Mutually Exclusive

Independent

also:

also:

Story: Ultimate Probability

https://www.youtube.com/watch?v=H2IfTwGisOg

https://www.maikaisogawa.com/ultimate-frisbee-probability/

Practice: Lets do the Frisbee Problem.

• You flip two frisbees. For each frisbee, the probability that it lands “heads” is 0.6. The two frisbees are considered “even” if both frisbees are heads or both frisbees are tails.
• What is the probability that the frisbees are even?

80

Same Problem!

81

Let p be the probability of a 1 from unknown_random.

What is the probability of a True from fair_random if p =.45?

Network reliability

82

Consider the following parallel network:

• 𝑛 independent routers, each with

probability 𝑝_i of functioning (where 1 ≤ 𝑖 ≤ 𝑛)

• 𝐸 = functional path from A to B exists.

What is P(E)?

​

𝑝₁

𝑝₂

𝑝_𝑛

…

𝐴

𝐵

Piech, CS109, Stanford University

Network reliability

83

Consider the following parallel network:

• 𝑛 independent routers, each with

probability 𝑝_i of functioning (where 1 ≤ 𝑖 ≤ 𝑛)

• 𝐸 = functional path from A to B exists.

What is P(E)?

​

𝑝₁

𝑝₂

𝑝_𝑛

…

𝐴

𝐵

Piech, CS109, Stanford University

Network reliability

84

Consider the following parallel network:

• 𝑛 independent routers, each with

probability 𝑝_i of functioning (where 1 ≤ 𝑖 ≤ 𝑛)

• 𝐸 = functional path from A to B exists.

What is P(E)?

​

𝑝₁

𝑝₂

𝑝_𝑛

…

𝐴

𝐵

Piech, CS109, Stanford University

Network reliability

85

Consider the following parallel network:

• 𝑛 independent routers, each with

probability 𝑝_i of functioning (where 1 ≤ 𝑖 ≤ 𝑛)

• 𝐸 = functional path from A to B exists.

What is P(E)?

​

𝑝₁

𝑝₂

𝑝_𝑛

…

𝐴

𝐵

Piech, CS109, Stanford University

Network reliability

86

Consider the following parallel network:

• 𝑛 independent routers, each with

probability 𝑝_i of functioning (where 1 ≤ 𝑖 ≤ 𝑛)

• 𝐸 = functional path from A to B exists.

What is P(E)?

​

𝑝₁

𝑝₂

𝑝_𝑛

…

𝐴

𝐵

Piech, CS109, Stanford University

Learning Goals of Today

Mutually Exclusive

Independent

Makes AND easy:

Makes OR easy:

Independence relationships can change with conditioning.

If E and F are independent, that does not mean they will still be independent given another event G.