Back when I was in college, we did a thing in the week leading up to Christmas called “pixie week”. It’s the old secret Santa game where all the participating guys pull a girls name out of a hat and vice versa. You then get them a little gift each day of the week and leave it for them anonymously. Lived in this dorm for three years and one year, as it happened, I pulled the name of the same girl who pulled my name. This strikes me as unlikely, in the extreme. But I figured that now, with the Straight Dope folks debating the issue I can nail down the exact odds of this having happened. OK, let’s assume for purposes of simplification that there were 75 participants of each gender. Are the odds a simple one in seventy-five? They’re probably not affected by the fact that it was me that it happened to, but what about “pulling order”. I mean that there would be cases where she could not possibly have pulled my name because someone else had gotten it already. Or is that balanced off by the fact that there would be cases where she would be picking from a smaller pool of names, pulling later, that I would still be part of. Is it even possible to calculate the odds without knowing pulling order?
This question has bugged me off and on for decades.
Right. There’s no reason her name would be any more or less likely than anyone else’s to be the one you end up with. Since all 75 names have the same probability as each other, that probability must be 1/75.
It’s not the same as the shared birthday puzzle, because in that puzzle the draw (assigning a birthday to each person) is effectively with replacement, while in this case the draw (assigning an integer to each person) is without replacement. This question is basically asking how many permutations of the numbers 1 to N have at least one fixed point (an alternative interpretation is that you’re asking for exactly one fixed point). Wikpedia give formulas for the number of permutations of N that have exactly one fixed point, and the number that have zero fixed point. If the question is “at least one” then the answer is N! minus the latter formula. If it is “at least one” then it’s just the former formula. Both formulas are kind of messy and not easy to transcribe here, so you can look at them on the wiki page. In this example, both formulas involve the sum of 75 terms, so I don’t feel like actually doing the calculation. The wiki page doesn’t reference an OEIS page but there probably is one.
Of note, no matter how many participants there are, the expected (i.e., average) number of matches is exactly 1. Sometimes you won’t have any, and sometimes you’ll have more than 1, but on average, it’s 1.
There are TWO permutations involved, but one can be ignored: “Wlog number the girls drawn by 1,2,…,75 as 1,2,…,75 respectively.”
In the limit, as N becomes large (and N=75 is large enough), the chance of no hit becomes 0.36787944117144, the reciprocal of Euler’s number 2.718281828459. (More generally, the chance of k hits approaches the chance of k in a Poisson distribution of mean 1.)
So, we all agree that there is a 1/75 chance of this happening to you on any given year.
The chance of this happening to you, at least once over the 3-years period you spent in the dorm is:
1-(1-1/75)^3 = 3.95%
or about 1 in 25. This is not so small; in fact it is easier than throwing a double six.
The cool thing would be for this to happen on three consecutive years, with the same girl. A quick simulation told me that the odd of this happening to someone in the dorm is about 1/5200.
Look, I know I am not the best in math, but wouldn’t it be something like 1 out of 150? The odds of him picking her number would be 1 of 75. The odds of her picking his, also 1 of 75. The odds of both happening would be 1 of 150.
This seems logical to me but my logic and math logic don’t always agree.
But you forgot to account for the fact that this could have happened with 74 other girls.
So, the odds of him picking “some girl’s” number are 1 out of 1 since he will necessarily pick a girl. And the odds of whichever girl he picked picking him in return are 1/75.
Try separating the events in time: The girls pick on Monday, the boys on Tuesday. The “big reveal” will be on Friday.
By the time Tuesday rolls around, it’s easy to see that there’s only one specific girl who “has your number,” so to speak, and 74 that don’t… So you’ve got a 1 in 75 chance of picking her.
But (unknown to you) a freak hurricane blizzard sharknado occurs on Monday, and the girls’ choices end up getting made on Wednesday, instead. By the end of the draw, there’s still only one specific girl that has your number, so there’s still a 1 in 75 chance that that’s the one you’re holding.
Note that come Friday when all is revealed, it doesn’t matter who picked first or when, only that each side picked out of a pool of 75.
A critical thing with probabilities is to think carefully about what you’re assuming you know beforehand. This can make an immense difference.
A very obvious example is a lottery. Suppose you didn’t play this week. You see the 6 numbers come up in the draw. Although the chance of those particular numbers coming up is incredibly small, obviously you don’t feel that anything remarkable has happened, since some numbers had to come up. You weren’t looking out for any particular numbers that you specified beforehand. A lottery drawing is only remarkable if the numbers in the draw coincide with a set of numbers that you specify beforehand when you buy a ticket.
Another great example was the O.J. Simpson trial. The defense cited a statistic that was something like only 1 in 10,000 people murders their spouse, with the obvious implication. But that’s the wrong probability to consider, because we already know she’s dead. Given the prior knowledge that somebody did murder her, the probability (purely statistically, without considering any other circumstances) that the murderer was the spouse is more like 1 in 2.
In this example, it makes a huge difference if (say) the boy has a prior crush on a specific girl. The chance that he picks a particular girl specified beforehand and she also picks him then follows more along your lines of reasoning - although the probabilities multiply rather than add, it’s (1/75)*(1/75), extremely unlikely. But if it can be any girl, you can see that there are 75 girls with whom this could happen, so it’s far less unlikely, just 1/75.
There is a simple problem -
You are asking either “what are the odds it happens to me?” which is 1 in 75.
Or you are asking “what are the odds it happens to some pair in the pool”? Not the same.
This is why the birthday paradox works - it asks “what are the odds I will find 2 people in the group with the same birthday?” not “what are the odds someone has the same birthday as me?” (The answer to the latter is obvious - 1/365 or else 1 in (365*4+1)
The girls pick on Monday - so each girl picked a certain different guy. The guys then pick Tuesday. The odds somebody gets a match? Approach from a different angle - what are the odds nobody gets a match? the first guy? 74/75 no match. But he’ picked someone an that eliminates her from being a match for someone else.
The second guy? There’s a 1 in 75 that his match is already picked, otherwise a 1 in 74 that he could pick the right girl. .
The third guy? There’s a 2 in 75 that his match is already picked, otherwise a 1 in 73 that he could pick the right girl.
The furth guy? There’s a 3 in 75 that his match is already picked, otherwise a 1 in 72 that he could pick the right girl.
and so on…
The last guy - 74 in 75 that she was already picked.
I leave the solution as an exercise to the reader…