1Classical probability
IA Probability
1.2 Counting
To find probabilities, we often need to count things. For example, in our example
above, we had to count the number of elements in B
k
.
Example. A menu has 6 starters, 7 mains and 6 desserts. How many possible
meals combinations are there? Clearly 6 × 7 × 6 = 252.
Here we are using the fundamental rule of counting:
Theorem (Fundamental rule of counting). Suppose we have to make
r
multiple
choices in sequence. There are
m
1
possibilities for the first choice,
m
2
possibilities
for the second etc. Then the total number of choices is m
1
× m
2
× ···m
r
.
Example. How many ways can 1
,
2
, ··· , n
be ordered? The first choice has
n
possibilities, the second has
n−
1 possibilities etc. So there are
n×
(
n−
1)
×···×
1 =
n!.
Sampling with or without replacement
Suppose we have to pick
n
items from a total of
x
items. We can model this as
follows: Let
N
=
{
1
,
2
, ··· , n}
be the list. Let
X
=
{
1
,
2
, ··· , x}
be the items.
Then each way of picking the items is a function
f
:
N → X
with
f
(
i
) = item at
the ith position.
Definition (Sampling with replacement). When we sample with replacement,
after choosing at item, it is put back and can be chosen again. Then any sampling
function f satisfies sampling with replacement.
Definition (Sampling without replacement). When we sample without replace-
ment, after choosing an item, we kill it with fire and cannot choose it again.
Then f must be an injective function, and clearly we must have x ≥ n.
We can also have sampling with replacement, but we require each item to be
chosen at least once. In this case, f must be surjective.
Example. Suppose
N
=
{a, b, c}
and
X
=
{p, q, r, s}
. How many injective
functions are there N → X?
When we choose
f
(
a
), we have 4 options. When we choose
f
(
b
), we have
3 left. When we choose
f
(
c
), we have 2 choices left. So there are 24 possible
choices.
Example. I have
n
keys in my pocket. We select one at random once and try
to unlock. What is the possibility that I succeed at the rth trial?
Suppose we do it with replacement. We have to fail the first
r −
1 trials and
succeed in the rth. So the probability is
(n − 1)(n − 1) ···(n − 1)(1)
n
r
=
(n − 1)
r−1
n
r
.
Now suppose we are smarter and try without replacement. Then the probability
is
(n − 1)(n − 2) ···(n − r + 1)(1)
n(n − 1) ···(n − r + 1)
=
1
n
.
Example (Birthday problem). How many people are needed in a room for there
to be a probability that two people have the same birthday to be at least a half?
Suppose
f
(
r
) is the probability that, in a room of
r
people, there is a birthday
match.
We solve this by finding the probability of no match, 1
− f
(
r
). The total
number of possibilities of birthday combinations is 365
r
. For nobody to have
the same birthday, the first person can have any birthday. The second has 364
else to choose, etc. So
P(no match) =
365 · 364 · 363 ···(366 − r)
365 · 365 · 365 ···365
.
If we calculate this with a computer, we find that
f
(22) = 0
.
475695 and
f
(23) =
0.507297.
While this might sound odd since 23 is small, this is because we are thinking
about the wrong thing. The probability of match is related more to the number of
pairs of people, not the number of people. With 23 people, we have 23
×
22
/
2 =
253 pairs, which is quite large compared to 365.
Sampling with or without regard to ordering
There are cases where we don’t care about, say list positions. For example, if we
pick two representatives from a class, the order of picking them doesn’t matter.
In terms of the function
f
:
N → X
, after mapping to
f
(1)
, f
(2)
, ··· , f
(
n
),
we can
– Leave the list alone
–
Sort the list ascending. i.e. we might get (2
,
5
,
4) and (4
,
2
,
5). If we don’t
care about list positions, these are just equivalent to (2, 4, 5).
–
Re-number each item by the number of the draw on which it was first seen.
For example, we can rename (2
,
5
,
2) and (5
,
4
,
5) both as (1
,
2
,
1). This
happens if the labelling of items doesn’t matter.
– Both of above. So we can rename (2, 5, 2) and (8, 5, 5) both as (1, 1, 2).
Total number of cases
Combining these four possibilities with whether we have replacement, no replace-
ment, or “everything has to be chosen at least once”, we have 12 possible cases
of counting. The most important ones are:
– Replacement + with ordering: the number of ways is x
n
.
–
Without replacement + with ordering: the number of ways is
x
(n)
=
x
n
=
x(x − 1) ···(x − n + 1).
–
Without replacement + without order: we only care which items get
selected. The number of ways is
x
n
= C
x
n
= x
(n)
/n!.
–
Replacement + without ordering: we only care how many times the item
got chosen. This is equivalent to partitioning
n
into
n
1
+
n
2
+
···
+
n
k
.
Say n = 6 and k = 3. We can write a particular partition as
∗∗ | ∗ | ∗ ∗ ∗
So we have
n
+
k −
1 symbols and
k −
1 of them are bars. So the number
of ways is
n+k−1
k−1
.
Multinomial coefficient
Suppose that we have to pick n items, and each item can either be an apple or
an orange. The number of ways of picking such that
k
apples are chosen is, by
definition,
n
k
.
In general, suppose we have to fill successive positions in a list of length
n
, with replacement, from a set of
k
items. The number of ways of doing so
such that item
i
is picked
n
i
times is defined to be the multinomial coefficient
n
n
1
,n
2
,···,n
k
.
Definition (Multinomial coefficient). A multinomial coefficient is
n
n
1
, n
2
, ··· , n
k
=
n
n
1
n − n
1
n
2
···
n − n
1
··· −n
k−1
n
k
=
n!
n
1
!n
2
! ···n
k
!
.
It is the number of ways to distribute
n
items into
k
positions, in which the
i
th
position has n
i
items.
Example. We know that
(x + y)
n
= x
n
+
n
1
x
n−1
y + ··· + y
n
.
If we have a trinomial, then
(x + y + z)
n
=
X
n
1
,n
2
,n
3
n
n
1
, n
2
, n
3
x
n
1
y
n
2
z
n
3
.
Example. How many ways can we deal 52 cards to 4 player, each with a hand
of 13? The total number of ways is
52
13, 13, 13, 13
=
52!
(13!)
4
= 53644737765488792839237440000 = 5.36 × 10
28
.
While computers are still capable of calculating that, what if we tried more
power cards? Suppose each person has n cards. Then the number of ways is
(4n)!
(n!)
4
,
which is huge. We can use Stirling’s Formula to approximate it: