



Store




CTK Exchange
Owen
guest

Nov0205, 07:09 AM (EST) 

"Gift Exchange probability"

While reading the "Plane Problem" probability question posed in another thread I was reminded of a probability problem that I've attempted to solve at various times in the past few years. I've also given the problems to many mathematician friends; while they have all found it intriguing, none have been able to solve it. Here goes. Each person brings a gift to a Christmas party for a gift exchange; the gifts are numbered 1 to n. Small tags with the numbers 1, 2, ..., n are put in a hat and the party goers consecutively pull a card out of the hat in order to determine the present he or she will receive. If one pulls out a card corresponding to the number of his or her own present, then the card is returned to the hat and that person draws another card. The question is: what is the probability that the last person gets stuck with his or her own gift? 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 


mr_homm
Member since May2205

Nov0705, 10:55 AM (EST) 

1. "RE: Gift Exchange probability"
In response to message #0

Well, this one was rather tricky! I have a solution, but it is rather complicated, so if you know of a simpler method, I would be interested to hear about it. Here is how I solved the problem: 1) Note that everybody except the last person is guaranteed not to get his own gift, because there are always at least two choices, and he can keep trying until he gets a different gift. 2) Since the drawing is random, every possible mapping of persons to gifts is equally likely, so probability can be determined by counting the number of cases where the last person does or does not get his own gift. Let's call the number of cases where no one among n people receives his own gift g(n). Then the probability we are looking for will be g(n1)/(g(n1)+g(n)). The numerator counts the number of ways n1 people could exchange gifts without anyone getting his own gift, which is exactly what happens among the first n1 people when the last person is left holding his own gift. Of course, g(n) counts the cases in which everyone including the last person does not get his own gift. The fraction is therefore the relevant cases divided by the total cases, so it gives the probability. 3) To do the counting, you need to break the possibilities down into manageable cases. First, the total number of ways to match n gifts with n people (regardless of whether any people get their own gifts) is n!, which includes all the cases where some people get their own gifts, and all the cases where no one gets his own gift. We want to know how many of these latter cases there are. The easiest way to find this is to start with n! and subtract out the case where exactly one person gets his own gift, then the case where exactly two get their own gifts, and so on. (Why not try to take a shortcut and subtract out all at once the set of all cases where at least one person gets his own gift? Because it is harder to count these properly without accidentally counting some twice. The more specific the cases you are counting, the easier it is to be sure you are not missing any or overcounting.) Now how many cases are there where exactly k persons get their own gift? There are n people to choose from, and we must choose k of them, which gives B(n,k) = n!/(k!(nk)!) choices. After choosing the people who do get their own gifts, the remaining nk people must not get their own gifts, which can happen in g(nk) ways. Therefore, we get g(n) = n!  sum_from_1_to_n(B(n,k)g(nk)). Now since B(n,k) = B(n,nk), we can rearrange the sum to be sum_from_0_to_(n1)(B(n,k)g(k)), and the equation can be rearranged neatly into n! = sum_from_0_to_n(B(n,k)g(k)). This lets us recursively calculate g(n). From now on, sum_from_0_to_n will be written as just sum_n. 4) Next, we must try to make this calculation a little easier, since it involves subtraction of quite large values (factorials) to find the answer. Even with a computer, you won't be able to calculate the solution this way, because the computations will involve numbers hundreds of digits long for n=100, for example. Fortunately there is a neater way to calculate it. I hope no one will mind the intrusion at this point of a short biographical anecdote. Long ago, when I was 7 years old, I was obsessed with patterns that could be found in sequences of numbers by taking their successive differences. I found among other things, that repeatedly taking the successive differences of polynomial values you eventually reached a constant value, that there was a pattern that could be used to extrapolate the rest of the sequence. I also found that you could construct sequences where the first, second, or in general kth successive difference regenerated the original sequence (these are of course exponential sequences). More relevantly, I also found that for every sequence S, there was an associated sequence S' where the successive differences of S gave S' and the successive sums of S' gave S. For example
1 0 1 2 9 44 1 1 3 11 53 2 4 14 64 6 18 78 24 96 120
The first line above is g(n) calculated by hand for n = 0,...5. This is the sequence S'. The sequence running down the left side of the triangle is obviously n! for n = 0,...5. This is the sequence S. It is obvious when you look at the triangle of numbers above that the second diagonal is the successive difference of the first, and the third diagonal again is the successive difference of the second, and so on.
What does that have to do with the current problem? The formula sum_n(B(n,k)g(k)) is exactly the formula for the nth successive sum of g(k). Back when I was 7 I could see that this relationship between S and S' was true, but I had no idea how to write any of this down. Now that I have been to school, I can state this as "my childhood theorem:" sum_n(B(n,k)S'(k)) = S(n) iff sum_n(B(n,k)S(k)(1)^(nk)) = S'(n). Applying this to the current problem gives sum(B(n,k)k!(1)^(nk)) = g(n). Now notice that B(n,k)k! = n!/(nk)! so that g(n) = n!sum_n(((1)^(nk))/(nk)!) = n!sum_n(((1)^k)/k!). Therefore by factoring n! and pulling the last term out of the sum, we get a very nice recursion for g(n): g(n) = n(n1)!(sum_(n1)(((1)^k)/k!) + ((1)^n)/n!) = ng(n1) + (1)^n. This means the g(n) is "almost factorial", only having an extra additive +/ 1 term in the recursion. Now the probability can be calculated by p(n) = g(n1)/(g(n)+g(n1)) = g(n1)/(ng(n1) + (1)^n + g(n1)) = 1/(n + 1 + ((1)^n)/g(n1)). This is the exact formula for the probability, and it is now in a form where the calculation can be done with great accuracy, since the only large term is in a denominator. In fact, for large n, the formula for g(n) approaches n!/e, and so to an excellent approximation (by "excellent" I mean hundreds of digits of accuracy for n = 100, for example), the probability is 1/(1 + n + ((1)^n)e/n!). This becomes indistinguishible from 1/(1+n) for practical purposes when n > 10 or so. Well, that certainly took a lot of work; either the problem's simplicity is deceptive, or I am missing the obvious. Stuart Anderson 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



