Mathematics for Computer Science

17.5. The Law of Total Probability 711

This rule extends to any set of disjoint events that make up the entire sample
space. For example,

Rule(Law of Total Probability: 3-events). IfE 1 ;E 2 ;andE 3 are disjoint and
PrŒE 1 [E 2 [E 3 çD 1 , then

PrŒAçDPr



AjE 1



PrŒE 1 çCPr



AjE 2



PrŒE 2 çCPr



AjE 3



PrŒE 3 ç:
This in turn leads to a three-event version of Bayes’ Rule in which the probability
of eventE 1 givenAis calculated from the “inverse” conditional probabilities ofA
givenE 1 ,E 2 , andE 3 :

Rule(Bayes’ Rule: 3-events).

Pr



E 1 jA



D

Pr



AjE 1



PrŒE 1 ç

Pr



AjE 1



PrŒE 1 çCPr



AjE 2



PrŒE 2 çCPr



AjE 3



PrŒE 3 ç
The generalization of these rules tondisjoint events is a routine exercise (Prob-
lems 17.3 and 17.4).

17.5.1 Conditioning on a Single Event

The probability rules that we derived in Section 16.5.2 extend to probabilities con-
ditioned on the same event. For example, the Inclusion-Exclusion formula for two
sets holds when all probabilities are conditioned on an eventC:

Pr



A[BjC



DPr



AjC



CPr



BjC



Pr



A\BjC



:

This is easy to verify by plugging in the Definition 17.2.1 of conditional probabil-
ity.^2
It is important not to mix up events before and after the conditioning bar. For
example, the following isnota valid identity:

False Claim.

Pr



AjB[C



DPr



AjB



CPr



AjC



Pr



AjB\C



: (17.3)

A simple counter-example is to letBandCbe events over a uniform space with
most of their outcomes inA, but not overlapping. This ensures that Pr



AjB



and
Pr



AjC



are both close to 1. For example,

BWWDŒ0::9ç;

CWWDŒ10::18ç[f 0 g;

AWWDŒ1::18ç;

(^2) Problem 17.14 explains why this and similar conditional identities follow on general principles
from the corresponding unconditional identities.