For example, when n=2, the probability the last person gets his own gift is 0. The permutation 12 will not occur and the permutation 21 must occur.

When n = 3, the only permutations possible are 213, 231, and 312, because the first person cannot keep his own gift. Half the time, then, he will take person number 2's gift and the other half of the time he will take person number 3's gift. In the former case, the two permutations 213 and 231 are equally likely.

So, I believe P(213) = P (231) = .25, while P(312) = .5.
So, when n=3, the probability person 3 gets stuck with his own gift is .25.

Does this make sense? I am typing it at 1:30 in the morning, so perhaps I'm not coherent!

>However, I believe I disagree with your very first
>line--that all permutations are equally likely.
>
>Does this make sense? I am typing it at 1:30 in the
>morning, so perhaps I'm not coherent!

Well, you're right of course. As soon as you pointed it out, I could see that the probabilities were not all equal, but were contingent on whether or not gift k was still present when person k made his choice. By the way, I had not originally meant to say that ALL choices were equally probable, only that all the
ALLOWED choices were equally probable. However, as you pointed out, even this much is not true. Therefore, I have started over with a recursive approach that takes into account the choices made at each stage. Here is what I have so far:

Suppose that there are n people, and that several have already chosen gifts, so that there are k gifts remaining. Number the people from high to low, so that person number n is the first to choose, and person number 1 is last. Then person k is about to choose a gift.

Now all the gifts number j, where j <= k, have been treated equally in every decision so far, because each person only considers whether a given gift is or is not his own, and all j <= k fall into the "not mine" category for all persons l, where l > k. Therefore, the probability that gift j has not yet been claimed when it is person k's turn to choose, is the same for all j <= k. Call this probability p_1(k).

We will also need to look at contingent probabilities, such as P(j1 is not yet claimed | j2 is not yet claimed), so we will need the joint probability p_2(k) = P( neither j1 nor j2 has been claimed before person k chooses). Again, this probability is the same for all distinct pairs of gifts when both j1 and j2 <= k. Therefore, the probability that j1 remains given that j2 remains is by Bayes theorem p_2(k)/p_1(k). From this we can calculate the probability that j1 remains given that j2 does not remain by P(j1|j2)P(j2) + P(j1|~j2)P(~j2) = P(j1). Substituting in the p_1(k) and p_2(k), we get p_2(k) + P(j1|~j2)(1-p_1(k)) = p_1(k), which solves to give P(j1|~j2) =( p_1(k) - p_2(k))/(1-p_1(k)). These two probabilities can be used to set up a recursion as follows:

Suppose at the start of turn k that we know p_1(k) and p_2(k). Then applying p_1(k) to gift k gives the probability that gift k is still among the choices. In that case, person k may choose with equal probability among the remaining k-1 gifts, which gives a probability of 1/(k-1) of removing any given one. Therefore, for each gift j < k, the probability that it remains is (k-2)/(k-1). Thus the contingent probability for gift j to remain is (k-2)/(k-1)P(j|k) = (k-2)/(k-1)p_2(k)/p_1(k). Similarly, in the opposite case where gift k is not still among the choices, the contingent probability for gift j to remain is (k-1)/kP(j|~k) = (k-1)/k(p_1(k)-p_2(k))/(1-p_1(k)). Hence the overall probability for gift j to remain is (k-2)/(k-1)p_2(k)/p1(k)*p_1(k) + (k-1)/k(p_1(k)-p_2(k))/(1-p_1(k))*(1-p_1(k)) = (k-2)/(k-1)p_2(k) + (k-1)/k(p_1(k) - p_2(k)). This formula makes sense because p_2(k) represents the case where gifts k and j remain, and p_1(k) - p_2(k) represents the case where one, but not both, of gifts k and j remain. Simplifying this formula gives p_1(k-1) = (k-1)/kp_1(k) - 1/(k(k-1))p_2(k).

