[staveleyf]

I sing in a men's choir numbering 70. Our librarian gives us each a copy of the sheet music for every song that we are performing, on which we write notes to help us during rehearsals. When we have finished performing a piece of music (this may typically be after a period of 1-2 years) we return the sheet music to the librarian.

When a piece of music comes back into our repertoire, the librarian will randomly hand out copies of the sheet music to choir members.

Assuming the same 70 people are members of our choir (in practice this doesn't happen because membership changes):
1) What is the chance that I will get back the same copy of the sheet music that I handed back last time?
2) What is the chance that at least 1 person in the choir will get back their original copy of sheet music?

[ebaines]

1) What is the chance that I will get back the same copy of the sheet music that I handed back last time?

If you assume that the number of pieces of sheet music available to be handed out is the same as the number of choir members, then the chance of you getting your old sheet back is 1 out of 70, or about 1.4% (Note - I would expect that in reality the number of copies of music that the librarian has is probably gteater than the number of choir members, so as to have extras just in case, but we'll ignore that).

2) What is the chance that at least 1 person in the choir will get back their original copy of sheet music?

This one's a little more difficult, but if n = number of choir members then for large values of n the probability that when the music is handed out at least one choir member gets his/her sheet back from last time is about 36.8%. I will spare you the details but the actual values for p for various values of n are:

n, probability(at least one)
1, 1
2, 0.5
3. 0.333
4, 0.375
5, 0.3667
6, 0.368056
7, 0.367857
8, 0.367882
9, 0.367889
10, 0.367889

More precisely the value for large vakues of n is 1 - 1/e. Here's why: The probability that any one individual gets his sheet back is 1/n, which means the probability that a particular member does not get his sheet back is (n-1)/n. The probability that at least one member gets his music back is one minus the probability that no one gets their music back. So P(at least one) = 1 - ((n-1)/n)^n. This formula can be rearranged as follows:



For large values of n:



So p( at least one ) = 1 - 1/e for large values of n.

[jcaron2]

EBaines,

I've been thinking about this problem for a few days. It seems pretty straightforward: each person has a probability of 69/70 of getting back a copy other than their original. Hence it would seem that the probability of nobody getting their original would be (69/70)^70 = 0.3652. Therefore, the probability of at least one person getting back their original would be 1 - 0.3652 = 0.6347 just like you said. (Though for the time being there's a typo in your table, since you forgot to actually do the subtraction after line 1 :)).

I was getting ready to answer the question as such, but I decided to run a quick Matlab simulation just to verify. For some reason, the answer I get is close to what we calculate, but not exact. It takes several million trials to consistently converge to four digits of precision, and it always converges on 0.6321 as the answer. :confused: It's so close, but definitely different. WHY!? It's driving me nuts.

Any ideas? It seems unlikely that it's some sort of imperfection in Matlab's random number generation, but I guess I can't rule that out.

[ebaines]

for the time being there's a typo in your table, since you forgot to actually do the subtraction after line 1 :) .

You're right! I got so caugt up in finding the probability that no one gets their sheet back that's what I put in the table. My bad. So yes - the probability that at least one gets his back is close to 1-.0.3679 =0.6321. The table (corrected) should be:

n, Prob(at least 1)
1, 1
2, 0.5
3, 0.6667
4, 0.625
5, 0.6333
6, 0.63194
7, 0.632143
8, 0632118
9, 0.632121
10, 0.632121

It takes several million trials to consistently converge to four digits of precision, and it always converges on 0.6321 as the answer. :confused:

But 1-1/e does indeed equal 0.6321, so I think the simulation is good. The problem is that (69/70)^70 is not precisely the answer to the problem, though it's close. What I tried to describe above is that it's a good approximation, especially as n gets large. But you can see for example that if n= 3 this approximation gives 1-(2/3)^3 = 0.7037, which is significantly off from the true answer for n=3, which is 2/3. The error is because the approximation treats each choir member's receiving of a sheet as independent events. But these are truly not independent events - if I get your sheet then the odds of you getting your sheet back is 0, not 1/n.

I should have been a bit clearer that the numbers I provided in the table are NOT the approximate answers as determined by 1-((n-1)/n)^n, but rather are the actual probabilities for each value of n. I didn't bother to go into the technique that I used to come up with these, as it's quite cumbersome and I figured the OP was less interested in how to do the calculation than in what the answer actually is. But if you're interested - I could provide a follow up with the details.

[jcaron2]

But if you're interested - I could provide a follow up with the details.

I would be interested. My apologies to the OP who probably doesn't care about all the details.

