Thread: Probability / odds of last person drawing their own name from a hat

Hi... I'm an English teacher, and just did an exercise with my 6th graders - Secret Santa. But in my version, kids don't all draw names at the same time, everyone does it one at a time. The question I have is, what is the probability of the *last* student drawing their own name from a hat?

If there are 12 students, 12 names in the hat, each student draws one name, in turn, and checks to be sure it's not their own, and if it is, they throw it back and pick again. Then the next student draws. However, in my exercise, no student draws their own name, until the very last student. Therefore the whole game has to be restarted. What were the odds of that happening? If possible, can you give it to me in a "1 in 1,000,000,000" type of answer? or explain how I can convert a decimal number to odds format?

And I would like to add... I'm not a math student - and I'm now 20+ years outside of university, so my ability to solve equations that you give me may be limited. Please don't bash me as I've seen in other threads. I've come here to the experts in a field to answer a curious question I have. That's all it is. If this isn't the right place, kindly point me in the right direction.
Thank you kindly

Hey HKJason.

So just to clarify, are you finding the probability that everyone picks out the correct name and thus everyone gets their name and puts it back in the hat?

Hmm. not really.

12 Students in a class - Each has to get a present for one of their classmates, in secret. So we put 12 names into a hat, and each student, in any order, picks one name, looks at it, and if it's not their own name (can't give a present to yourself), they keep the name and go and buy a present for them. If it is their own name, they just toss it back in the hat, and select again.

So in theory, with an even number of students, everyone gets a present. Given the way they select their names, everyone should get a name that is not theirs - except the last student *could* possibly be left getting their own name - and since they can't throw it back in, we have to do the whole thing over again! That's what happened. I want to know the odds of that happening... The first 11 students didn't select the 12th student's name, leaving the 12th student with his own name in the hat.

example, for 3 students:

1st possibility:
A picks B (there are three to choose from)
B picks C (only two names left)
C picks A (it's the only one left) -> this 'game' was successful.

2nd possibility:
A picks C
B picks A
C picks B -> another successful outcome.

3rd possibility:
A picks B
B picks A
C picks C -> unsuccessful -- so the game has to start over. <- odds of this... but for 12 students

So basically you want the odds of the last person getting their own name given that everybody else got a different name?

That sounds like a nice succinct way to say it! thanks :-)

What I can do is simulate the process happening about 50,000 times and get a probability for that particular event happening.

This is a common technique for complex problems that don't have a nice or easy analytic solution.

Do you want to give it a try later on (not right at this moment)?

Sure! Thank you very much for your time on this! I'm not in a rush...

Hi HKJason,

I wrote a program (using the Python programming language) which worked through all the possibilities and computed the probability that the last person draws his own name, with the result that the probability is 0.0650929. My program is not a simulation, like that proposed by chiro, but rather a computation; it doesn't draw any random numbers. It takes about 1.5 minutes to run on my PC, however, so I'm glad you don't have more students, because the run time is more or less exponential in the number of students.

I've tried to come up with a pencil and paper solution but have not been successful so far. The bit about not drawing your own name (unless you are the last to draw) makes computation tricky.

No "the bit about not drawing your own name" does NOT make it tricky. No matter how the first n-1 names are given out, the whole problem here is to determine the last name left in the hat being the name of the last student to pick.

If there are n names in the hat then the probability of any one name being the last left in the hat is 1/n. And the probability of any one out of n students being the last to pick is also 1/n. The probablility that the last name left in the hat is the name of the last student to pick is [itex](1/n)(1/n)= 1/n^2[/itex].

If there are 20 students the probability the last student will get his own name is 1/400.

Hi HKJason,
As you computed, for 3 students the probability that you must start over is 1/3. Of course, this does not agree with the last answer of HallsOfIvy, I believe his solution neglected to take into account that the pairings of the students do not have a student paired with himself. Here's my solution:

Wow, thank you everyone, for the effort you put into this. I appreciate it.

It is interesting, however, that I end up with 3 different answers so far....

