4
$\begingroup$

The number of possible poker hands drawn from a standard 5-card deck is ${52 \choose 5}$. This is sampling without replacement where order does not matter, e.g., A-K-Q-J-10 is the same hand as 10-J-A-K-Q.

In a group of 5 individuals the number of possible sequences of birthdays (using the standard rules of the Birthday Problem) is $365^5$. This is sampling with replacement where order does matter, e.g., 1-7-23-23-314 is different than 23-7-23-314-1. I can't seem to develop any intuition for why order should matter in the Birthday Problem, i.e., why isn't the number of possible sequences ${365+5-1 \choose 5}$?

Can someone help me out and explain why order matters?

$\endgroup$
  • 1
    $\begingroup$ Who said order matters? Your answer key? It might be implied by the term "sequence" but that's pretty ambiguous $\endgroup$ – shadowtalker May 12 '15 at 20:20
  • 1
    $\begingroup$ You can make order matter in your poker hands and have $\dfrac{52!}{47!}$ possible hands, i.e. $5!$ as many. You could easily adjust the rest of your analysis to fit this. But this option to choose whether to make order matter or not does not work so well with sampling with replacement especially if you want to use counting arguments. $\endgroup$ – Henry May 12 '15 at 20:57
  • $\begingroup$ @ssdecontrol, I am working backwards from Table 1.2.1 on page 16 of Casella and Berger "Statistical Inference." More specifically, 365^5 in the Birthday Problem implies sampling with replacement and order matters according to that table. $\endgroup$ – Thomas May 12 '15 at 22:44
  • $\begingroup$ @Thomas it does. Strange but my only explanation is that they specifically mean a sequence to mean an ordered sequence $\endgroup$ – shadowtalker May 13 '15 at 1:17
  • $\begingroup$ @Thomas when you state the Birthday Problem (in caps), so you mean this: en.wikipedia.org/wiki/Birthday_problem $\endgroup$ – mandata May 13 '15 at 14:52
6
$\begingroup$

It is possibly in the language used. In mathematics, language is very important, so one has to be careful how something is described or discussed. Also, these situations are a little different, though it is important not to conflate the concepts of order and replacement. Language aspect: A 'hand' in cards does not denote order. 'number of possible sequences' denotes order. So order matters here because it was requested. So that is one difference.
Structural difference: Once a card is picked, that possibility (rank&suit) is no longer available, whereas in the birthday problem, all 365 days are available to each of the 5 individuals.

$\endgroup$
1
$\begingroup$

After further study, allow me to offer this answer in addition to the given by mandata. I believe that my initial intuition was correct in that there are indeed ${365+5-1 \choose 5}$ possible sequences in the Birthday Problem discussed above, i.e., order does not matter when the goal is to enumerate the number of sequences. However, these sequences are not equiprobable because we are sampling with replacement, so they can't be used to define the sample space needed to calculate the probability of two or more individuals having the same birthday (see Example 1.2.19 on page 17 of Casella and Berger). To define the sample space for the probability calculation the $365^5$ ordered sequences must be used because they are equiprobable. I believe that this is what Henry was saying in his comment above. I have looked at a number of statistics textbooks that discuss how to solve the Birthday Problem and none of them mentioned this subtlety.

$\endgroup$
  • $\begingroup$ I think your logic failed. You don't know which 4 birthdays might need to be added. You would need all days repeated 5 times. $\endgroup$ – paparazzo Mar 24 '18 at 13:16
1
$\begingroup$

I've learned some things from thinking about this. Think about drawing twice from {H,T} with replacement -- there are only three possible 'hands' HH,HT,and TT. But not all three 'hands' are equally likely. Our experience suggests that HT should count twice. In general, the probablity of each 'hand' is not $\frac{1}{(\#\text{possible hands})}$ but rather it is $\frac{\#(\text{ways to draw that hand})}{\#(\text{ways to draw any hand})}$.

This explains why ordered calculations are justified in the birthday problem.

To take an extreme example, it should feel true that "all 5 people born January 1st" is less likely than "4 people born January 1st and 1 person born January 2nd." By our empirical law, the second scenario is five times more likely. Doing the calculation without order would assume these two 'hands' were equally likely.

Based on this example, I think doing the calculation without order would over-estimate the frequency of duplicates (because it counts them with commensurate probability as the all-distinct cases). This is borne out in the calculation: the inequality $\frac{\binom{365}{k}}{\binom{365+k-1}{k}} < 0.5$ is first achieved by $k=17$ (the LHS is the chance of all distinct birthdays if all 'hands' were counted equally likely).

$\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.