Study Guides (400,000)
CA (150,000)
UTSC (10,000)
Final

CSCA67H3 Lecture Notes - Lecture 5: Birthday Problem, Sample Space, Brady HaranExam


Department
Computer Science
Course Code
CSCA67H3
Professor
Anna Bretscher
Study Guide
Final

This preview shows pages 1-2. to view the full 7 pages of the document.
CSCA67 Tutorial, Week 5
Oct. 6th-Oct. 10th, 2014
Compiled by G. Singh Cadieux
Adapted from
A. Bretscher, CSCA67 Week 5 Lecture Notes,
Interactive Mathematics: Singapore TOTO &
Interactive Mathematics: Probability and Poker
1Review of last week’s lecture
Introduction to probability: The Birthday Problem
Q: What is the probability that, in a group of npeople, at least 2 have the same birthday?
Let us represent the days of the year by the integers 1, 2, . . . , 365. Then we choose our sample space Sto
be {all possible combinations of nbirthdays}. That is, we include all possible combinations of ndays, with
repetition - up to nrepetitions of the same day (when all nbirthdays fall on the same day).
For example, if n= 3, we include:
all the single days of the year (eg. (1, 1, 1), (2, 2, 2), (3, 3, 3), . . . ), in the case that all 3 birthdays
fall on the same day,
all combinations of 2 different days of the year (eg. (1, 1, 2), (1, 1, 3), (1, 1, 4), . . . ), in the case that
2 of the birthdays fall on the same day, and
all combinations of 3 different days of the year (eg. (1, 2, 3), (1, 2, 4), (1, 2, 5), . . . ), in the case that
all 3 birthdays fall on different days
Suppose that all birthdays (and combinations of birthdays) are equally likely. Then, by the classical definition
of probability,
P({at least 2 people share a birthday}) = |{at least 2. . . }|
|S|
We know from counting principles that
|S|= # of ways to select the first birthday ×# of ways to select the second birthday
×. . . ×# of ways to select the nth birthday
= 365 ×365 ×. . . ×365
= 365n
and that
|{at least 2. . . }| = # of arrangements of nbirthdays where 2 people share a birthday
+ # of arrangements of nbirthdays where 3 people share a birthday
+. . . + # of arrangements of nbirthdays where npeople share a birthday
1

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

So
P({at least 2 people share a birthday}) = |{2 people share a birthday}| +. . . +|{npeople share a birthday}|
365n
Note that this counting method counts ordered n-tuples: for example, where n= 3, we consider (1, 1, 2)
and (1, 2, 1) to be different combinations of birthdays.
If we were to instead consider unordered n-tuples, we could not use the classical definition of probability,
since not all outcomes would be equally likely. For example, where n= 3, the unordered combination (1, 1,
2) is more likely than the unordered combination (1, 2, 3), since there are more ways in which the former
can occur.
However, this seems very laborious to compute, particularly if nis large.
We can instead use the complement rule to determine that
P({at least 2 people share a birthday}) = 1 P({at least 2 people share a birthday})
= 1 P({no shared birthdays})
= 1 # of ways to select nunshared birthdays
365n
= 1 365 ×364 ×. . . ×(365 n+ 1)
365n
Notice that, if n > 365, the above calculation produces
P({at least 2. . . }) = 1 365 ×(365 1) ×. . . ×(365 364) ×(365 365) ×. . . ×(365 n+ 1)
365n
= 1 365 ×. . . ×0×. . . ×(365 n+ 1)
365n
= 1 0
365n
= 1 0 = 1
Why does this make sense?
By the pigeonhole principle, if we have nobjects to place in fewer than npigeonholes, at least 1 pigeonhole
will contain multiple objects. In this case, if there are more than 365 birthdays to distribute over 365 days,
at least 2 birthdays will fall on the same day. Thus, the probability of at least 2 people sharing a birthday
is 1, or absolutely certain.
2Probability problems
2.1 Singapore TOTO
In the Singapore lottery game of TOTO, 6 (distinct) winning numbers plus one “additional” winning number
are drawn at random from the numbers 1 to 45. In the ordinary game, players choose 6 numbers/ticket in
the hope of matching some or all of the winning numbers and becoming instant millionaires.
Prizes
Group Prize Amount Winning Numbers Matched
1 33% of prize pool 6
2 13% of prize pool 5 + additional number
3 13% of prize pool 5
4 13% of prize pool 4 + additional number
5 $30 per winning combination 4
6 $20 per winning combination 3 + additional number
2
You're Reading a Preview

Unlock to view full version