-1
$\begingroup$

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$

  • 0
    $S_n$ is the number of fixed points of a random permutation, and so it's approximately distributed Poisson (with mean 1).2010-11-15
  • 0
    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: http://mathworld.wolfram.com/Derangement.html2010-11-15

2 Answers 2

2

Please note:

  • 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}$

1

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$