Mathematical Foundations of Computer Science

Lecture Outline
October 18, 2018

The Total Probability Theorem. Consider events E and F . Consider a sample point
ω ∈ E. Observe that ω belongs to either F or F . Thus, the set E is a disjoint union of two
sets: E ∩ F and E ∩ F . Hence we get
Pr[E] = Pr[E ∩ F ] + Pr[E ∩ F ]
= Pr[F ] × Pr[E|F ] + Pr[F ] × Pr[E|F ]
In general, if A1 , A2 , . . . , An form a partition of the sample space and if ∀i, Pr[Ai ] > 0, then
for any event B in the same probability space, we have
n
X n
X
Pr[B] = Pr[Ai ∩ B] = Pr[Ai ] × Pr[B|Ai ]
i=1 i=1

Example. A medical test for a certain condition has arrived in the market. According
to the case studies, when the test is performed on an affected person, the test comes up
positive 95% of the times and yields a “false negative” 5% of the times. When the test is
performed on a person not suffering from the medical condition the test comes up negative
in 99% of the cases and yields a “false positive” in 1% of the cases. If 0.5% of the population
actually have the condition, what is the probability that the person has the condition given
that the test is positive?

Solution. We will consider the following events to answer the question.

C: event that the person tested has the medical condition.
C: event that the person tested does not have the condition.
P : event that the person tested positive.
We are interested in Pr[C|P ]. From the definition of conditional probability and the total
probability theorem we get
Pr[C ∩ P ]
Pr[C|P ] =
Pr[P ]
Pr[C] Pr[P |C]
=
Pr[P ∩ C] + Pr[P ∩ C]
Pr[C] Pr[P |C]
=
Pr[C] Pr[P |C] + Pr[C] Pr[P |C]
0.005 × 0.95
=
0.005 × 0.95 + 0.995 × 0.01
= 0.323
This result means that 32.3% of the people who are tested positive actually suffer from the
condition!
2 Lecture Outline October 18, 2018

Example. A transmitter sends binary bits, 80% 0’s and 20% 1’s. When a 0 is sent, the
receiver will detect it correctly 80% of the time. When a 1 is sent, the receiver will detect
it correctly 90% of the time.
(a) What is the probability that a 1 is sent and a 1 is received?
(b) If a 1 is received, what is the probability that a 1 was sent?

Solution. We will consider the following events.

S0 : event that the transmitter sent a 0.

S1 : event that the transmitter sent a 1.
R1 : event that 1 was received.

(a) We are interested in finding Pr[S1 ∩ R1 ] .

Pr[S1 ∩ R1 ] = Pr[S1 ] × Pr[R1 |S1 ]

= 0.2 × 0.9
= 0.18

(b) We are interested in finding Pr[S1 |R1 ].

Pr[S1 ∩ R1 ]
Pr[S1 |R1 ] =
Pr[R1 ]
0.18
=
Pr[R1 ∩ S1 ] + Pr[R1 ∩ S0 ]
0.18
=
0.18 + Pr[S0 ] × Pr[R1 |S0 ]
0.18
=
0.18 + 0.8 × 0.2
= 0.5294

Example. An urn contains 5 white and 10 black balls. A fair die is rolled and that
number of balls are chosen from the urn.
(a) What is the probability that all of the balls selected are white?
(b) What is the conditional probability that the die landed on 3 if all the balls selected are
white?

Solution. We will consider the following events.

W : event that all of the balls chosen are white.

Di : event that the die landed on i, 1 ≤ i ≤ 6.
October 18, 2018 Lecture Outline 3

(a) We want to find Pr[W ]. We can do this as follows.

6
X
Pr[W ] = Pr[W ∩ Di ]
i=1
X6
= Pr[Di ] Pr[W |Di ]
i=1
6 5


X 1 i
= 15


6 i
i=1
 
1 5 10 10 5 1
= + + + +
6 15 105 455 1365 3003
= 0.075

(b) We want to find Pr[D3 |W ]. This can be done as follows.

Pr[D3 ∩ W ]
Pr[D3 |W ] =
Pr[W ]
Pr[D3 ] × Pr[W |D3 ]
=
Pr[W ]
1/6 × 53 / 15



3
=
0.075
1/6 × 10/455
=
0.075
0.00366
=
0.075
= 0.048

Independent Events. Two events A and B are independent if and only if Pr[A ∩ B] =
Pr[A]×Pr[B]. This definition also implies that if the conditional probability Pr[A|B] exists,
then A and B are independent events if and only if Pr[A|B] = Pr[A] .

Events A1 , A2 , . . . , An are mutually independent if ∀i, 1 ≤ i ≤ n Ai does not “depend” on

any combination of the other events. More formally, for every subset I ⊆ {1, 2, . . . , n},
Y
Pr[∩i∈I Ai ] = Pr[Ai ]
i∈I

In other words, to show that A1 , A2 , . . . , An are mutually independent we must show that
all of the following hold.

Pr[Ai ∩ Aj ] = Pr[Ai ] · Pr[Aj ] ∀ distinct i, j

Pr[Ai ∩ Aj ∩ Ak ] = Pr[Ai ] · Pr[Aj ] · Pr[Ak ] ∀ distinct i, j, k
Pr[Ai ∩ Aj ∩ Ak ∩ Al ] = Pr[Ai ] · Pr[Aj ] · Pr[Ak ] · Pr[Al ] ∀ distinct i, j, k, l
...
Pr[A1 ∩ A2 ∩ · · · ∩ An ] = Pr[A1 ] Pr[A2 ] · · · Pr[An ]
4 Lecture Outline October 18, 2018

The above definition implies that if A1 , A2 , . . . , An are mutually independent events then

Pr[A1 ∩ A2 ∩ . . . ∩ An ] = Pr[A1 ] × Pr[A2 ] × · · · × Pr[An ]

However, note that Pr[A1 ∩ A2 ∩ . . . ∩ An ] = Pr[A1 ] × Pr[A2 ] × · · · × Pr[An ] is not a sufficient

condition for A1 , A2 , . . . , An to be mutually independent.
Do not confuse the concept of disjoint events and independent events. If two events A
and B are disjoint and have a non-zero probability of happening then given that one event
happens reduces the chances of the other event happening to zero, i.e., Pr[A|B] = 0 6= Pr[A].
Thus by definition of independence, events A and B are not independent.

Example. Two cards are sequentially drawn (without replacement) from a well-shuffled
deck of 52 cards. Let A be the event that the two cards drawn have the same value (e.g.
both 4s) and let B be the event that the first card drawn is an ace. Are these events
independent?

Solution. To decide whether the two events are independent we need to check whether
Pr[A ∩ B] = Pr[A] Pr[B].

3 1
Pr[A] = =
51 17
4 1
Pr[B] = =
52 13
1 3
Pr[A ∩ B] = ×
13 51
1
=
221
1 1
= ×
17 13
= Pr[A] Pr[B]

Example. Suppose that a fair coin is tossed twice. Let A be the event that a head is
obtained on the first toss, B be the event that a head is obtained on the second toss, and
C be the event that either two heads or two tails are obtained. (a) Are events A, B, C
pairwise independent? (b) Are they mutually independent?

Solution. Note that Ω = {HH, HT, T H, T T }. A = {HH, HT }, B = {HH, T H}, C =

{HH, T T }, A ∩ B = {HH}, A ∩ C = {HH}, B ∩ C = {HH}, A ∩ B ∩ C = {HH}. The
October 18, 2018 Lecture Outline 5

probabilities of the relevant events are as follows.

Pr[A] = 1/2
Pr[B] = 1/2
Pr[C] = 1/2
Pr[A ∩ B] = 1/4 = Pr[A] Pr[B]
Pr[A ∩ C] = 1/4 = Pr[A] Pr[C]
Pr[B ∩ C] = 1/4 = Pr[B] Pr[C]
Pr[A ∩ B ∩ C] = 1/4 6= Pr[A] Pr[B] Pr[C]

Thus we see that A, B, C are pairwise independent but not mutually independent.

Example. Consider the experiment in which we roll a dice twice. Consider the following
events.

A: event that the first roll results in a 1, 2, or a 3.

B: event that the first roll results in a 3, 4, or a 5.
C: event that the sum of the two rolls is a 9

Are events A, B, and C mutually independent?

Solution. We show below that the events are not mutually independent as they are not
pairwise independent.

A = {(i, j) | 1 ≤ i ≤ 3 and 1 ≤ j ≤ 6}
B = {(i, j) | 3 ≤ i ≤ 5 and 1 ≤ j ≤ 6}
C = {(3, 6), (6, 3), (4, 5), (5, 4)}
A ∩ B = {(3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6)}
A ∩ C = {(3, 6)}
B ∩ C = {(3, 6), (4, 5), (5, 4)}
A ∩ B ∩ C = {(3, 6)}
Pr[A] = 1/2
Pr[B] = 1/2
Pr[C] = 1/9
Pr[A ∩ B ∩ C] = 1/36 = Pr[A] · Pr[B] · Pr[C]
Pr[A ∩ B] = 1/6 6= Pr[A] · Pr[B]
Pr[A ∩ C] = 1/36 6= Pr[A] · Pr[C]
Pr[B ∩ C] = 3/36 6= Pr[B] · Pr[C]