4
$\begingroup$

The Birthday Problem: given $n$ people (typically $n<365$), what is the probability that some pair of them share a birthday (omitting Feb 29th, for simplicity)?

The solution: First, find the probability that all $n$ people have different birthdays. Here is where I am confused. The solutions I have seen all say this probability is: $$ \frac{_{365}P_n}{365^n} $$

Why isn't this $_{365}C_n$,instead?

$\endgroup$
1
  • 1
    $\begingroup$ How many ways are there of assigning $n$ of the 365 possible birthdays to $n$ people? $\endgroup$ – MJD Nov 13 '14 at 19:07
5
$\begingroup$

If you did combinations, you would basically choose the birthdays but not assign them to the $n$ people. However the denominator presumes the birthdays have been assigned (365 choices for Alice, 365 choices for Bob, etc.)

$\endgroup$
2
  • 2
    $\begingroup$ what if we will use also compinations ( with repetition ) for the denominator? $\endgroup$ – karhas Aug 25 '16 at 23:25
  • 1
    $\begingroup$ @karhas, I had exactly the same question, and I think that the comment of Ned (see below, the answer of, again, Ned) provides me the answer: the combinations compute the number of sets. But here the set are not equally likely. The set {1, 1, 1, ...} (same birthday for the n persons) is less common than the set {1, 2, 3, 4, 1, ...} (a set with differents birthdays for the n persons). So, in this problem, it is not fair to use the number of sets (or you need to weight all the sets). $\endgroup$ – AntoineP Feb 26 '20 at 10:08
1
$\begingroup$

The probability with $n$ people is, by considering the first, then the second, then the third, ..., $$\frac{365}{365}\times \frac{364}{365}\times \frac{363}{365}\times \cdots \times\frac{365-n+1}{365}.$$

Now simplify.

$\endgroup$
1
$\begingroup$

Regarding paw88789's response, it is mathematically correct, but omits the "why" of the question, which is why permutations should be used instead of combinations to determine the number of possibilities of the group's birthdays.

Combinations certainly give the number of possible birthday sets, which seems a reasonable way to solve the problem. However, the birthday problem is for a real group of people, and such groups allow for repetition of birthdays. Once repetition is allowed, the number of ways the group can have birthdays is 365^n, for an n-person group. Combinations with repetition are not calculated by nCr [C(n,r)], nor are they related to permutations by a factor of r!, as in nCr = nPr * r!. Although we could calculate the combinations with repetition, it still misses the correct number of possible ways for the group's set of birthdays because a group with a certain combination of birthdays can be put together in possibly more ways than one, and this affects the probability of the result. The basis for the probability of no repetition of birthdays is the number of possible ways for no repetition of birthdays divided by the number of total possible ways, 365^n, for birthdays.

Only permutation gives the correct number of possible ways a group can have birthdays without repetition.

$\endgroup$
0
1
$\begingroup$

You could, in principle, use combinations to do this problem, that is, take the people to be indistinguishable from each other. The difficulty is that the corresponding sample space consists of ordered partitions of $n$ into 365 non-negative pieces, and those partitions are NOT EQUALLY LIKELY (and are hard to count). So it will NOT be simply (size of event) / (size of sample space).

In general, situations that involve independent identical trials (like people's birthdays, rolling dice, flipping coins, drawing with replacement) are most easily modeled by ordered (i.e. distinguishable) trials, because it is easier to model the sample space with equally likely outcomes that way. For example, the question what is the probability of getting three different numbers when rolling three dice [which IS the birthday problem with 6,3 in place of 365,$n$] is much easier to do if we imagine the dice as distinguishable (i.e. $6\times 5 \times 4/6^3$) than by enumerating ordered partitions of 3 into 6 pieces and figuring out the relative frequency of each type.

$\endgroup$
4
  • $\begingroup$ I agree that the partitions of 365 is tough, but for the dice case, it should be easy enough right: numerator: $\frac{6 \times 5 \times 4}{6}=20$ denominator would be (no repeats + one repeat + all same) = (20+6*5+6) = 56. Which gives prob of no repeats = $\frac{20}{56}$ which is vastly different from $\frac{6\times 5\times 4}{6^{3}} = \frac{5}{9}$ $\endgroup$ – tpb261 Nov 15 '18 at 16:00
  • $\begingroup$ But those 56 items are NOT equally likely -- the multiset [1,1,1] occurs less often than the multiset [1,3,4], for example, and though you can, in theory model the dice rolls by unordered combinations (i.e. multisets) you can not get the probability of events by just dividing the cardinality of the event by the cardinality of the sample space. You must weight the (multiset) outcomes by their frequency which for practical purposes takes you back to viewing them as ordered triples, since that view makes them equally likely. $\endgroup$ – Ned Nov 15 '18 at 23:47
  • $\begingroup$ @tpb261 see the comment above (sorry I forgot to address you in the comment) $\endgroup$ – Ned Nov 19 '18 at 2:52
  • $\begingroup$ Thanks!! I did check your comment on phone (from where I don't like to reply), and came to my desktop just now. I missed the point in your answer. My bad. $\endgroup$ – tpb261 Nov 19 '18 at 11:56
0
$\begingroup$

Combinations exclude order, while permutations take order into account.

So when it comes to assigning ($person_0$,$person_1$, $person_2$) birth dates from $\{a,b,c,d\}$

(Arrays used below, index denotes person_number .. so if $a$ has index 0, a has been assigned to $person_0$)

[a,b,c], [c,b,a], [b,c,a] .. would be considered the same one element.

So if you are trying to calculate the length of the favorable outcomes space, you'd see why that would be incorrect

As for the the denominator i.e the length of space of all possible outcomes $365^n$ should not give anyone trouble

So P = $\frac {\text{length of favorable outcome space}}{\text{length of all possible outcomes space}}$

So just $C^{365}_n$ would give you a length of set of assignments where order is not important and that is pretty much it. WHen it comes to probability you are missing the deominator

P.S. $\frac{P^{365}_{n}}{365^{n}}$ is the probability of no one sharing the same birthday

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.