Chapter 2: Axioms of Probability

Part I: Theory

Ver. 092115

Sample Space

2

3

4

Event

5

Set operations

6

HINT

7

DeMorgan’s Law

8

Bertrand Paradox

9

Bertrand Paradox

10

Counter-intuitive Probability

What if

whenever the ball is drawn, it is always randomly drawn ?

11

A possible definition of probability

But, two issues regarding the definitions are raised:

1. can the convergence always happen ?

2. can the convergence be verifiable ?

It would be more reasonable to assume a set of simpler and more self-evident axioms about probability and try to prove the existence of such a constant limiting frequency.

12

Modern Approach..

13

Propositions

Proof

14

15

Inclusion-exclusion identity

Proof: try induction !

Chapter 2. Axioms of Probability�part two

By Andrej Bogdanov

Birthdays

17

You have a room with n people. What is the probability that at least two of them have a birthday on the same day of the year?

Probability model

experiment outcome = birthdays of n people

The sample space consists of all sequences (b₁,…, b_n) where b₁,…, b_n are numbers between 1 and 365

S_n = {(b₁,…, b_n) : 1 ≤ b₁,…, b_n ≤ 365 } = {1, …, 365}ⁿ

Birthdays

18

Probability model

We will assume equally likely outcomes.

This is a simplifying model which ignores some issues, for example:

Leap years have 366 not 365 days

Not all birthdays are equally represented, e.g. September is a popular month for babies

Birthdays among people in the room may be related, e.g. there may be twins inside

Birthdays

19

We are interested in the event that two birthdays are the same:

E_n = {(b₁,…, b_n) : b_i = b_j for some pair i ≠ j }

It will be easier to work with the complement of E:

E_n^c = {(b₁,…, b_n) : (b₁,…, b_n) are all distinct }

365⋅364⋅…⋅(365 – n + 1)

365ⁿ

P(E_n) = 1 – P(E_n^c)

Birthdays

20

P(E_n)

n

Among 23 people, two have the same birthday

with probability about 50%.

Interpretation of probability

21

The probability of an event should equal the fraction of times that it occurs when the experiment is performed many times under the same conditions.

Let’s do the birthday experiment many times and see if this is true.

Simulation of birthday experiment

22

# perform t simulations of the birthday experiment for n people

# output a vector indicating the times event E_n occurred

def simulate_birthdays(n, t):

days = 365

occurred = []

for time in range(t):

# choose random birthdays for everyone

birthdays = []

for i in range(n):

birthdays.append(randint(1, days))

# record the occurrence of event E_n

occurred.append(same_birthday(birthdays))

return occurred

​

# check if event E_n occurs (two people have the same birthday)

def same_birthday(birthdays):

for i in range(len(birthdays)):

for j in range(i):

if birthdays[i] == birthdays[j]:

return True

return False

​

randint(a,b)�Choose a random integer in a range

Interpretation of probability

23

t experiments

n = 23

Fraction of times two people have the

same birthday in the first t experiments

Problem for you to solve

24

You drop 3 blue balls and 3 red balls into 5 bins at random. What is the probability that some bin gets two (or more) balls of the same color?

Generalized inclusion exclusion

25

P(E₁ ∪ E₂) = P(E₁) + P(E₂) – P(E₁E₂)

P(E₁ ∪ E₂ ∪ E₃) =

P(E₂ ∪ E₃) = P(E₂) + P(E₃) – P(E₂E₃)

P(E₁ (E₂ ∪ E₃)) = P(E₁E₂ ∪ E₁E₃)

= P(E₁E₂) + P(E₁E₃) – P(E₁E₂E₃)

P(E₁ ∪ E₂ ∪ E₃) = P(E₁) + P(E₂ ∪ E₃) – P(E₁ (E₂ ∪ E₃))

Generalized inclusion exclusion

26

P(E₁ ∪ E₂ ∪…∪E_n) = ∑_{1 ≤ i ≤ n} P(E_i)

– ∑_{1 ≤ i ≤ j ≤ n} P(E_iE_j)

+ ∑_{1 ≤ i ≤ j ≤ k ≤ n} P(E_iE_jE_k)

…

+ or – P(E₁E₂…E_n)

+ if n is odd,

– if n is even

(-1)ⁿ⁺¹

27

Each of n men throws his hat. The hats are mixed up and randomly reassigned, one to each person. What is the probability that at least someone gets their own hat?

Hats

28

Probability model

outcome = assignment of n hats to n people

The sample space S consists of all permutations