Ironically when I did the simplified calculation and saw the answer, I immediately saw that it was approaching 1-1/e (since ~63% is one of those numbers that comes up over and over in the world of engineering). Yet somehow, when I ran the simulation and got an answer that was even closer to the true value of 1-1/e, I didn't recognize it as such. I have no excuse. :o

[ebaines]

I would be interested.

OK, here is the method that I used:

Suppose there are n choir members, identified as A, B, C, …. and also n pieces of music identified as a, b, c, … The music sheets are shuffled into random order and then distributed to the members A, B, C, etc. The question is: when randomly distributing the music sheets what is the probability that at least one of the members gets their specific music sheet?

Let f(j,k) = the number or ways that j pieces of music can be distributed to j choir members with precisely k matches. For example (3,1) is the number of ways that 3 pieces of music can be distributed to 3 people with 1 match. The notation f(n,0) signifies the number of ways that n pieces of music can be distruibuted to n choir members with no matches ar all.

We start by considering f(n,0) for the first few values of n:
For n = I, f(1,0) = 0 because if there is only one choir member and one sheet of music he can't help but be given his own sheet.
For n=2, f(2,0) = 1 . The music can be distributed in only two possible ways: ab and ba. The first matches the choir members, the second does not.
For n=3, f(3,0) =2. There are 6 possible ways that the music can be distributed: abc, acb, bac, bca, cab, and cba. Two of these have no matches to the order of choir members. So f(3) = 2.
Now consider n = 4, and we will begin to generalize the method. First note that for n pieces of music there are n! Ways that the music can be distributed. Then consider that there are n+1 = 5 possible outcomes, which for n=4 are:

Case 1. Everybody gets matched to their music. There is precisely one sequence that accomplishes this, which for n =4 is: abcd. Hence f(4,4) = 1
Case 2. Three people get properly matched and one does not. This is an impossible outcome – you can't ever have just one person with a mismatch, since his own piece of music must have been given to someone else. Hence f(4,3) = 0.
Case 3. Two people are matched correctly, and two are not. The number of ways that the 2 people can be matched is C(4,2) = 4 x 3/2 = 6. For each of those possibilities the number of ways that the two mismatches can then be arranged is f(2,0) = 1; for example if A gets a and B gets b, then for C must get d and D must get c. So f(4,2) = 6 x 1 = 6.
Case 4. One person gets the right music and three do not. The number of ways this can occur is C(4,1) x f(3,0) = 4 x 2 = 8. Thus f(4,1) = 8.
Case 5. Zero people get the right music = f(4,0).

Now comes the trick. The sum of the above 5 possible outcomes must add up to 4! So:

4! = 1 + 0 + 6 + 8 + f(4,0), and hence:

f(4,0) = 4! – 1 – 0 – 6 – 8 = 9.

As check those 9 possibilities of no matches are: badc, bcda, bdac, cadb, cdab, cdba, dabc, dcab, dcba.

Thus we have calculated a value for f(4,0) using the oreviously determined values for f(2,0) and f(3,0). In this way we can build up a recursive technique for calculating f(n,0) based on the principle that for any value n>1:

n! = 1 + 0 + C(n,n-2)f(2,0) + C(n, n-3)f(3,0) + … + f(n,0) , or:
f(n,0) = n! – (1 + C(n,n-2)f(2,0) + C(n, n-3)f(3,0) + … + C(n,1)f(n-1,0))

The probability that there are no matches for a group of n is f(n,0) divided by n!:

P(no matches for population n) = f(n,0)/n! = 1 – (1+ (n,n-2)f(2,0) + C(n, n-3)f(3,0) + … + C(n,1)f(n-1,0))/n!

Finally, the probability that at least 1 choir member gets the correct music is 1 minus the above, or:

P(at least one match) = 1- P(no matches) = (1+ (n,n-2)f(2,0) + C(n, n-3)f(3,0) + … + C(n,1)f(n-1,0))/n!

I used Excel to build up a table for n = 1, 2, 3,. up to a value of n = 10, but beyond that the value is essentially equal to 1/e. Specifically I get:

N; P(at least one)
1; 1
2; 0.5
3; 0.6667
4; 0.625
5; 0.63333
6; 0.631944
7; 0.632143
8; 0.632118
9; 0.632121
10; 0.632121

For comparison, 1-1/e taken to 6 decimals is also 0.632121.

I hope this explanation is clear.

[jcaron2]

Brilliant, EB!

Thanks for the explanation! Unfortunately I can't give you any rep because I need to spread it around first. :)