Question about permutations and subsets

Question

Consider $n$ people who are attending a party. We assume that every person has an equal probability of being born on any day during the year, independently of everyone else, and ignore the additional complication presented by leap years (i.e., nobody is born on February $29$). What is the probability that each person has a distinct birthday?

The solution to this problem is $\frac{365 \cdot 364 \cdot \ldots \cdot (365 - n + 1)}{365^n}$.

I was wondering why the sample space contains birthday lists like $b_1b_2\ldots b_n$. Why don't we choose $n$ places out of $365$ instead? I am not sure but to me it seems like the order shouldn't matter here.

Answer 1

Birthday Problem. This is the famous 'birthday problem' or, because some people find the answer surprising 'birthday paradox'. There are lots of links to it on this site and elsewhere on the Internet, so I will get right to the point, and just try to answer your specific question.

Often when sampling is 'with replacement' it is more convenient to look at ordered outcomes. The birthday problem clearly involves sampling with replacement because it is possible for a birthday to be selected more than once.

There are many problems that can be answered with either ordered or unordered samples. The important thing is that if you are using ordered samples in the denominator (to count outcomes in the whole sample space), you must also use ordered samples in the the numerator (to count 'favorable' outcomes). In the birthday problem it is especially easy to use a sample space with $365^n$ ordered samples in the denominator, so it is natural to start with that and, accordingly, to use ordered samples in the numerator.

Urn Problem. Here is a problem in which you can use either ordered or unordered outcomes: I have an urn containing 5 balls, 3 red and 2 green. I withdraw two balls without replacement. What is the probability I get two balls of the same color:

Ordered (permutations).

Count all ordered outcomes in denominator: $5(4) = 20.$

Numerator. Ways with two red: $3(2) = 6.$ Ways with two green: 2(1) = 2.

Answer. $(6+2)/20 = 2/5$

Unordered (combinations).

Denominator: ${5 \choose 2} = 10.$

Numerator: Both red: ${3 \choose 2}{2 \choose 0} = 3.$ Both green: ${2 \choose 2}{3 \choose 0} = 1.$

Answer: $(3 + 1)/10 = 2/5.$

However, suppose my task to find the probability that I choose a red ball and then a green ball. This new problem involves order, and I have no choice but to use ordered outcomes throughout: $6/20 = 3/10.$

Answer 2

Problem with solution based on combination, is that it cannot "see" orderings. Consider very simple example: two coin flips. What is probability of event $A_1$, that two flips will be different? One reasoning is with orderings: first and second flip. There are $\#\Omega_1=2^2$ possibilities.First flip can be arbitrary - hence 2 options, but the second has to be opposed. Thus $\#A_1=2*1$, and the probability $P(A_1) = \frac{\#A_1}{\#\Omega_1}=\frac{2*1}{2^2}$. Now second approach: we don't worry about orderings, there are only three possibilities: two heads, two tails, or head and tail - $\#\Omega_2=3$ and $\#A_2=1$ ($A$ is elementary event). You could rather guess probability, but lets apply equations: $P(A_2)=\frac{\binom{2}{2}}{\binom{2+2-1}{1}}=\frac{1}{3}$. Why there are different results? Because in first approach event "different flips" has probability $\frac{1}{2}$ - bigger than for example "two heads", $\frac{1}{4}$. In second approach all three events have the same probability, because they are elementary events.

Now all to be done is to see that above example and your problem are in principle the same. To help you understand similarity: consider $n=3$ in birth problem. Take "ordering approach", $\#\Omega=365^3$. Let event $A$ means "every person has distinct birthday: 1st, 2nd and 3rd Jan", and $B$ - "two persons have 1st Feb as birthday, and one person has birthday at 2nd Feb". We can distinct (permute) those persons in our approach, so $P(A)=\frac{3!}{365^3}=\frac{6}{365^3}$ and in $B$ it is sufficient to decite which person has birthday at 2nd Feb $P(B)=\frac{\binom{3}{1}}{365^3}=\frac{3}{365^3}$. Ok, so in this approach event (set) $A$ has six elementary events (elements) and $B$ has three. Now final part: in second approach where no person is distinguished, there is only one possibility to have three persons' birthdays at three different, fixed days; $\#A'=1$, but $\#B'=1$ as well! That is why $P(A')=\frac{1}{\binom{365+3-1}{3}}\neq P(A)=\frac{3!}{365^3}$.

In practice you have to use intuition and experience from similar exercises to decide about wheter to use ordering, but thumb rule is: if you have regular combinations, both approaches should give correct result, but using combination with repetition $\binom{n+k-1}{k}$ is subtle and can give different results.

Note: By $elementary\ events$ I mean elements, or singletons of probability space, $event$ is always a subset. I assume, that all elementary events have the same probability (the same mass).

Answer 3

... it seems like the order shouldn't matter here

Quite right. The birthdays are really assigned independently at random to each of the people. Because the order doesn't matter, and all are equivalent, we can choose to regard the birthdays as being assigned in a sequence, any sequence. This enables us to work out the chances easily.