18.

440: Lecture 4
Axioms of probability and
inclusion-exclusion

Scott Sheeld

MIT

18.440 Lecture 4

1
Outline

Axioms of probability

Consequences of axioms

Inclusion exclusion

18.440 Lecture 4
2
Outline

Axioms of probability

Consequences of axioms

Inclusion exclusion

18.440 Lecture 4

3
Axioms of probability

P(A) [0, 1] for all A S.

P(S) = 1.
Finite additivity: P(A B) = P(A) + P(B) if A B = .

Countable additivity: P(
i=1 Ei ) = i=1 P(Ei ) if Ei Ej =
for each pair i and j.

18.440 Lecture 4
4

I Neurological: When I think it will rain tomorrow the
truth-sensing part of my brain exhibits 30 percent of its
maximum electrical activity.

I Frequentist: P(A) is the fraction of times A occurred during
the previous (large number of) times we ran the experiment.

I Market preference (risk neutral probability): P(A) is
price of contract paying dollar if A occurs divided by price of
contract paying dollar regardless.

I Personal belief: P(A) is amount such that Id be indierent
between contract paying 1 if A occurs and contract paying
P(A) no matter what.

18.440 Lecture 4

5
Axiom breakdown

I What if personal belief function doesnt satisfy axioms?
I
Consider an A-contract (pays 10 if candidate A wins election)
a B-contract (pays 10 dollars if candidate B wins) and an
A-or-B contract (pays 10 if either A or B wins).
I
Friend: Id say A-contract is worth 1 dollar, B-contract is
worth 1 dollar, A-or-B contract is worth 7 dollars.
I
Amateur response: Dude, that is, like, so messed up.
Havent you heard of the axioms of probability?
I
Professional response: I fully understand and respect your
opinions. In fact, lets do some business. You sell me an A
contract and a B contract for 1.50 each, and I sell you an
A-or-B contract for 6.50.
I
Friend: Wow... youve beat by suggested price by 50 cents
on each deal. Yes, sure! Youre a great friend!
I
Axioms breakdowns are money-making opportunities.
18.440 Lecture 4 6

I Neurological: When I think it will rain tomorrow the
truth-sensing part of my brain exhibits 30 percent of its
maximum electrical activity. Should have P(A) [0, 1],
maybe P(S) = 1, not necessarily P(A B) = P(A) + P(B)
when A B = .

I Frequentist: P(A) is the fraction of times A occurred during
the previous (large number of) times we ran the experiment.
Seems to satisfy axioms...

I Market preference (risk neutral probability): P(A) is
price of contract paying dollar if A occurs divided by price of
contract paying dollar regardless. Seems to satisfy axioms,
assuming no arbitrage, no bid-ask spread, complete market...

I Personal belief: P(A) is amount such that Id be indierent
between contract paying 1 if A occurs and contract paying
P(A) no matter what. Seems to satisfy axioms with some
notion of utility units, strong assumption of rationality...
18.440 Lecture 4
7
Outline

Axioms of probability

Consequences of axioms

Inclusion exclusion

18.440 Lecture 4
8
Outline

Axioms of probability

Consequences of axioms

Inclusion exclusion

18.440 Lecture 4
9
Intersection notation

I We will sometimes write AB to denote the event A B.

18.440 Lecture 4

10
Consequences of axioms

I Can we show from the axioms that P(Ac ) = 1 P(A)?

I Can we show from the axioms that if A B then

P(A) P(B)?

I Can we show from the axioms that

P(A B) = P(A) + P(B) P(AB)?

I Can we show from the axioms that P(AB) P(A)?

I Can we show from the axioms that if S contains nitely many

eelements x1 , . . . , xk , then the values

l
P({x1 }), P({x2 }), . . . , P({xk }) determine the value of P(A)
for any A S?

I What k-tuples of values are consistent with the axioms?

18.440 Lecture 4

11
Famous 1982 Tversky-Kahneman study (see wikipedia)

