4 of 64

Quiz

Probability/Ch3

A box contains 3 cards. One is black on both sides. One is red on both sides. One is black on one side and red on the other.

You draw a random card and see a black side. What are the chances the other side is red?

A: 1/4

B: 1/3

C: 1/2

5 of 64

Solution

Probability/Ch3

S = { F1, B1, F2, B2, F3, B3 }

The event you see a black side is SB = { F1, B1, F3 }

The event the other side is red is OR = { F2, B2, F3 }

P(OR | SB) =

equally likely outcomes

P(OR SB)

P(SB)

1/|S|

3/|S|

= 1/3

6 of 64

Probability/Ch3

7 of 64

Probability/Ch3

8 of 64

Probability/Ch3

9 of 64

Probability/Ch3

10 of 64

Probability/Ch3

11 of 64

Probability/Ch3

Law of total probability

12 of 64

Probability/Ch3

Bayes’s Rule

Independent Event

13 of 64

Probability/Ch3

14 of 64

Probability/Ch3

Problem of the point

1623 – 1662

15 of 64

Probability/Ch3

1601 –1665

16 of 64

Probability/Ch3

Color a complete graph

17 of 64

Probability/Ch3

18 of 64

Probability/Ch3

Then what ?

19 of 64

Probability/Ch3

20 of 64

Probability/Ch3

21 of 64

Probability/Ch3

Catalan number (counting T-path)

If we walk in a lattice and in each step we can choose “going right” or “going up” one unit. How many paths are there from (0,0) to (n,n), without crossing the diagonal line ?

(0,0)

(n,n)

Swap and push

cross then swap

22 of 64

Probability/Ch3

Bertrand’s ballot problem (counting NT-path)

Suppose in an election candidate A receives n votes and B receives m where n>m.

What is the probability that A always wins B during the counting process ?

Cycle Lemma!

(0,0)

(m,m)

(n,m)

(n,0)

(0,m)

touch then swap

23 of 64

Probability/Ch3

Cycle lemma for the Catalan number

Note that the number of T-path from (0,0) to (n,n) equals that of NT-path from (0,0) to (n+1,n). Therefore by the cycle lemma, Catalan number is

Q. How many NT-paths and T-paths from (0,0) to (km+p,m)

for positive integers m,k and p? (check wiki for details)

(0, m)

(0, 0)

(km, 0)

(km+p, 0)

(km+p, m)

24 of 64

3. Conditional probability�part two

25 of 64

Cause and effect

Probability/Ch3

effect:

cause:

C₁

C₂

C₃

26 of 64

Bayes’ rule

Probability/Ch3

P(E|C) P(C)

P(E)

P(E|C) P(C)

P(E|C) P(C) + P(E|C^c) P(C^c)

More generally, if C₁,…, C_n partition S then

P(C|E) =

P(C_i|E) =

P(E|C_i) P(C_i)

P(E|C₁) P(C₁) + … + P(E|C_n) P(C_n)

27 of 64

Cause and effect

Probability/Ch3

cause:

C₁

C₂

C₃

effect:

P(C_i|B) =

P(B|C_i) P(C_i)

P(B|C₁) P(C₁) + P(B|C₂) P(C₂) + P(B|C₃) P(C₃)

28 of 64

Medical tests

Probability/Ch3

If you are sick (S), a blood test comes out positive (P) 95% of the time.

If you are not sick, the test is positive 1% of the time.

Suppose 0.5% people in Hong Kong are sick.

You take the test and come out positive. What are the chances that you are sick?

P(P|S) P(S)

P(P|S) P(S) + P(P|S^c) P(S^c)

P(S|P) =

95% 0.5%

1% 99.5%

≈ 32.3%

29 of 64

Computer science vs. nursing

Probability/Ch3

Two classes take place in Lady Shaw Building.

One is a computer science class with 100 students, out of which 20% are girls.

The other is a nursing class with 10 students, out of which 80% are girls.

A girl walks out. What are the chances that she is from the computer science class?

30 of 64

Two effects

Probability/Ch3

Cup one has 9 blue balls and 1 red ball.

