CTK Exchange Front Page Movie shortcuts Personal info Awards Reciprocal links Terms of use Privacy Policy Cut The Knot! MSET99 Talk Games & Puzzles Arithmetic/Algebra Geometry Probability Eye Opener Analog Gadgets Inventor's Paradox Did you know?... Proofs Math as Language Things Impossible My Logo Math Poll Other Math sit's Guest book News sit's Recommend this site    |Store|    CTK Exchange

 Subject: "Gift Exchange probability" Previous Topic | Next Topic
 Conferences The CTK Exchange This and that Topic #649 Printer-friendly copy Email this topic to a friend Reading Topic #649
Owen guest
Nov-02-05, 07:09 AM (EST)

 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?

Subject     Author     Message Date     ID Gift Exchange probability Owen Nov-02-05 TOP RE: Gift Exchange probability mr_homm Nov-07-05 1 RE: Gift Exchange probability Owen Nov-08-05 2 RE: Gift Exchange probability mr_homm Nov-11-05 3 RE: Gift Exchange probability Owen Nov-15-05 8 RE: Gift Exchange probability mr_homm Nov-16-05 9 RE: Gift Exchange probability mr_homm Nov-16-05 10 RE: Gift Exchange probability mr_homm Dec-06-05 11 RE: Gift Exchange probability mpdlc Nov-13-05 4 RE: Gift Exchange probability mpdlc Nov-13-05 5 RE: Gift Exchange probability Owen Nov-14-05 6 RE: Gift Exchange probability mpdlc Nov-14-05 7

 Conferences | Forums | Topics | Previous Topic | Next Topic
mr_homm
Member since May-22-05
Nov-07-05, 10:55 AM (EST)    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(n-1)/(g(n-1)+g(n)). The numerator counts the number of ways n-1 people could exchange gifts without anyone getting his own gift, which is exactly what happens among the first n-1 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!(n-k)!) choices. After choosing the people who do get their own gifts, the remaining n-k people must not get their own gifts, which can happen in g(n-k) ways. Therefore, we get g(n) = n! - sum_from_1_to_n(B(n,k)g(n-k)). Now since B(n,k) = B(n,n-k), we can rearrange the sum to be sum_from_0_to_(n-1)(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)^(n-k)) = S'(n).Applying this to the current problem gives sum(B(n,k)k!(-1)^(n-k)) = g(n). Now notice that B(n,k)k! = n!/(n-k)! so that g(n) = n!sum_n(((-1)^(n-k))/(n-k)!) = 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(n-1)!(sum_(n-1)(((-1)^k)/k!) + ((-1)^n)/n!) = ng(n-1) + (-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(n-1)/(g(n)+g(n-1)) = g(n-1)/(ng(n-1) + (-1)^n + g(n-1)) = 1/(n + 1 + ((-1)^n)/g(n-1)). 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 Owen guest
Nov-08-05, 08:47 PM (EST)

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 line--that 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! mr_homm
Member since May-22-05
Nov-11-05, 01:53 AM (EST)    In response to message #2 Owen
Member since Nov-11-05
Nov-15-05, 09:04 PM (EST)    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 mr_homm
Member since May-22-05
Nov-16-05, 07:04 PM (EST)    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/(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 mr_homm
Member since May-22-05
Nov-16-05, 11:27 PM (EST)    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/(n-1).--Stuart mr_homm
Member since May-22-05
Dec-06-05, 07:42 AM (EST)    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 pm,k-1 = (k-m)/k�pm,k - m/(k(k-1))�pm+1,k and the starting values were pm,n = 1 for 1 <= m <= n. First, multiply through to clear out the fractions, to get k(k-1)�pm,k-1 = (k-1)(k-m)�pm,k - m�pm+1,k and then absorb the m coefficient by redefining p as pm,k = qm,k/(m-1)!, so that k�(k-1)qm,k-1 = (k-1)(k-m)�qm,k - qm+1,k. Similarly, let qm,k = rm,k�k! to get (k-1)�rm,k-1 = (k-1)(k-m)�rm,k - rm+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 rm,k = sm,k/(k-m)! to get (k-1)�sm,k-1 = (k-1)�sm,k - sm+1,k, and after bumping up the k index by one, get the form, k�sm,k = k�sm,k+1 - sm+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 sm,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 tm,k = sm,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 sm,k = sm,k+1 - 1/k�sm+1,k+1, to see that s1,1 is a kind of (n-1)st successive difference of the sequence sm,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): s1,1 = Summ=1m=n(-1)m-1(Sym(n-1,n-m)/(n-1)!�sm,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 sm,n are found by applying all our variable changes to pm,n, which gives sm,n = (n-m)!(m-1)!/n!�pm,n = 1/(m�Bin(n,m)), where Bin(n,m) is the binomial coefficient. Substituting this into our summation formula above gives s1,1 = Summ=1m=n(-1)m-1(Sym(n-1,n-m)/(m�Bin(n,m)�(n-1)!) = 1/(n-1)!�Summ=1m=n(-1)m-1(Sym(n-1,n-m)/(n�Bin(n-1,m-1)) = 1/(n-1)!�Summ=0m=n-1(-1)m(Sym(n-1,n-1-m)/(n�Bin(n-1,m)) = 1/n!�Summ=0m=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 s1,1 = 1/n!�Summ=0m=n-1(-1)n-1-m(Sym(n-1,m)/(Bin(n-1,m)). This gives s1,1, but what is p1,1? Using the variable changes again gives p1,1 = 1!/((1-1)!(1-1)!)�s1,1 = s1,1, so we get p1,1 = 1/n!�Summ=0m=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 p1,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

mpdlc guest
Nov-13-05, 08:12 AM (EST)

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 viewsa) 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 N-1 allocations.c) Since it is not permitted during the first N-1 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 (N-1)/N. Now we cross the column K an the row 1.For the next one person row 2 the combined probability yields (N-1)/N times (N-2)/(N-1) which equal to (N-2)/ N and so for to the person (N-1) it wil be 1/N, which in accordance with b) is the probability of the last person to get stuck with is own present. mpdlc guest
Nov-13-05, 12:43 PM (EST)

In response to message #4

 Once posted I realized of an error in my message the probability for the first person yields (N-2)/(N-1), since G1, its own gift, should not be considered as a favorable case. And consequently for the secon one should be (N-3)/(N-2).So the end result has to be 1/(N-1) instead of 1/N. Owen
Member since Nov-11-05
Nov-14-05, 08:40 AM (EST)    In response to message #5

 "Once posted I realized of an error in my message the probability for the first person yields (N-2)/(N-1), since G1, its own gift, should not be considered as a favorable case. And consequently for the second one should be (N-3)/(N-2)."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. mpdlc guest
Nov-14-05, 10:31 AM (EST)

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.

 Conferences | Forums | Topics | Previous Topic | Next Topic
 Select another forum or conference Lobby The CTK Exchange (Conference)   |--Early math (Public)   |--Middle school (Public)   |--High school (Public)   |--College math (Public)   |--This and that (Public)   |--Guest book (Public) Educational Press (Conference)   |--No Child Left Behind (Public)   |--Math Wars (Public)   |--Mathematics and general education (Public) You may be curious to have a look at the old CTK Exchange archive.  