Sign up ×

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?

share|cite|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|cite|improve this answer
@Jonathan Christensen I voted to deleted my post. But I repost your good comment. The following is a comment from Jonathan Christensen: This page gives a sum representation, and Mathworld gives another form. Edit: The first page also says the expected value is always 1, irrespective of n. – Nicolas Essis-Breton Nov 1 '12 at 1:56
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

Your Answer


