The matching problem - placing $n$ letters into $n$ envelopes randomly - the meaning of the sum of $\operatorname{Pr}(A_i)$.

The matching problem

A person types $$n$$ letters, types the corresponding addresses on $$n$$ envelopes, and then places the $$n$$ letters in the $$n$$ envelopes in a random manner. What's the probability that at least one letter will be placed in the correct envelope?

This is a worked example from the book Probability and Statistics 4th Edition By Morris H. Degroot, p.49, and I'm reading the solution. It says let $$A_i$$ be the event that letter i is placed in the correct envelope ($$i = 1, . . . , n)$$, so the probability $$Pr(A_i)$$ that any particular letter will be placed in the correct envelope is $$1/n$$. I can understand this, because there is only one correct envelope among n envelopes.

But I can't grasp this: $$\sum_{1}^{n}Pr(A_i) = n\cdot(1/n) = 1.$$

As it says the probability = 1, does it mean it's certain that either letter 1 or 2 or 3... or n will be placed in the correct envelope? I tried with $$n = 2, 3, 4$$ and always found that there are arrangements when none of the letters were placed correctly in their envelopes.

Thank you.

• I don't see what the book is trying to say here. That statement is certainly true, but it doesn't have very much to do with the question unless they're trying to use the principle of inclusion and exclusion. Commented Sep 28, 2023 at 7:20
• Yes, it's trying to use the principle of inclusion and exclusion. I'm a beginner of probability, so forgive me if I'm asking a too basic question. What confuses me is why it's certain that either letter 1 or 2 or 3... or n will be placed in the correct envelope? (As it says the sum of Pr(Ai) = 1). Thank you. Commented Sep 28, 2023 at 7:31
• I believe what it is trying to say is that the expected number of letters in the correct envelope is $1$, although the notation is murky. Commented Sep 28, 2023 at 8:12

In this context the equality:$$P(A_1)+\cdots+P(A_n)=1$$is correct but does not tell us that it is for certain that some letter is placed in the right envelope.

For that we need:$$P(A_1\cup\cdots\cup A_n)=1$$which is false in this context.

The two expressions on LHS do not have the same value. They would have the same value if the events would have been mutually exclusive but that is evidently not the case here.

Applying the principle of inclusion/exclusion and symmetry we can find an expression for the second expression. I suspect strongly that this will be handled in the book you mention.

• Thank you. Now I understand it. So the sum of the probability of a number of events in a sample space can even be greater than 1 and all the outcomes from those sets may not fill up the space. Commented Sep 28, 2023 at 11:58
• Yes, that surely is possible. You are welcome. Commented Sep 28, 2023 at 12:03

This is an example of linearity of expectation. For a Bernoulli random variable $$X$$, we have $$E[X]=0\cdot P[X=0]+1\cdot P[X=1]=P[X=1].$$ Let Bernoulli random variable $$X_i$$ indicate whether letter $$i$$ is placed correctly. Then the expected number of correctly placed letters is $$E\left[\sum_{i=1}^n X_i\right] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n P[X_i=1] = \sum_{i=1}^n P[A_i] = \sum_{i=1}^n \frac{1}{n} = n\cdot\frac{1}{n} = 1.$$

• I assume the question was about the sum of probabilities, not about the expected number of letters placed into correct envelope.
– user
Commented Sep 28, 2023 at 15:16
• My answer is intended to provide an interpretation for the sum of probabilities. Commented Sep 28, 2023 at 15:28