# Suppose that n people have their hats returned at random, find the following

Let $X_{i} = 1$ if ith person gets his or her own hat back and $0$ otherwise. Let $S_{n} = \sum_{i=1}^{n}X_{i}$, then $S_{n}$ is the total number of people who get their own hats back. Show that:

a) $E(X_{i}^{2}) = \frac{1}{n}$

b) $E(X_{i}.X_{j}) = \frac{1}{n(n - 1)}$ for $i\neq j$

c) $E(S_{n}^{2}) = 2$ (using (a) and (b)).

d) $var(S_{n}) = 1$

-
$S_n$ is the number of fixed points of a random permutation, and so it's approximately distributed Poisson (with mean 1). – Yuval Filmus Nov 15 '10 at 3:51
If $S_n = 0$ (nobody gets their own hat back) then you have what's called a derangement. There are lots of interesting results about derangements. For instance, $P(S_n = 0)$ rapidly approaches $\frac{1}{e}$ as $n$ increases. If $D_n$ is the number of derangements on $n$ elements then $D_n$ satisfies the nice recurrence relations $D_n = (n-1)(D_{n-1} + D_{n-2})$ and $D_n = nD_{n-1} + (-1)^n$. For more information and references see MathWorld's entry on derangements: mathworld.wolfram.com/Derangement.html – Mike Spivey Nov 15 '10 at 5:22

• a) $X_{i}=1$ probability $\frac{1}{n}$ and 0, otherwise. Thus $X_{i}^{2}=1$ with probability $\frac{1}{n}$ and 0, otherwise, which implies $E(X_{i}^{2})=\frac{1}{n}$

• b) The probability that both $X_{i}$ and $X_{j}$ are 1 is $\frac{1}{n(n-1)}$ (Why?)

• c) $E(S_{n}^{2}) = \sum\limits_{i} E[X_{i}^{2}] + \sum\limits_{i}\sum\limits_{j \neq i} E[X_{i}X_{j}= n \cdot \frac{1}{n} + n(n-1) \cdot \frac{1}{n(n-1)}$

• d) $Var(S_{n}) = E[S_{n}^{2}] - (E[S_{n}])^{2}$

-

I'll give some hints:

1) Notice that $X_i^2 = X_i$, since $X_i$ is $0$ or $1$. Then, $E X_i = 0 \cdot \mathrm{P}(X_i=0) + 1 \cdot \mathrm{P}(X_i = 1) = \mathrm{P}(X_i = 1)$. What is this probability?

2) Again, $X_i X_j$ is $0$ or $1$. Notice that $X_i X_j = 1$ if and only if person $i$ gets their hat AND person $j$ gets their hat. What is the probability of this? Let $A$ be the event person $i$ gets his hat and $B$ be the event person $j$ does. Then

$$\mathrm{P}(X_i X_j = 1) = \mathrm{P}(A \cap B) = \mathrm{P}(A) \mathrm{P}(B|A)$$

What are $\mathrm{P}(A)$ and $\mathrm{P}(B|A)$?

3) After some algebra,

$E S_n^2 = E(\sum_{i=1}^n X_i )^2 = E(\sum_{i=1}^n X_i^2 + \sum_{i \neq j} X_i X_j)$

Distribute the $E$ through. Use 1) and 2). How many ways can $i \neq j$?

4) $\mathrm{Var} S_n = E S_n^2 - (E S_n)^2$

-