If eight people participate in a Secret Santa gift exchange, what is the probability that the gift-giving will form a loop?

I am not sure, please check it.

As I see it, giving gifts can be seen as arrangements. We can then use permutations and combinations. To find the probability, we need sample space and an event.

[] [] [] [] [] [] [] []

There are 8 slots (above). The 8 slots are 8 persons.

The sample space consists of any person giving gift to any other person. So, if we choose 1 person (out of 8)(8C1), s/he can give a gift to anyone from remaining 7 (7P7).
Sample space = 8C1 * 7P7 = 8 * 5040 = 40320 number of ways (=8P8).

In our event, the left-most person gives gift to their immediate right one, s/he in turn to their immediate right one, until we reach the last one to the right. The last one gives the gift to the first (left-most) person/slot. This completes the loop.
Event = 8C1*7C1 + 1C1*6C1 + 1C1*5C1 + 1C1 * 4C1 + 1C1*3C1 + 1C1*2C1 + 1C1*1C1 + 1C1*1C1 = 78.
(Each of these terms refer to one person giving a gift to another in your example. Here’s it is.
1 gives to 4
4 gives to 6
6 gives to 3
3 gives to 8
8 gives to 2
2 gives to 7
7 gives to 5
5 gives to 1)

Probability = n(Event) / n(Sample Space) = 78 / 40320 = 0.001935 or 0.1935 % (approximately 0.2%).

It’s still May….

Check me on this…

The first person has 7 choices (anybody but himself).
The recipient of that gift has 6 choices, if we are to form a loop. He can’t give to himself, he can’t give to anybody who has already received a gift (which is just himself), and he can’t give to the person who gave him the gift or we would not end up with a large loop. A total of 2 off limits people.
The next recipient cannot give to himself, anybody who has already received a gift (himself and his giver), nor the first giver. 5 choices.
It will continue on as such until the 7th person. At this point, 6 people will have received gifts. However, of the two remaining, he can only give to one of them if we are to form a loop – the giver of the first present is reserved for the last person. Just 1 choice.
And the eighth person also has just one choice, he must complete the loop by giving to the first giver.

The total number of ways to form the loop is 7!. This is our numerator.

The total number of ways to complete a secret santa without the loop restriction is our denominator.

The first person has 7 choices, anybody but himself. He removes his choice from the hat and the next person draws.
The second person has 6 choices, anybody but himself. And so on.
The trouble is that we might get down the last person and the only name left in the hat is himself…

Yikes, give me some time to think about this denominator. I’m going to have to politely disagree with @prasad on the denominator – you have not accounted for the possibility of giving multiple gifts to the same person.

As for your last question, I think the probability will diminish as n increases. The probability is 1 for n = 2 or n = 3. It obviously has to drop off from there.

Okay, I think I know how to go about it now.

The most understandable way (for me) to count the number of legal secret santa possibilities is to assume the picking process starts over if anybody draws their own name. This is what a lot of people choose to do anyhow, as it gives away some info about who someone’s secret santa is if they see their own name at any time.

So, if we want the final outcome to be legal, we can assume there are 7 possibilities for the first person – everybody but himself. Picking himself would result in starting over.
The problem branches. When the second person picks, he may either have 7 choices or 6. This depends on whether it was his name drawn by the first person, which is a 1/7 possibility. So his number of choices can be represented as 7*1/7+6*6/7.
If the third person’s name has already been chosen, there are 6 remaining possibilities – everybody except him and the other person whose name has been drawn. Otherwise, there are 5. I think his chances of having already been drawn are 1/7+1/(7*1/7+6*6/7).

As you can see it starts getting very convoluted and very branchy quickly. Doesn’t seem quite right, does it? I would have thought the generalized secret santa (denominator) would be easier than your specific example of a loop (numerator) but it’s not turning out that way.

I’m thinking of writing a computer program to simulate this to back up my calculations.

Maybe I misunderstand the question, but it seems like it’s 100% probable because that’s the way it has to work.
The “loop” is just the fact that no matter what party you start with giving to another, somebody will draw a ticket to give that person a gift. Unless somebody is left out of the draw there will always be a sequence from one person, through the whole group, ending with the original person.

@dabbler There is not always going to be a sequence that goes through the whole group. For example:
1–2
2–3
3–4
4–1
5–6
6–7
7–8
8–5

This forms two distinct loops.

Oh! I see what you mean. whoosh! right over my head thanks!
In that case I think @prasad‘s analysis is correct, it’s a combinatorial problem.