I People are told Linda is 31 years old, single, outspoken, and
very bright. She majored in philosophy. As a student, she was
deeply concerned with issues of discrimination and social
justice, and also participated in anti-nuclear demonstrations.

I They are asked: Which is more probable?
Linda is a bank teller.
Linda is a bank teller and is active in the feminist movement.

I 85 percent chose the second option.

I Could be correct using neurological/emotional denition. Or a
which story would you believe interpretation (if witnesses
oering more details are considered more credible).

I But axioms of probability imply that second option cannot be
more likely than rst.

18.440 Lecture 4

12
Outline

Axioms of probability

Consequences of axioms

Inclusion exclusion

18.440 Lecture 4

13
Outline

Axioms of probability

Consequences of axioms

Inclusion exclusion

18.440 Lecture 4

14
Inclusion-exclusion identity

I Imagine we have n events, E1 , E2 , . . . , En .

I How do we go about computing something like

P(E1 E2 . . . En )?

I It may be quite dicult, depending on the application.

I There are some situations in which computing
P(E1 E2 . . . En ) is a priori dicult, but it is relatively
easy to compute probabilities of intersections of any collection
of Ei . That is, we can easily compute quantities like
P(E1 E3 E7 ) or P(E2 E3 E6 E7 E8 ).

I In these situations, the inclusion-exclusion rule helps us
compute unions. It gives us a way to express
P(E1 E2 . . . En ) in terms of these intersection
probabilities.

18.440 Lecture 4
15
Inclusion-exclusion identity

I Can we show from the axioms that

P(A B) = P(A) + P(B) P(AB)?

I How about P(E F G ) =

P(E ) + P(F ) + P(G ) P(EF ) P(EG ) P(FG ) + P(EFG )?

I More generally,

n
P(ni=1 Ei ) = P(Ei ) P(Ei1 Ei2 ) + . . .
i=1 i1 <i2

+ (1)(r +1) P(Ei1 Ei2 . . . Eir )

i1 <i2 <...<ir

+ ... + (1)n+1 P(E1 E2 . . . En ).

The notation i1 <i2 <...<ir means a sum over all of the nr

P e l
I

subsets of size r of the set {1, 2, . . . , n}.
18.440 Lecture 4
16
Inclusion-exclusion proof idea

I Consider a region of the Venn diagram contained in exactly
m > 0 subsets. For example, if m = 3 and n = 8 we could
consider the region E1 E2 E3c E4c E5 E6c E7c E8c .

I This region is contained in three single intersections (E1 , E2 ,
and E5 ). Its contained in 3 double-intersections (E1 E2 , E1 E5 ,
and E2 E5 ). Its contained in only 1 triple-intersection
(E1 E2 E5 ).
It is counted
m1
m2 +
m3 + . . .
m
e l e l e l e l
m times in the

I
inclusion exclusion sum.

I How many is that?

I Answer: 1. (Follows from binomial expansion of (1 1)m .)

I Thus each region in E1 . . . En is counted exactly once in

the inclusion exclusion sum, which implies the identity.

18.440 Lecture 4
17
Famous hat problem

I n people toss hats into a bin, randomly shue, return one hat
to each person. Find probability nobody gets own hat.

I Inclusion-exclusion. Let Ei be the event that ith person gets
own hat.

I What is P(Ei1 Ei2 . . . Eir )?
(nr )!

I Answer: .
en!nl
I
There are r terms like that in the inclusion exclusion sum.
What is nr (nr )!
e l
n!
?
I
Answer: r1
! .

1 1 1 1

I
P(ni=1 Ei ) = 1 2! + 3! 4! + . . . n!

1 1 1
1
I
1 P(ni=1 Ei ) = 1 1 + 2! 3! + 4! . . . n! 1/e .36788

18.440 Lecture 4

18
MIT OpenCourseWare
http://ocw.mit.edu

18.440 Probability and Random Variables

Spring 2014

For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.