p₁p₂p₃p₄ of the numbers 1, 2, 3, 4

let’s do n = 4: 1342 means

1 gets 1’s hat

2 gets 3’s hat

3 gets 4’s hat

4 gets 2’s hat

Hats

29

1234, 1243, 1324, 1342, 1423, 1432,

2134, 2143, 2314, 2341, 2413, 2431,

3124, 3142, 3214, 3241, 3412, 3421,

4123, 4132, 4213, 4231, 4312, 4321 }

S = {

H: “at least someone gets their own hat”

P(H) =

Now let’s calculate in a different way.

Hats

30

Event H “at least someone gets their own hat”

H = H₁ ∪ H₂ ∪ H₃ ∪ H₄

H_i is the event “person i gets their own hat”.

H₁ = {p₁p₂p₃p₄ : permutations such that p₁ = 1}

and so on.

Hats

31

P(H₁ ∪ H₂ ∪ H₃ ∪ H₄)

We will calculate P(H) by inclusion-exclusion:

Under equally likely outcomes,

Hats

32

H₁ = { p₁p₂p₃p₄ : permutations such that p₁ = 1}

H₂ = { p₁p₂p₃p₄ : permutations such that p₂ = 2}

similarly |H₃| = |H₄| = 3!

P(H₁) = P(H₂) = P(H₃) = P(H₄) = 3!/4!

Hats

33

H₁ = { p₁p₂p₃p₄ : permutations such that p₁ = 1}

H₂ = { p₁p₂p₃p₄ : permutations such that p₂ = 2}

H₁H₂ = { p₁p₂p₃p₄ : permutations s.t. p₁ = 1 and p₂ = 2}

similarly |H₁H₃| = |H₁H₄| = … = |H₃H₄| = 2!

P(H₁H₂) = … = P(H₃H₄) = 2!/4!

Hats

34

P(H₁ ∪ H₂ ∪ H₃ ∪ H₄)

Hats

35

It remains to evaluate

Each term has the form

Hats

36

General formula for n men:

Let E_n = “at least someone gets their own hat”

assuming equally likely outcomes.

Hats

37

P(E_n)

n

Hats

38

Remember from calculus

so P(E_n) → 1 – e^-1 ≈ 0.63212 as n → ∞

Circular arrangements

39

In how many ways can n people sit at a round table?

Once the first person has sat down, the others can be arranged in (n – 1)! ways relative to his position.

(n – 1)!

We do not distinguish between seatings that differ by a rotation of the table.

Round table

40

10 husband-wife couples are seated at random at a round table. What is the probability that no wife sits next to her husband?

Probability model

The sample space S consists of all circular arrangements of {H₁, W₁, …, H₁₀, W₁₀}

We assume equally likely outcomes.

|S| = (n – 1)!

Round table

41

The event N of interest is that no husband and wife are adjacent. Let A₁, …, A₁₀ be the events

A_i = “The husband-wife pair H_i, W_i is adjacent”

P(N) = 1 – P(N^c) = 1 – P(A₁ ∪ … ∪ A₁₀)

so

We calculate this using inclusion-exclusion.

Round table

42

The inclusion exclusion formula involves expressions like P(A₁), P(A₂A₅), P(A₃A₄A₇A₉).

Let’s start with P(A₁), so we want H₁ and W₁ adjacent.

We need to calculate |A₁|, the number of circular arrangements in which H₁ and W₁ are adjacent.

Round table

43

We use the basic principle of counting.

Treating the couple H₁, W₁ as a single unordered item, we get 18! circular arrangements

For each of this arrangements, the couple can sit in the order H₁W₁ or W₁H₁ --- 2 possibilities so

|A₁| = 2 × 18!

P(A₁) = 2 × 18! / 19!

Round table

44

In general, the events in the inclusion-exclusion formula are indexed by some set C of couples.

E.g. if A₃A₄A₇A₉ then C = {3, 4, 7, 9}.

In how many ways can we arrange the couples so that those in C are adjacent?

Treating the couples in C as single unordered items, we get (19 – |C|)! arrangements.

For each such arrangement, we can order the C couples in 2^|C| possible ways.

2^|C|(19 – |C|)!

Round table

45

P(A₁ ∪ A₂ ∪…∪A₁₀)

value

#terms

2 × 18! / 19!

10

×

so P(N) = 1 – 0.6605… = 0.3395…

Problem for you to solve

46

You have 8 different chopstick pairs and you randomly give them to 8 guests.

What is the probability that no guest gets a matching pair?