Cup two has 9 red balls and 1 blue ball.

I choose a cup at random and draw a ball. It is blue.

I draw another ball from the same cup (without replacement). What is the probability it is blue?

31 of 64

Russian roulette

Probability/Ch3

Alice

Bob

BANG

Alice and Bob take turns spinning the 6 hole cylinder and shooting at each other.

What is the probability that Alice wins (Bob dies)?

32 of 64

Russian roulette

Probability/Ch3

S = { H, MH, MMH, MMMH, MMMH, …}

E.g. MMH: Alice misses, then Bob misses, then Alice hits

A = “Alice wins” = { H, MMH, MMMMH, …}

Probability model

outcomes are not equally likely!

33 of 64

Russian roulette

Probability/Ch3

P(A)

outcome H MH MMH MMMH MMMH

probability

1/6

5/6 ∙ 1/6

(5/6)² ∙ 1/6

(5/6)³ ∙ 1/6

(5/6)⁴ ∙ 1/6

= 1/6 + (5/6)² ∙ 1/6 + (5/6)⁴ ∙ 1/6 + …

= 1/6 ∙ (1 + (5/6)² + (5/6)⁴ + …)

= 1/6 ∙ 1/(1 – (5/6)²)

= 6/11

34 of 64

Russian roulette

Probability/Ch3

Solution using conditional probabilities:

P(A) = P(A|W₁) P(W₁) + P(A|W₁^c) P(W₁^c)

A = “Alice wins” = { H, MMH, MMMMH, …}

W₁ = “Alice wins in first round” = { H }

A^c = “Bob wins” = { MH, MMMH, MMMMMH, …}

5/6

1/6

P(A^c)

P(A) = 1 ∙ 1/6 + (1 – P(A)) ∙ 5/6

11/6 P(A) = 1

so P(A) = 6/11

35 of 64

Infinite sample spaces

Probability/Ch3

Axioms of probability:

1. for every E, 0 ≤ P(E) ≤ 1

2. P(S) = 1

3. If EF = ∅ then

P(E∪F) = P(E) + P(F)

3. If E₁, E₂, … are pairwise disjoint:

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

36 of 64

Problem for you to solve

Probability/Ch3

Charlie tosses a pair of dice. Alice wins if the sum is 7. Bob wins if the sum is 8.

Charlie keeps tossing until one of them wins.

What is the probability that Alice wins?

37 of 64

Hats again

Probability/Ch3

The hats of n men are exchanged at random. What is the probability that no man gets back his hat?

Solution using conditional probabilities:

N = “No man gets back his hat”

H₁ = “1 gets back his own hat”

P(N) = P(N|H₁) P(H₁) + P(N|H₁^c) P(H₁^c)

(n-1)/n

1/n

38 of 64

Hats again

Probability/Ch3

N = “No man gets back his hat”

H₁ = “1 gets back his own hat”

S₁ = “1 exchanges hats with another man”

P(N) = P(N|H₁^c)

n – 1

P(N|H₁^c) = P(NS₁|H₁^c) + P(NS₁^c|H₁^c)

= P(S₁|H₁^c) P(N|S₁H₁^c) + P(NS₁^c|H₁^c)

1/(n-1)

p_n_-2

let p_n = P(N)

p_n_-1

p_n =

p_n = p_n_-1 + p_n_-2

n – 1

39 of 64

Hats again

Probability/Ch3

N = “No man gets back his hat”

p_n = P(N)

p_n = p_n_-1 + p_n_-2

n – 1

p₁ = 0

p_n – p_n_-1 = – (p_n_-1 – p_n_-2)

p₃ – p₂ = – (p₂ – p₁)

= –

p₃ = –

p₄ – p₃ = – (p₃ – p₂)

p₄ = – +

p₂ =

40 of 64

Summary of conditional probability

Probability/Ch3

Conditional probabilities are used:

to estimate the probability of a cause when we observe an effect

Conditioning on the right event can simplify the description of the sample space

When there are causes and effects

To calculate ordinary probabilities

41 of 64

Independence of two events

Probability/Ch3

