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.

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

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.