2
$\begingroup$

I have the following probability question, with two different solutions, and I would like to determine which one is right. Here is the problem:

$n$ balls are labeled $1$ to $n$, and $n$ boxes are also labeled $1$ to $n$. Now put these $n$ balls randomly into these $n$ boxes, such that each box contains only one ball. If a ball is in the box with the same number it has (e.g. ball #3 is in box #3), then we say that this ball is in the right box. Let $X$ be the number of balls that are in the right boxes, what is the expected value of $X$?

Here are the two solutions I have:

Solution 1: The probability that at least $k$ balls are in the right box is $$P(X\ge k)=\frac{\binom{n}{k}(n-k)!}{n!}=\frac{1}{k!},\quad k=0,1,2,\dots,n,$$ so the expected value of $X$ is

$$E(X)=\sum_{k=0}^n P(X\ge k)=\sum_{k=0}^n\frac{1}{k!}.$$

Solution 2: For $j=1,\dots,n$, let $X_j$ be the random variable such that $$X_j=\begin{cases}1, &\text{if ball }\#j\text{ is in the right box},\\ 0, &\text{otherwise},\end{cases}$$ Then we have $X=\sum_{j=1}^n X_j$. For each $j=1,\dots,n$, we have $$P(X_j=1)=\frac{(n-1)!}{n!}=\frac{1}{n},$$ therefore, $$E(X)=\sum_{j=1}^n E(X_j)=1.$$

From my instinct, I feel that the first solution is the right one, but I cannot tell what is wrong with the second solution (Maybe I am wrong?). Any suggestions would be greatly appreciated!

Edit: Now I've figured out that the second one is right. The problem with the first one is that the relation $P(X\ge k)=\frac{\binom{n}{k}(n-k)!}{n!}$ is incorrect, and thus caused the wrong answer.

$\endgroup$
4
  • 1
    $\begingroup$ The second is the correct one. I don't quite get the probability calculation in the first. It is impossible to have only one incorrect, so $P(X=n-1)=0$, and your probability is not compatible with that. $\endgroup$ Nov 1, 2022 at 8:57
  • $\begingroup$ $P(X\ge 1)\neq\frac{1}{1!}=1$ $\endgroup$ Nov 1, 2022 at 8:58
  • $\begingroup$ @JaapScherphuis I see, this makes sense. Thanks! $\endgroup$
    – Frank Lu
    Nov 1, 2022 at 9:00
  • $\begingroup$ @DanielMathias Thanks. Now I see where the mistake is. $\endgroup$
    – Frank Lu
    Nov 1, 2022 at 9:00

1 Answer 1

1
$\begingroup$

The second solution is the right one. What was your thinking process when claiming that $\mathbb{P}(X \ge k) = \frac{{{n}\choose{k}} (n-k)!}{n!}$ ?

$\endgroup$
5
  • $\begingroup$ $n!$ is the total number of combinations. Now assume that at least $k$ balls are in the right box, this means in particular, $k$ balls are in the right box, and that's where the factor $\binom{n}{k}$ came from. Now for the rest of the $(n-k)$ balls, they are permuted in any order (in the rest of the $(n-k)$ boxes), and this gives the factor $(n-k)!$. This was the initial thought. $\endgroup$
    – Frank Lu
    Nov 1, 2022 at 9:07
  • $\begingroup$ @FrankLu With that counting method, many cases are overcounted. For example, if k=1 and there are actually two correct balls, then either one of the correct balls can be the chosen correct one with the other being part of the n-1 remaining "don't care" balls. $\endgroup$ Nov 1, 2022 at 9:27
  • $\begingroup$ ok @FrankLu. But at least means either k or k+1 or k+2 or ... or n. Then when dealing with the case "k ball are in the right box" you omit several cases $\endgroup$
    – user1077509
    Nov 1, 2022 at 9:38
  • $\begingroup$ @JaapScherphuis You are right, this is where the problem arises. $\endgroup$
    – Frank Lu
    Nov 1, 2022 at 10:09
  • $\begingroup$ @ChristianYeo Right, I messed up with counting those cases. $\endgroup$
    – Frank Lu
    Nov 1, 2022 at 10:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .