Why is this approach on variant of birthday problem wrong?

Question

$n$ people are attending a party. Each has an equal probab of being born on any day during the year, independently of everyone else. Ignore leap years (i.e., nobody is born on February 29). What is the probab that each person has a distinct birthday? Assume $n\leq365$

Solution that is given by a Lecturer in probabilities. I am not sure why, but I have seen different solutions. Any ideas on why it is wrong?

The probability of the first person is $\frac{1}{365}$. The probability of the second person having a birthday on a day different than the first is $\frac{1}{364}$. The probability of the 3rd person having a birthday on a day different from the above two is $\frac{1}{363}$.

And so on.

So the probability of the n people is $Pn= \frac{1}{365} * \frac{1}{364} * \frac{1}{363} *... *\frac{1}{365-(n+1)}$.

My opinion is that the Pn only is the probability for specific n days in the year. But we want for any combination of n days in the year. So can we multiply $Pn$ by 365 choose n and get the result ?

As far as I know the result is : $Qn= \frac{365 * 364 * 363 *... (365- (n+1)) } { 365^n}$. It seems that the result cannot be yielded by multiplying $Pn$ by (365 choose n). Any ideas on how from $Pn$ I can arrive at $Qn $?

Answer 1

"The probability of the second person having a birthday on a day different than the first is 1/364."

Is it? Regarding the rest of your question, you should consider permutations not combinations.

Answer 2

"The probability of the second person having a birthday on a day different than the first is 1/364."

This is false. Consider the case where the first two people shared the same birthday.

You may also note that $Q(n) = \frac{1}{P(n)*365^n}$ if you wish to deduce $Q(n)$ from $P(n)$.

Answer 3

Something is very, very, very wrong here. The probability of the second person have a birthday on a day different than the first is 364/365 = 1 - 1/365. That lecturer needs to learn just a little bit to use intuition.

The lecturer suggests the probability that three random people have their birthdays on different days is (1/365) * (1/364) * (1/363). That's one in 48 million, much less likely than winning the lottery. I'll bet him $1,000, even money, that three random people have different birthdays, until he runs out of money.

It seems he is calculating the following probability: I guess the birthday of the first person. 1/365 that I get it right. Then I ask the next person if they have the same birthday until I find someone with a different birthday than the first person, and guess that second person's birthday. 1/364 that I get it right again. I find a third person with a birthday different from those two and guess their birthday. 1/363 that I get it right and so on.

(The quoted $Q_n$ seems to be the correct answer).

Answer 4

Something is wrong with $P_n$...

You seem to be trying to intuit the answer from the start, and an error has occurred somewhere along the way. It is much safer in probability to make smaller steps and arrive at the solution, rather than coming up with an intuitive answer.

Rather than directly thinking about the probability that no person shares the same birthday, it is safer to first formulate the underlying space, then find the probability we care about by describing it as a set in the space.

The following is going to seem over-formal, and for this level of problem it probably is. But all of the steps will be clear and it will show a safe way of thinking about this sort of question.

We could say that each person's birthday is a random variable $X$ which is an identity function on an event space. We will say $X:\Omega\rightarrow \Omega$ and: $$\Omega = \{\text{birthdays someone could have}\}= \{\text{Jan. 1},\dots, \text{Dec. 31}\} =\{\omega_1,\dots, \omega_{365}\}.$$

We also assume that if $\omega \in \Omega$ then $P(\omega)=\frac{1}{365}.$

Using this notation, $P(X=\omega)=\frac{1}{365}$ if $\omega \in \{\omega_1,\dots, \omega_{365}\}$.

Furthermore, if $A\subseteq \Omega,$ then $P(X\in A)=\frac{|A|}{\Omega}.$

Now say we have some sequence of people $X_1,\dots,X_n$ with independent birthdays. We can form the space of their birthdays as:

$$\Omega^n=\{\text{possible birthdays }n\text{ people can have}\}= \underset{n}{\underbrace{\Omega \times \dots \times \Omega}}.$$

If $\omega_1,\dots,\omega_n \in \Omega$, by independence:

$$P((X_1,\dots,X_n)=(\omega_1,\dots,\omega_n)) = \underset{n}{\underbrace{\frac{1}{365}\cdot \dots \cdot \frac{1}{365}}}=\frac{1}{365^n}.$$

So then if $A\subseteq \Omega^n$:

$$P((X_1,\dots,X_n)\in A)=\frac{|A|}{365^n}$$

Now we can formulate our original question in terms of these random variables: $$P(\{\text{No one shares the same birthday}\})=P(X_1\neq X_2\neq X_3\neq \dots \neq X_n)$$

From this we can write the probability we care about in terms of a set $S$ in $\Omega^n$:

$$S=\{(\omega_1,\dots,\omega_n):\text{every }\omega_i\text{ is distinct}\}$$

And now to find the probability we care about we just have to find the size of that set. If you think about it, you will see that the size of the set is 'the number of ways we can choose $n$ different things from a set of 365 distinct objects when order matters.'

The first one we can choose any of the $365$, the next one we can choose anything except the first one we chose, i.e. $364$ and so on, so we have:

$$|S|=\underset{n}{\underbrace{365\cdot \dots \cdot (365-n+1)}}=\frac{365!}{(365-n)!}$$

Finally, we have $P(S)=|S|/365^n=\frac{\frac{365!}{(365-n)!}}{365^n}.$