Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|cite|improve this question
    
$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
up vote 2 down vote accepted

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

share|cite|improve this answer

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$

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.