Let E₁ be “first coin comes up H”

E₂ be “second coin comes up H”

Then P(E₂| E₁) = P(E₂)

Events A and B are independent if

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

P(E₂E₁) = P(E₂)P(E₁)

42 of 64

Examples of (in)dependence

Probability/Ch3

Let E₁ be “first die is a 4”

S₆ be “sum of dice is a 6”

S₇ be “sum of dice is a 7”

P(E₁) =

P(S₆) =

P(E₁S₆) =

E₁, S₆are dependent

P(S₇) =

P(E₁S₇) =

E₁, S₇are independent

P(S₆S₇) =

S₆, S₇are dependent

1/6

5/36

1/36

1/6

1/36

43 of 64

Algebra of independent events

Probability/Ch3

If A and B are independent, then A and B^c are also independent.

Proof: Assume A and B are independent.

P(AB^c)

= P(A) – P(AB)

= P(A) – P(A)P(B)

= P(A)P(B^c)

so B^c and A are independent.

Taking complements preserves independence.

44 of 64

Independence of three events

Probability/Ch3

Events A, B, and C are independent if

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

P(BC) = P(B) P(C)

P(AC) = P(B) P(C)

and P(ABC) = P(A) P(B) P(C).

This is important!

45 of 64

(In)dependence of three events

Probability/Ch3

Let E₁ be “first die is a 4”

E₂ be “second die is a 3”

S₇ be “sum of dice is a 7”

P(E₁E₂) = P(E₁) P(E₂)

P(E₁S₇) = P(E₁) P(S₇)

P(E₂S₇) = P(E₂) P(S₇)

P(E₁E₂S₇) = P(E₁) P(E₂) P(S₇)

✔

✗

1/6

1/36

E₁

E₂

S₇

1/6

1/36

46 of 64

Independence of many events

Probability/Ch3

Events A₁, A₂, … are independent if for every subset A_i₁, …, A_ir of the events

P(A_i₁…A_ir) = P(A_i₁) … P(A_ir)

Independence is preserved if we replace some event(s) by their complements, intersections, unions

Algebra of independent events

47 of 64

The proof can also be done by induction.

Probability/Ch3

48 of 64

Playoffs

Probability/Ch3

Alice wins 60% of her ping pong matches against Bob. They meet for a 3 match playoff. What are the chances that Alice will win the playoff?

Probability model

Let W_i be the event Alice wins match i

We assume P(W₁) = P(W₂) = P(W₃) = 0.6

We also assume W₁, W₂, W₃ are independent

49 of 64

Playoffs

Probability/Ch3

Probability model

To convince ourselves this is a probability model, let’s redo it as in Lecture 2:

S = { AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB }

the probability of AAA is P(W₁W₂W₃) = 0.6³

AAB

P(W₁W₂W₃^c) = 0.6²∙ 0.4

ABA

P(W₁W₂^cW₃) = 0.6²∙ 0.4

BBB

P(W₁^cW₂^cW₃^c) = 0.4³

…

The probabilities add up to one.

50 of 64

Playoffs

Probability/Ch3

A = { AAA, AAB, ABA, BAA }

For Alice to win the tournament, she must win at least 2 out of 3 games. The corresponding event is

0.6³

0.6²∙ 0.4 each

P(A) = 0.6³ + 3 ∙ 0.6²∙ 0.4 = 0.648.

Alice wins a p fraction of her ping pong games against Bob. What are the chances Alice beats Bob in an n match tournament (n is odd)?

General playoff

51 of 64

Playoffs

Probability/Ch3

Solution

Probability model similar as before.

Let A be the event “Alice wins playoff”

A_k be the event “Alice wins exactly k matches”

P(A_k) = C(n, k) p^k (1 – p)ⁿ^-^k

A = A₍_n_+1)/2∪…∪A_n

P(A) = P(A₍_n_+1)/2) + … + P(A_n) (they are disjoint)

number of arrangements of k As, n – k Bs

probability of each such arrangement

52 of 64

Playoffs

Probability/Ch3

P(A) = ∑ _k_{= (}_n_+1)/2