Since we have three different answers so far, I propose to consider the case where there are only 4 students in detail in order to illustrate what I think is a correct method of solution. For simplicity let's suppose the students are numbered 1 through 4, and the names in the hat are actually their numbers.

As already noted by johng, there are only two possible sequences in which student 4 gets stuck with his own number: 2-3-1-4 and 3-1-2-4; anything else violates the rule that a student (other than student 4) can't draw his own number. We will compute the probabilities of each of these two sequences.

In order to draw 2-3-1-4, student 1 must first draw a 2, with probability 1/3. (Remember that he can't draw a 1, so there are only 3 possibilities.) Student 2 must then draw a 3, with probability 1/3 since the hat contains {1,3,4}, all of which are "legal". Student 3 must then draw a 1 with probability 1/2 since the hat now contains {1,4}, all of which are allowed. Student 4 is then stuck with a 4. So the probability of 2-3-1-4 is (1/3)(1/3)(1/2).

In order to draw 3-1-2-4, student 1 must draw a 3, with probability 1/3. Student 2 must then draw a 1, with probability 1/2, since the hat now contains {1,2,4} but he can't draw a 2. Student 3 must then draw a 2, with probability 1/2 since the hat now contains {2,4}. Student 4 is stuck with a 4. So the probability of 3-1-2-4 is (1/3)(1/2)(1/2).

Putting these two results together, the probability that student 4 is stuck with his own number out of the hat is


The difficulty of expanding this method to larger numbers of students is that the number of cases that must be considered (here only two) expands exponentially with the number of students. It's not hard to see that the number of possible sequences for n students is D(n-1), the number of derangements of n-1 objects. For 12 students, we have D(11) sequences, which is over 14 million but is feasible on a modern PC. Working the problem for 24 students by this method is clearly not feasible. So for larger numbers of students, I think the best idea so far is chiro's recommendation of using a simulation to get an approximate result. I've used simulation to check my answers for 4 and 12 students, and the simulation agrees well with the numbers computed by the "exact" method. Maybe someone will find a shorter computation, but I haven't seen one posted yet which I think is correct.

[edit] More information on derangements can be found here: Derangement - Wikipedia, the free encyclopedia [/edit]

Originally Posted by awkward

probability is approx 0.1389

I think the best idea so far is chiro's recommendation of using a simulation to get an approximate result. I've used simulation to check my answers for 4 and 12 students, and the simulation agrees well with the numbers computed by the "exact" method.

Excellent! Just so I'm clear, the simulation method for 12 students shows a .1389 (or approx) probability as well?

Thanks for the tip on the derangements. It seems that is what I'm after. I either forgot about them, or didn't cover them in Uni...

Originally Posted by HKJason

Excellent! Just so I'm clear, the simulation method for 12 students shows a .1389 (or approx) probability as well?

Thanks for the tip on the derangements. It seems that is what I'm after. I either forgot about them, or didn't cover them in Uni...

No, my simulation for 12 students shows a probability of about 0.065, which is in agreement with the calculation of 0.06509.

0.1389 is the probability for 4 students.

If anyone is interested, here is my Python program for computing the probability for the case of 12 students. To change the number of students, all that's necessary is to change the first line, currently reading "N = 12".

The students are numbered from 0 to 11, since that seems a little more natural in Python. The hat is represented by a Python "set". The program prints out the probability that the last student gets stuck with his own number from the hat.

Warning: this program can take a long time to run, as described in a previous post.

Code:

N = 12  # number of students
pN = 0  

# student i draws from the hat
# the probability of getting to this point is p
def draw(i, hat, p):
    global pN
    if not ((N-1) in hat):
        return
    if i == N-1:
        pN += p
        return
    if i in hat:
        nchoices = len(hat) - 1
    else:
        nchoices = len(hat)
    for j in hat:
        if i != j:
            draw(i+1, hat - set([j]), p / float(nchoices))

hat = set([i for i in range(N)])
draw(0, hat, 1.0)
print pN