# probability of loops for "secret santas" **URL:** \ **Category:** Factual Questions\ **Created:** [October 1, 2003, 10:50pm UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007 "2003-10-01T22:50:31Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![TJdude825](https://avatars.discourse-cdn.com/v4/letter/t/dec6dc/32.png) [@TJdude825](https://boards.straightdope.com/u/TJdude825)\ **Post date:** [October 1, 2003, 10:50pm UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/1 "2003-10-01T22:50:31Z")
Recently in my English class, we each had to write a poem about another member of the class (chosen at random, so it was kind of like the “secret santas” game which you may be familiar with) and then we presented them as follows: Student 1 volunteers, and reads his poem about Student 2. Student 2 then reads her poem about Student 3, and so on. Eventually we get to someone (say, Student 15) who wrote about Student 1. So we’ve made a 15-person loop, and now someone else has to volunteer. Nobody wrote a poem about himself, so there are no 1-person loops. For a class of 30 students, there could be one big 30-person loop, or there could be 15 loops of 2 people each. Or, there could be a loop of 10, two loops of 9, and a loop of 2. There are a lot of possibilities. I’m wondering, for a class of n students, how would you figure out the average number of loops and the expected size of the loops? In other words, if we did this whole poetry assignment hundreds of times, how often would we get one loop, two loops, three loops, etc. and how often would we get loops of 2 and 28 vs. 3 and 27 vs. 4 and 26, etc.? (Again, this example is assuming n is 30, but I’m curious if there’s a general formula) I don’t even know where to start on this. Any ideas? ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [October 1, 2003, 11:11pm UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/2 "2003-10-01T23:11:32Z")
Hmmm… interesting puzzle; a few observations: Everybody will be in a loop There can be no branches and mergers, dead ends or fresh starts in any of the loop paths. I haven’t a clue how to work out the likely distribution of loop sizes though. ---
**Author:** ![yabob](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/yabob/32/2821_2.png) [@yabob](https://boards.straightdope.com/u/yabob)\ **Post date:** [October 1, 2003, 11:57pm UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/3 "2003-10-01T23:57:16Z")
A place to start: All permutations, as this exercise illustrates, can be represented as a set of disjoint cycles (what you call “loops”). These are usually written in a notation something like this: (1 3 6)(2 5) ie, element 1 permutes to 3, 3 permutes to 6, and 6 back to 1. 2 is permuted to 5, and 5 back to 1. 4 is presumed to be fixed, or you could say (4). careful - some texts use slightly different notation for this, and some compose permutations left-to-right, some right-to-left when they discuss permutation multiplication. You have insisted that there are no fixed elements, so all such representations will involve sets of n numbers arranged within parentheses with no singletons. I would think first of counting possible patterns of parenthesized groups, then counting the ways to arrange the numbers within the patterns. There are some constraints on that last step - (1 3 5) is the same thing as (3 5 1), for instance, and (1 2)(3 4) is the same thing as (3 4)(1 2). You can insist that every cycle is represented with its lowest number first, and cycles of same length are specified in order of the lowest element to obtain a “canonical” form. Actually, just choosing distinct combinations of numbers for each set of parentheses takes care of the first consideration, and dividing by m! for each set of similar length cycles in a pattern takes care of the second. At the end of the day, this is such a messy counting problem that I’m sure I’m missing an easier way to do it. ---
**Author:** ![yabob](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/yabob/32/2821_2.png) [@yabob](https://boards.straightdope.com/u/yabob)\ **Post date:** [October 1, 2003, 11:59pm UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/4 "2003-10-01T23:59:09Z")
duh - in my first paragraph after the sample permutation I meant “5 back to 2”. ---
**Author:** ![Bippy\_the\_Beardless](https://avatars.discourse-cdn.com/v4/letter/b/ac8455/32.png) [@Bippy\_the\_Beardless](https://boards.straightdope.com/u/Bippy_the_Beardless)\ **Post date:** [October 2, 2003, 12:00am UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/5 "2003-10-02T00:00:22Z")
If we consider how the loops are formed and numbering the students by their location in the loop For 5 students, (x,y) where x is the student number and y is their poem’s students number. We can define the first student arbitrarily as (1,2) (1,2) leads to (2,3) 3/4 times leads to (2,1) 1/4 times and is a completed loop (1,2) + (2,3) leads to (3,4) 2/3 times leads to (3,1) 1/3 times and is a completed loop (1,2) + (2,3) + (3,4) leads to (4,5) 1/2 times leads to (4,1) 1/2 times and is a completed loop (1,2) + (2,3) + (3,4) + (4,5) leads to (5,1) and is a completed loop This would be a useable basis for a recursive function call to calculate all the loop probabilities. Since once a loop is completed the calculation can continue with the smaller set of remaining students. ---
**Author:** ![Bill\_H](https://avatars.discourse-cdn.com/v4/letter/b/a5b964/32.png) [@Bill\_H](https://boards.straightdope.com/u/Bill_H)\ **Post date:** [October 2, 2003, 12:15am UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/6 "2003-10-02T00:15:21Z")
First comment: pretty interesting poetry class, eh? Building on **Bippy the Beardless** ’s work: Suppose 30 people in the class. Person 1 picks a name (but it can’t be his own). Person 2 picks a name. What are the odds it is Person 1? I.e. that we have a loop? 1/29 Let’s say Person 2 doesn’t pick Person 1 (28/29 chance). What are the odds he’ll pick Person 1? 1/28. So, the cumulative probability of this happening (Person 2 doesn’t pick Person 1 AND Person 2 does pick Person 1) are 28/29 \* 1/28 = (conveniently) 1/29. Repeat for Person 3: The cumulative odds of: Person 2 doesn’t pick Person 1 (28/29) AND Person 2 doesn’t pick Person 1 (27/28) AND Person 3 does pick Person 1 (1/27) = (again conveniently) 28/29 \* 27/28 \* 1/27 = 1/29. And down the line. The odds of a two person chain are the same as the odds of a 30 person chain. Once a chain is formed, the same process applies for the remaining unchained pool. ---
**Author:** ![Bill\_H](https://avatars.discourse-cdn.com/v4/letter/b/a5b964/32.png) [@Bill\_H](https://boards.straightdope.com/u/Bill_H)\ **Post date:** [October 2, 2003, 12:20am UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/7 "2003-10-02T00:20:23Z")
Argh. fix that (same math and logic apply): > [@](#): > > Let’s say Person 2 doesn’t pick Person 1 **and instead picks Person 3** (28/29 chance). What are the odds **that Person 3 will** pick Person 1? 1/28. So, the cumulative probability of this happening (Person 2 doesn’t pick Person 1 AND Person **3** does pick Person 1) are 28/29 \* 1/28 = (conveniently) 1/29. > > Repeat for Person 3: The cumulative odds of: Person 2 doesn’t pick Person 1 (28/29) AND Person **3** doesn’t pick Person 1 (27/28) AND Person **4** does pick Person 1 (1/27) = (again conveniently) 28/29 \* 27/28 \* 1/27 = 1/29. ---
**Author:** ![wolf\_meister](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/wolf_meister/32/15202_2.png) [@wolf\_meister](https://boards.straightdope.com/u/wolf_meister)\ **Post date:** [October 2, 2003, 1:21am UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/8 "2003-10-02T01:21:23Z")
TJDude This is not the same as a “Secret Santa” drawing. For example, let’s say there are 4 people in a “Secret Santa” drawing. Person ‘A’ could choose ‘B’ and ‘B’ could choose ‘A’. Let’s say the same happens to ‘C’ and ‘D’. This is a successful secret Santa drawing but not a successful “loop” as to what you are trying to accomplish. Guess I came to this thread a little late but just thought I’d mention this. If you’d like to see exact probabilities for “Secret Santa” drawings, go to [http://www.1728.com/puzzle2.htm](http://www.1728.com/puzzle2.htm) and look at puzzle 26. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 2, 2003, 2:55am UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/9 "2003-10-02T02:55:21Z")
The question is: what’s the probability of having k connected components in a random graph with n vertices and n edges where every vertex is of degree 2? **RTFirefly** is our resident graph theory expert, so we’ll see if he shows up. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [October 2, 2003, 3:24am UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/10 "2003-10-02T03:24:58Z")
I knew this had to do with [Stirling Numbers of the first kind](http://mathworld.wolfram.com/PermutationCycle.html). I’d actually pontificate more but my copy of _Concrete Mathematics_ is not at hand. ---
**Author:** ![TJdude825](https://avatars.discourse-cdn.com/v4/letter/t/dec6dc/32.png) [@TJdude825](https://boards.straightdope.com/u/TJdude825)\ **Post date:** [October 2, 2003, 5:23am UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/11 "2003-10-02T05:23:24Z")
**wolf\_meister** , the only difference I can see between my random drawing, and the drawing in your link is that I didn’t have anything that said, “if you do draw your own name, then…” I just assumed that you wouldn’t draw your own name. Then the whole idea of “successes” in that problem is meaningless in this one. So they’re two different puzzles, but they use almost the same “secret santa” drawing process. If A chooses B, B chooses A, C chooses D, and D chooses C, this isn’t “no loop,” it’s just two different loops of two people each. Using **yabob** ’s notation, this is (A B)(C D). By the way, since I don’t really care about the answer as much trying to figure out how to get the answer, feel free to allow a student write about himself, if it makes the math easier. ---
**Author:** ![scm1001](https://avatars.discourse-cdn.com/v4/letter/s/c4cdca/32.png) [@scm1001](https://boards.straightdope.com/u/scm1001)\ **Post date:** [October 2, 2003, 9:50am UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/12 "2003-10-02T09:50:41Z")
Building on **Bippy the Beardless** ’s work: Suppose 30 people in the class. Person 1 picks a name (but it can’t be his own). Person 2 picks a name. What are the odds it is Person 1? I.e. that we have a loop? 1/29 Let’s say Person 2 doesn’t pick Person 1 (28/29 chance). What are the odds he’ll pick Person 1? 1/28. So, the cumulative probability of this happening (Person 2 doesn’t pick Person 1 AND Person 2 does pick Person 1) are 28/29 \* 1/28 = (conveniently) 1/29. Repeat for Person 3: The cumulative odds of: Person 2 doesn’t pick Person 1 (28/29) AND Person 2 doesn’t pick Person 1 (27/28) AND Person 3 does pick Person 1 (1/27) = (again conveniently) 28/29 \* 27/28 \* 1/27 = 1/29. And down the line. The odds of a two person chain are the same as the odds of a 30 person chain. Once a chain is formed, the same process applies for the remaining unchained pool. \*\* [/QUOTE] extending this analysis, it is clear that the probability of a loop X in a class of Y is (Y-2/Y-1)(Y-3/Y-2)…X-1 times e.g. for a loop 4 in 30 people it is 28/29x27/28x26/27. When this probability is 0.5 then this will be the average loop size for the largest ring note most of the factors cancel. So we are left with (Y-1)/(Y-X) = 0.5. When Y is large this means that X is about Y/2 or 15 for the above problem feel free to attack my answer as maths was only my second best subject ---
**Author:** ![scm1001](https://avatars.discourse-cdn.com/v4/letter/s/c4cdca/32.png) [@scm1001](https://boards.straightdope.com/u/scm1001)\ **Post date:** [October 2, 2003, 9:52am UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/13 "2003-10-02T09:52:22Z")
hmm I am having second thoughts about my answer. Will come back after a nap with a better answer ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 2, 2003, 3:27pm UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/14 "2003-10-02T15:27:28Z")
Actually, **ftg** gave what is necessary for the answer. All you need to do is generate all the permutations on n elements, and count the ones that have the cycle structure you’re interested in. But we can do one simpler and just generate partitions of n, and count the ones that have the interesting property. That’s a bit simpler. I don’t know the general formula, but I may be able to derive it from that. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 2, 2003, 3:33pm UTC](https://boards.straightdope.com/t/probability-of-loops-for-secret-santas/205007/15 "2003-10-02T15:33:04Z")
I should elaborate a bit. Let’s say we’ve got 15 people, and we want to know what the odds of getting 3 loops of 2 are. We subtract 2 from 15 three times, so that we’re now interested in the number of partitions of 11. Compute that, divide it by the number of partitions of 15, and you have your answer. There’s a slight wrinkle in that we’re interested only in partitions that don’t involve 1 (which would correspond to someone drawing their own name), but that’s not too bad to deal with.