ⁿ

C(n, k) p^k (1 – p)ⁿ^-^k

p = 0.6

p = 0.7

The probability that Alice wins an n game tournament

53 of 64

Problem for you

Probability/Ch3

The Lakers and the Celtics meet for a 7-game playoff. They play until one team wins four games.

Suppose the Lakers win 60% of the time. What is the probability that all 7 games are played?

54 of 64

Suppose Pk is the probability that k games are played. We have

Probability/Ch3

Can you verify

55 of 64

Gambler’s ruin

Probability/Ch3

You have $100. You keep betting $1 on red at roulette.

You stop when you win $200, �or when you run out of money.

What is the probability you win $200?

56 of 64

Gambler’s ruin

Probability/Ch3

Probability model

S = all infinite sequences of Reds and Others

Let R_i be the event of red in the ith round � (there is an R in position i)

Probabilities:

P(R₁) = P(R₂) = … = 18/37

R₁, R₂, … are independent

call this p

57 of 64

Gambler’s ruin

Probability/Ch3

Let W be the event you win $200 and w_n = P(W).

You have $100. You stop when you win $200.

= P(W|R₁) P(R₁) + P(W|R₁^c) P(R₁^c)

w_n = P(W)

1-p

w_n₊₁

w_n_-1

w_n = (1-p)w_n_-1 + pw_n₊₁

w₀ = 0

w₂₀₀ = 1.

58 of 64

Gambler’s ruin

Probability/Ch3

p(w_n₊₁ – w_n) = (1-p)(w_n – w_n_-1)

w_n = (1-p)w_n_-1 + pw_n₊₁

w₀ = 0

w₂₀₀ = 1.

w_n₊₁ – w_n = λ (w_n – w_n_-1)

let λ = (1-p)/p = 19/18

= λ² (w_n_-1 – w_n_-2)

= … = λⁿ (w₁ – w₀)

w_n₊₁ = w_n+ λⁿw₁

= w_n_-1+ λⁿ^-1w₁+λⁿw₁

= … = w₁+ λw₁+ … + λⁿw₁

59 of 64

Gambler’s ruin

Probability/Ch3

w_n = (1-p)w_n_-1 + pw_n₊₁

w₀ = 0

w₂₀₀ = 1.

λ = (1-p)/p = 19/18

w_n₊₁ = w₁+ … + λⁿw₁

= (λⁿ⁺¹ – 1)/(λ – 1)w₁

w₂₀₀ = (λ²⁰⁰ – 1)/(λ – 1)w₁

w_n₊₁ =

λⁿ⁺¹ – 1

λ²⁰⁰ – 1

You have $100.

You stop when you win

$200 or run out.

The probability you win is

w₁₀₀ ≈ 0.0045

60 of 64

The general gambler’s ruin problem

Probability/Ch3

Two people play a game with each other. The loser pays one dollar to the winner at the end of the game. Initially they have r₁ and r₂ dollars and the winning rates are p and 1-p respectively. They continue to play until one of them goes bankrupt. Find the probability that the guy with r₁ dollars initially loses all the money at the end.

Let P_r₁ be the probability then

1 of 64

2 of 64

3 of 64

4 of 64

5 of 64

6 of 64

7 of 64

8 of 64

9 of 64

10 of 64

11 of 64

12 of 64

13 of 64

14 of 64

15 of 64

16 of 64

17 of 64

18 of 64

19 of 64

20 of 64

21 of 64

22 of 64

23 of 64

24 of 64

25 of 64

26 of 64

27 of 64

28 of 64

29 of 64

30 of 64

31 of 64

32 of 64

33 of 64

34 of 64

35 of 64

36 of 64

37 of 64

38 of 64

39 of 64

40 of 64

41 of 64

42 of 64

43 of 64

44 of 64

45 of 64

46 of 64

47 of 64

48 of 64

49 of 64

50 of 64

51 of 64

52 of 64

53 of 64

54 of 64

55 of 64

56 of 64

57 of 64

58 of 64

59 of 64

60 of 64

61 of 64

62 of 64

63 of 64

64 of 64