2
$\begingroup$

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?

1 Answers 1

2

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 $

  • 1
    This is probably because Binomial is approximated by Poisson for large $n$ with $\lambda=n \cdot \frac{1}{n}=1$ irrespective of $n$2012-11-01