Owen
guest

Nov0805, 08:47 PM (EST) 

2. "RE: Gift Exchange probability"
In response to message #1

Thanks for taking the time to work on this problem. Indeed I think it is a challenging one. It appears that your g(n) function is simply the # of derangements of the integers 1 to n. I believe that function is well known and does involve factorials in a summation. I have tried using derangements to solve the problem, too. However, I believe I disagree with your very first linethat all permutations are equally likely.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!


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




mr_homm
Member since May2205

Nov1105, 01:53 AM (EST) 

3. "RE: Gift Exchange probability"
In response to message #2

Hi Owen, >However, I believe I disagree with your very first >linethat 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(j1j2)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)(1p_1(k)) = p_1(k), which solves to give P(j1~j2) =( p_1(k)  p_2(k))/(1p_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 k1 gifts, which gives a probability of 1/(k1) of removing any given one. Therefore, for each gift j < k, the probability that it remains is (k2)/(k1). Thus the contingent probability for gift j to remain is (k2)/(k1)P(jk) = (k2)/(k1)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 (k1)/kP(j~k) = (k1)/k(p_1(k)p_2(k))/(1p_1(k)). Hence the overall probability for gift j to remain is (k2)/(k1)p_2(k)/p1(k)*p_1(k) + (k1)/k(p_1(k)p_2(k))/(1p_1(k))*(1p_1(k)) = (k2)/(k1)p_2(k) + (k1)/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(k1) = (k1)/kp_1(k)  1/(k(k1))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(k1) = (k3)/(k1)p_3(k) + (k2)/(k)(p_2(k)  p_3(k)) = (k2)/kp_2(k)  2/(k(k1))p_3(k). The pattern is clear upon calculating the recursion for p_3(k), and it is in general p_m(k1) = (km)/(k)p_m(k)  m/(k(k1))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 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




Owen
Member since Nov1105

Nov1505, 09:04 PM (EST) 

8. "RE: Gift Exchange probability"
In response to message #3

Thank you, Stuart. This looks promising. I heard (through a friend) that someone had found a recurrence relation (which they couldn't solve), but I never saw it'so I don't know whether it is similar to yours or not. 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 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




mr_homm
Member since May2205

Nov1605, 07:04 PM (EST) 

9. "RE: Gift Exchange probability"
In response to message #8

>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. 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/(n1), 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


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




mr_homm
Member since May2205

Nov1605, 11:27 PM (EST) 

10. "RE: Gift Exchange probability"
In response to message #9

Clarification: >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/(n1). Stuart


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




mr_homm
Member since May2205

Dec0605, 07:42 AM (EST) 

11. "RE: Gift Exchange probability"
In response to message #8

I've been thinking about this one on and off for a while, now, and I have something that ALMOST works: 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,k1} = (km)/k·p_{m,k}  m/(k(k1))·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(k1)·p_{m,k1} = (k1)(km)·p_{m,k}  m·p_{m+1,k} and then absorb the m coefficient by redefining p as p_{m,k} = q_{m,k}/(m1)!, so that k·(k1)q_{m,k1} = (k1)(km)·q_{m,k}  q_{m+1,k}. Similarly, let q_{m,k} = r_{m,k}·k! to get (k1)·r_{m,k1} = (k1)(km)·r_{m,k}  r_{m+1,k}. Next, and this is a little trickier, notice that (k1)m = (km)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}/(km)! to get (k1)·s_{m,k1} = (k1)·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}·(k1)^{m}, which would leave the left hand side with a coefficient of ((k1)/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 (n1)^{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)^{m1}(Sym(n1,nm)/(n1)!·s_{m,n}), where Sym(n,m) is the mfold 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} = (nm)!(m1)!/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)^{m1}(Sym(n1,nm)/(m·Bin(n,m)·(n1)!) = 1/(n1)!·Sum_{m=1}^{m=n}(1)^{m1}(Sym(n1,nm)/(n·Bin(n1,m1)) = 1/(n1)!·Sum_{m=0}^{m=n1}(1)^{m}(Sym(n1,n1m)/(n·Bin(n1,m)) = 1/n!·Sum_{m=0}^{m=n1}(1)^{m}(Sym(n1,n1m)/(Bin(n1,m)). Reindexing this sum by letting m > n1m, and using the fact that Bin(n1,m) = Bin(n1,n1m), you get s_{1,1} = 1/n!·Sum_{m=0}^{m=n1}(1)^{n1m}(Sym(n1,m)/(Bin(n1,m)). This gives s_{1,1}, but what is p_{1,1}? Using the variable changes again gives p_{1,1} = 1!/((11)!(11)!)·s_{1,1} = s_{1,1}, so we get p_{1,1} = 1/n!·Sum_{m=0}^{m=n1}(1)^{n1m}(Sym(n1,m)/(Bin(n1,m)). Noticing that Bin(n1,m) is exactly the number of terms in Sym(n1,m), this ratio can be interpreted as the average value of the mfold products of the integers from 1 through n1. Therefore, the final conclusion can be stated as follows: The probability p_{1,1} is the alternating sum of the averages of the mfold 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 mfold 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 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



mpdlc
guest

Nov1305, 08:12 AM (EST) 

4. "RE: Gift Exchange probability"
In response to message #0

Back to the desktop after a few days off. I found this question in probability. This is a field which, even recognizing its importance in research, sampling, polling, gambling.. and for measuring the uncertainty, I fully dislike because for me like politicians is filled with subtilities, deceiving tricks, double meanings and concealing surprises, it is hard even sometimes to merely understand the proposed question. So declaring flatly my ignorance on the subject I will take the question, just like one in a brainstorming session in the hope to bring a what maybe a new approach, in what looks an extensive research in your side. Those are my views a) I start organizing in a matrix the data rows for persons, columns for the gifts. An elements of principal diagonal of the matrix will represent the gift and the person who donated.
b) The probability that the last person gets stuck with his or her own gift (Gn), must equal to the one that gift precisely not to been selected during the last N1 allocations. c) Since it is not permitted during the first N1 allocations that person take ist own gift, the elements in the main diagonal ought not to be considered because the extractions must be repeated, it is like non existing ones. Indeed it is no change in the probability it will certainly change the number of extractions from the hat needed before we get into the last allocation, but it does not change the odds.
d) We start with the first person ( first row in our matrix) an he/she get Gk located in column K the chances of not getting Gn ( the gift of the last person) is obviously (N1)/N. Now we cross the column K an the row 1. For the next one person row 2 the combined probability yields (N1)/N times (N2)/(N1) which equal to (N2)/ N and so for to the person (N1) it wil be 1/N, which in accordance with b) is the probability of the last person to get stuck with is own present.


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



mpdlc
guest

Nov1305, 12:43 PM (EST) 

5. "RE: Gift Exchange probability"
In response to message #4

Once posted I realized of an error in my message the probability for the first person yields (N2)/(N1), since G1, its own gift, should not be considered as a favorable case. And consequently for the secon one should be (N3)/(N2). So the end result has to be 1/(N1) instead of 1/N. 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




Owen
Member since Nov1105

Nov1405, 08:40 AM (EST) 

6. "RE: Gift Exchange probability"
In response to message #5

"Once posted I realized of an error in my message the probability for the first person yields (N2)/(N1), since G1, its own gift, should not be considered as a favorable case. And consequently for the second one should be (N3)/(N2)." 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 (N2)/(N1), not (N3)/(N2). 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. 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




mpdlc
guest

Nov1405, 10:31 AM (EST) 

7. "RE: Gift Exchange probability"
In response to message #6

I fully understand your point. 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. 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Front page
Contents
Copyright © 19962018 Alexander Bogomolny

