Today:
Probability
ECS 20 — Lecture 19 — Fall 2013 —3 Dec 2013
Phil Rogaway
Announcements:
– Please work out the old final for Thursday
– Final’s week OH are online. Unfortunately, I am out of town. I will check the chat room as
often as I can.
– Final: you may not leave during the last 30 mins.
Poker examples and first use of probability
Let’s introduce probability informally
straight flush = five consecutive cards: A2345, 23456, 34567, …, 89AJQ, 9AJQK, AJQKA in any suit. So 40 possible.
royal flush = AJQKA of one suit. So 4 possible
four of a kind = four cards of one value, eg., four 9’s
full house = 3 cards of one value, 2 cards of another value. Eg, three 10’s and two 4’s. flush = five cards of a single suit
three of a kind = three cards of one value, a fourth card of a different value,
and a fifth card of a third value
two pairs = two cards of one value, two more cards of a second value, and the remaining card of a third value
one pair = two cards of one value, but not classified above
1
1. 2.
How many poker hands are there? Answer: C(52,5)=2,598,960
How many poker hands are full houses?
Answer: A full house can be partially identified by a pair, like (J,8), where the first component of the pair is what you have three of, the second component is what you have two of. So there are P(13,2)=13*12 such pairs. For each there are C(4,3)=4 ways to choose the first component, and C(4,2)=6 ways to choose the second component. So all together there are
13*12*4*6=3,744 possible full houses.
The probability of being dealt a full house is therefore
3,744/2,598,960 .001441 P[FullHouse] .001441
The probability of an event is a real number between 0 and 1 (inclusive). If asked what’s the probability of something, don’t answer with a “percent”, and don’t answer with something outside of [0,1]. When we give something in “percent’s”, we are giving a probability multiplied by 100.
3. How many poker hands are two pairs?
Answer: We can partially identify two pairs as in {J, 8}. Note that now the pair is now unordered. There are C(13,2) such sets. For each there are C(4,2) ways to choose the larger card and C(4,2) ways to choose the smaller card. There are now 52 8 remaining cards one can choose as the fifth card (to avoid a full house, there are 8 “forbidden” cards). So the total is
C(13,2)*C(4,2)*C(4,2)*44 = 123,552. The chance of being dealt two pairs is therefore
C(13,2)*C(4,2)*C(4,2)*44 / C(52,5) = 123,552/2,598,960 .047539 4.75% P[TwoPairs] .047539
Basic definitions / theory
Schaum’s, chapter 7.
Probability does not appear at all in Biggs.
2
Def:
x S
In general, whenever you hear probability make sure that you are clear what is the probability space is: what is the sample space and what is the probability measure on it.
An outcome is a point in S.
Def: Let (S, P) be a probability space.
An event is a subset of S.
Def: Let A be an event of probability space (S, P).
P(A) = P(a) (I’m used to using Pr, will probability slip) aA
The probability of event A. By convention, P()=0
Def: The uniform distribution is the one where P(a) = 1/|S| —ie, all points are equiprobable. Def: Events A and B are independent if P(A B) = P(A) P(B).
A (finite) probability space (S,P) is
a finite set S (the sample space) and
a function P: S [0,1] (the probability measure) such that that
P(x) = 1 (alternative notation: , , for x, P, S)
Def: A random variable is a function X: S R from the sample space to the reals. Def: E[X] = P(s) X(s) // expected value of X (“average value”)
sS
Def: if B then P(A|B) = P(A B) / P(B)
Propositions:
– P() = 0 // by definition
– P(S) = 1
– P(A) + P(Ac) = 1, or P(A) = 1 – P(Ac)
– If A and B are disjoint events (that is, disjoint sets) then P(A B) = P(A) + P(B)
– (“sum bound”)
P(A B) P(A) + P(B)
– In general,
P(A B) = P(A) + P(B) P(AB) // inclusion-exclusion principle
– If B1,B2 disjoint, nonempty events whose union is S then P(A) = P(A | B1) P(B1) + P(A | B2) P(B2)
– E(X+Y) = E(X) + E(Y) // expectation is linear.
Eg 1: Dice
The singular, the students assure me, is die. Like mice and mie. I guess.
3
You roll a fair die six times: S = {1,2,3,4,5,6}
P(1)=P(2)=…=P(6)=1/6
“you roll an even number” is an event.
Event is A = {2,4,6}. P(A) = 3 * (1/6) = 1/2.
Pair of dice.
S = {1,2,3,4,5,6} {1,2,3,4,5,6}o P((a,b)) = 1/36 for all (a,b) in S
Illustrate independence.
P(left die even and right die even) = P(left die even) P(right die even) = (1/2) (1/2) =1/4
Pair of dice, what’s the chance of rolling an “8”?
Event E = {(2,6),(3,5),(4,4),(5,3),(6,2)} P(E) = 5/36
Be careful: P(E) = |E|/|S| only if we are assuming the uniform distribution.
Pair of dice, what’s the chance of rolling an “8” if I tell you that both numbers came out even?
Method 1: Imagine the new probability space: (2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6)
*** **** *** So probability is 3/9 = 1/3
Method 2: A little more mechanically A = “rolled an 8”
B = “both die are even”
P(A | B) = P(AB)/P(B)
= (3/36) / (9/36) = 1/3
Eg 2. Back to the Poker examples
What’s the probability space?
Sample space has |S| = C(52,5)
We can regard the points of S as 5-elements subsets
of {2C,2D,2H,2S, 3C,3D,3H,3S,…, KC,KD,KH,KS, AC,AD,AH,AS} or {1, …,52} Probability measure is uniform: P(a) = 1/|S|.
Eg 3: Fair coin
Flip a fair coin 100 times. What is the probability space?
S = {0,1}100
P(s) = 2 100 for all s in S.
What is the chance of getting exactly 50 out of the 100 coin flips land heads?
P(50Heads) = C(100,50) / 2100 0.07959 // note “100 choose 50” to Google P(51Heads) = C(100,51) / 2100 0.07803
Eg 4: Biased coin
Now, what if the coin is biased?
Say that the coin lands heads with probability p= .51 and tails with probability 1p= .49. each flip independent of the rest.
You flip the unfair coin 100 times. The coin lands heads a fraction p=0.51 of the time:
4
S = {0,1}100 (same as before, but now)
P(x) = p#1(x) (1p) #0(x) where #1(x) = the number of 1-bits in the string x and
#0(x) = the number of 0-bits in the string x. What’s the Probability of 50 and 51 heads now?
P(50Heads) =C(100,50)(.51^50)(.49^50)0.07801 P(51Heads) = C(100,51)(.51^51)(0.49^49) 0.07906
Makes sense — 51 heads should now be the most likely number, and things should fall off from there. Before, 50 heads was the most likely outcome.
Eg 5: Birthday phenomenon
n=23 people gather in a room.
What’ the chance that some two have the same birthday? Assume nobody born 2/29, all other birthdays equiprobable. S = [1..365]23
P(SameBirthday) = 1 Pr(AllBirthdaysDifferent) 1 (11/365)(1365) … (122/365)
22
1 (11/i) 0.507
i=1
That’s as far as we got in lecture. See http://en.wikipedia.org/wiki/Birthday_problem#Calculating_the_probability if you didn’t follow.
5