Derangement without replacement

Question

Each of $n \geq2$ people puts his or her name on a slip of paper (no two have the same name). The slips of paper are shuffled in a hat, and then each person draws one (uniformly at random at each stage, without replacement). Find the average number of people who draw their own names.

Does this match the pattern of derangements? I can't wrap my head around the fact that this does not allow replacement.

EDIT 2:

Adding to the comment of @drhab.

The probability that the first person draws his own name is $\frac1n$. By symmetry, anyone could be the first person. So,

$$P[X_i] = \frac1n.$$

And summing over $n$ (linearity of expectation), I get $1$.

Is my approach correct? I am not super confident. I am trying to self-study probability using Blizstein's lectures and book, and I keep getting stuck in most of the questions.

Answer 1

A derangement is a permutation of a set of distinct objects such that no object ends up in its original position. In this case, shuffling the names and having each person draw one is a permutation. A derangement would be no person drawing their own name.

The average number of people who draw their own name can be found the following way:

Consider the $(m+1)$th person out of $n$. What is the chance they draw their own name, given their name one of the $n-m$ still in the hat? What is the chance their name has not already been one of the first $m$ drawn out of the hat? Multiply these together and you get the probability the $(m+1)$th person draws their own name. Then sum the products over all $n$ people and you get the average number who draw their own name.

Answer 2

Hint:

For $i=1,\dots,n$ let $X_i$ take value $1$ if person $i$ draws his own name, and let it take value $0$ otherwise. Then if $X$ denotes the number of persons that draw their own names: $$X=X_1+\cdots+X_n$$ Now find $\mathbb EX$ by means of linearity of expectation and symmetry.