Take the 2-minute tour ×
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.

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|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
    
@Yuval: there was a consensus on the meta.math.SE to not speculatively tag postings as [homework]. That you might be personally convinced it "looks like homework" is not sufficient information for tagging of multiple such postings as homework. –  T.. Nov 15 '10 at 7:16
    
@T.: I think "using (a) and (b)" gives it up. –  Yuval Filmus Nov 15 '10 at 20:03
    
@Yuval: no disagreement, but to avoid speculation or back-and-forth interrogation (often somewhat hostile) of the question posters, I think it would be better to mark such indicators as [task] or [specified-method] or similar objective tags that are "computable from the question" without input from the OP. These tags don't exist at the moment but would avoid much of the negative, speculative, identification/interrogation cycle around supposed homework problems. –  T.. Nov 15 '10 at 20:27
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

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.