However, it is clear that we will also need to know all the p_2(k) values, so we will need a recursion for p_2(k) as well. This will involve contingent probabilities of the form P((j1&j2)|k), which will require knowledge of p_3(k), defined as the joint probability that three distinct gifts numbered j <= k are still present at the start of turn k. Recursion on p_3(k) will require p_4(k), and so on. A similar calculation to that in the paragraph above gives the recursion for p_2(k): p_2(k-1) = (k-3)/(k-1)p_3(k) + (k-2)/(k)(p_2(k) - p_3(k)) = (k-2)/kp_2(k) - 2/(k(k-1))p_3(k). The pattern is clear upon calculating the recursion for p_3(k), and it is in general p_m(k-1) = (k-m)/(k)p_m(k) - m/(k(k-1))p_(m+1)(k).

Notice that p_m(k) = 0 for m > k, as there cannot be more gifts numbered j < k remaining than the total number k of gifts remaining. This means that as k decreases towards 1, there are progressively fewer recursions to calculate. Also, it is clear that when k = n, all the p_m(n) = 1 (provided m <= n), since all gifts are guaranteed to be present at the start of the process. This gives the iteration a set of starting values.

To test this out, I set up a spreadsheet with the general recursion formula in each cell, gave it the initial values, and computed some probabilities. The probabilities calculated by the formula match my hand calculations for n = 1,2,3,4, which is as far as I checked. This looks like a good stopping point for now. There is a unified recursive formula which calculates the probabilities, which is a big improvement over hand analysis, but I have not yet tried to find a closed form formula for the probability. It'should be possible to derive it, but this will have to be stage two of the analysis. Or perhaps someone else would like to try his hand at it?

More later.

--Stuart Anderson

It does seem that the solution might be asymptotic to 1/n. Here are some values for P(n) for n <= 10, if you want to check your spreadsheet further. These were computed by Jerry Grossman, who wrote a computer program to do it by brute force.

> n = 2, prob = 0 = 0
> n = 3, prob = 1/4 = 0.25
> n = 4, prob = 5/36 = 0.1388888888...
> n = 5, prob = 19/144 = 0.13194444444...
> n = 6, prob = 203/1800 = 0.11277777777...
> n = 7, prob = 4343/43200 = 0.100532407407407...
> n = 8, prob = 63853/705600 = 0.090494614512...
> n = 9, prob = 58129/705600 = 0.082382369614...
> n = 10, prob = 160127/2116800 = 0.075645786092...

Owen

I checked the numbers this morning. They all agree out to as many decimals as my spreadsheet will display. Also, just for fun, I expanded my spreadsheet and calculated the value for n=100, which turns out to be around 0.95. So if it is going asymptotically to 1/(n-1), it's not getting there very fast!

The recursion I gave can be simplified somewhat by changing variables, at the price of making more complicated starting values. This makes the spreadsheet more efficient, but it does not get me any closer to solving the recursion. I'll try more later.

--Stuart

>for fun, I expanded my spreadsheet and calculated the value
>for n=100, which turns out to be around 0.95.

I meant that pn = 0.95; p itself is of course 0.0095. This still shows that p is not very close to 1/(n-1).

--Stuart

The main strategy is to try to change variables to simplify the recursion. It is possible to make the recursion very simple, but the starting data then gets messier. The main point to notice is that when varying m changes a coefficient by a factor of m, then attaching a factor of m! to p can absorb the change, and similarly for k. Here is what I did (with better formatting this time):

The original recursion was p_m,k-1 = (k-m)/k·p_m,k - m/(k(k-1))·p_m+1,k and the starting values were p_m,n = 1 for 1 <= m <= n. First, multiply through to clear out the fractions, to get k(k-1)·p_m,k-1 = (k-1)(k-m)·p_m,k - m·p_m+1,k and then absorb the m coefficient by redefining p as p_m,k = q_m,k/(m-1)!, so that k·(k-1)q_m,k-1 = (k-1)(k-m)·q_m,k - q_m+1,k. Similarly, let q_m,k = r_m,k·k! to get (k-1)·r_m,k-1 = (k-1)(k-m)·r_m,k - r_m+1,k.

Next, and this is a little trickier, notice that (k-1)-m = (k-m)-1 = k=(m+1), so that the difference of the subscripts of the first and last terms are equal, and that of the middle term is one more. Therefore, let r_m,k = s_m,k/(k-m)! to get (k-1)·s_m,k-1 = (k-1)·s_m,k - s_m+1,k, and after bumping up the k index by one, get the form, k·s_m,k = k·s_m,k+1 - s_m+1,k+1.

