Secret santa probability

Question

1. 26 people put their name in a hat.
2. Each person picks a name out of the hat to buy a gift for.
3. If a person picks out themselves they put the name back into the hat

What is the probability of the last person picking themselves?

I only ask this because it just happened!!

Answer 1

After the first $25$ people have picked names, there are two possibilities:

$\bullet$ We have a derangement of the first $25$ names, in this case the last person picks his own name.
$\bullet$ The last person picks the name of another person, and then we get a derangement of all names.

The number of derangements of $n$ objects is equal to $\left[ \frac{n!}{e}\right]$ (see link), so the probability of the last person picking his own name is equal to $$\frac{\left[ \frac{25!}{e}\right]}{\left[ \frac{25!}{e}\right] + \left[ \frac{26!}{e}\right]} = \frac{5706255282633466762357224}{154068892631103602583645049} \approx \frac{1}{27} - 2.4 \cdot 10^{-28}$$

Answer 2

I do not have an exact answer, but a Monte Carlo approach shows that the probability that the last person picks his own name is approximately 0.03351 (95% confidence interval 0.03316 to 0.03386).

It would be a mistake to simply count the possible sequences of draws and divide the number of cases in which the last person picks his own name by the total number of sequences, as in Arthur's proposed solution. The reason is that the sequences are not all equally likely. For example, in the case of three people, the first person may draw 2 or 3, each with probability 1/2. If he draws a 2, the second person may draw a 1 or 3, each with probability 1/2. But if the first person draws a 3, the second person must draw a 1. So the sequences (2,1,3) and (2,3,1) each have probability 1/4, while the sequence (3,1,2) has probability 1/2.

Here is a Python function which simulates the process. The persons are numbered from 0 to npersons-1 for programming convenience. (The version of Python used was 2.7.1).

import random

def draw_gifts(npersons, ntrials):
    "Simulate drawing gifts with npersons, ntrials times; return number of failures"
    nfail = 0
    for t in range(ntrials):
        hat = [i for i in range(npersons)]
        for i in range(npersons-1):
            # person i draws from the hat
            # hat[0]..hat[i-1] contain numbers already drawn
            # hat[i]..hat[npersons-1] contain eligible numbers
            j = random.randint(i, npersons-1)
            # redraw if necessary
            while hat[j] == i:
                j = random.randint(i, npersons-1)
            temp = hat[i]
            hat[i] = hat[j]
            hat[j] = temp
        if hat[npersons-1] == npersons-1:
            nfail += 1
    return nfail    

If the random number generator seed is first set to 1234 via "random.seed(1234)" and the function above is invoked via "draw_gifts(26, 1000000)" (simulating 26 persons and 10^6 trials), the returned number of failures, i.e. cases in which the last person draws his own number, is 33508. A standard statistical formula for a confidence interval on proportions, based on a Normal approximation, yields a 95% confidence interval of 0.03316 to 0.03386 for the probability of failure. See http://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval.