# How would I find $E(M)$?

There are $n$ balls labeled 1 through $n$, and $n$ boxes labeled 1 through $n$. The balls are distributed randomly into the boxes, one in each box, so that all $n!$ permutations are equally likely. Say that a match occurs at place $i$ if the ball labeled $i$ happens to fall in the box labeled $i$. Let $M$ be the total number of matches. How would I find the expected value of M? I know that the probability of a match is $\frac1n$. And since the values that can be taken on are discrete I want to do $$\sum_{j=1}^nx*\frac1n$$ but I don't know what to do for $x$ here. Any suggestions?

-

Think about this in the following way: $M$ takes values between $0$ and $n$. To have 0 matches each ball has to land in the wrong box, hence: $$P(M=0)=\bigg(1-\frac{1}{n}\bigg) \cdot \bigg(1-\frac{1}{n} \bigg)\ldots \bigg(1-\frac{1}{n} \bigg) \approx e^{-1}$$ for large $n$. To get 1 match, exactly one of the balls has to land in the right box, the rest in the worng (it does not matter which. of course): $$P(M=1)=\frac{1}{n} \bigg(1-\frac{1}{n} \bigg)^{n-1}+\frac{1}{n} \bigg(1-\frac{1}{n} \bigg)^{n-1}+ \ldots+\frac{1}{n} \bigg(1-\frac{1}{n} \bigg)^{n-1}=\binom{n}{1} \frac{1}{n}\bigg(1-\frac{1}{n} \bigg)^{n-1}$$ Do you see the pattern? At the end, the mean number of successes is $$\mathbf{E}M=\sum_{k=0}^{n}k\binom{n}{k}p^{k}(1-p)^{n-k}$$ where $p=\frac{1}{n}$, which is the expectation of the Binomial RV with parameters $n,p$, hence $$\mathbf{E}M=np=1$$
This is probably because Binomial is approximated by Poisson for large $n$ with $\lambda=n \cdot \frac{1}{n}=1$ irrespective of $n$ – Alex Nov 1 '12 at 1:59