It is impossible to get rid of these last two factors of k because they are associated with different k values in the subscripts. If the factor of k on the s_m,k+1 term could be removed, we would have a simple difference, with a scale factor. However, the change of variable that would remove this k is t_m,k = s_m,k·(k-1)^m, which would leave the left hand side with a coefficient of ((k-1)/k)^m, which is intractable because it is a function of both m and k.

Now rewrite the recursion as s_m,k = s_m,k+1 - 1/k·s_m+1,k+1, to see that s_1,1 is a kind of (n-1)^st successive difference of the sequence s_m,n, in which the term further to the right is divided by k. Studying this successive difference gives the following pattern (write it out for n=4 to see the it): s_1,1 = Sum_m=1^m=n(-1)^m-1(Sym(n-1,n-m)/(n-1)!·s_m,n), where Sym(n,m) is the m-fold symmetric product of the first n integers, i.e. the sum of products of all choices of m integers from 1 through n.

Now the values s_m,n are found by applying all our variable changes to p_m,n, which gives s_m,n = (n-m)!(m-1)!/n!·p_m,n = 1/(m·Bin(n,m)), where Bin(n,m) is the binomial coefficient. Substituting this into our summation formula above gives s_1,1 = Sum_m=1^m=n(-1)^m-1(Sym(n-1,n-m)/(m·Bin(n,m)·(n-1)!) = 1/(n-1)!·Sum_m=1^m=n(-1)^m-1(Sym(n-1,n-m)/(n·Bin(n-1,m-1)) = 1/(n-1)!·Sum_m=0^m=n-1(-1)^m(Sym(n-1,n-1-m)/(n·Bin(n-1,m)) = 1/n!·Sum_m=0^m=n-1(-1)^m(Sym(n-1,n-1-m)/(Bin(n-1,m)).

Reindexing this sum by letting m --> n-1-m, and using the fact that Bin(n-1,m) = Bin(n-1,n-1-m), you get s_1,1 = 1/n!·Sum_m=0^m=n-1(-1)^n-1-m(Sym(n-1,m)/(Bin(n-1,m)). This gives s_1,1, but what is p_1,1? Using the variable changes again gives p_1,1 = 1!/((1-1)!(1-1)!)·s_1,1 = s_1,1, so we get p_1,1 = 1/n!·Sum_m=0^m=n-1(-1)^n-1-m(Sym(n-1,m)/(Bin(n-1,m)).

Noticing that Bin(n-1,m) is exactly the number of terms in Sym(n-1,m), this ratio can be interpreted as the average value of the m-fold products of the integers from 1 through n-1. Therefore, the final conclusion can be stated as follows:

The probability p_1,1 is the alternating sum of the averages of the m-fold products, divided by n!. This is closer to closed form, but not quite there yet. It'seems to me that there may be a formula for the values of the m-fold products of integers (because this may be of some general interest outside of this puzzle), and if so, a true closed form formula could be derived. Does anyone know of such a formula?

I have checked my formula for the cases n=3 and n=4, and it gives 1/4 and 5/36, just as it'should. This looks like the end of stage two of finding a formula for the probability of the last person getting his own gift back. Whether there is a stage three or not depends on whether I (or someone) can find a formula for these products.

Well, that was certainly long -- I hope you found it worth reading to the end!

--Stuart Anderson

So the end result has to be 1/(N-1) instead of 1/N.

As Stuart mentioned above early in his post (I haven't had time to digest the entire post yet), the probabilities for the second (and subsequent) selector depends on which gifts were previously selected. If person 1 chose gift #2, then the probability of person 2 not choosing gift #N is (N-2)/(N-1), not (N-3)/(N-2). I believe that the conditional probabilities are such that we cannot simply multiply them as if they were independent.

I think you should get P(2) = 1, P(3) = 1/4, and P(4) = 5/36, if you want to test any closed form formulas you obtain.

The solution I gave it will be only valid if there is a discipline in the extraction order, so the next person to get the slip from the hat has to be precisely the one whose gift was selected in the extraction before, obviously it does not be the case.

I told you probability the only assure to you.... if that you will be never sure of anything.

I also will try to digest the whole of your researchs, I doubted I ever will achieve it, but as a consolation -it is said that Leibniz was a real donkey in the field,- so at least I will be in a good companion.