Question

Suppose thatnletters are placed at random innenvelopes, as in the matching problem of Sec. 1.10, and letqndenote the probability that no letter is placed in the correct envelope. Show that the probability that exactly one letter is placed in the correct envelope isqn−1.

Short answer

Exactly one letter placed in the correct envelope is \({q_{n - 1}}\).

Step-by-step solution

Given information

Given that\(n\)letters are placed at random in\(n\)envelopes.

Also,\({q_n}\)denote the probability that no letter is placed in the correct envelope.

Also, let \({q_{n - 1}}\) denote the probability that exactly one letter is placed.

State the condition

Let \({A_i}\) be the event that the letter is placed in the correct envelope \(\left( {i = 1, \ldots ,n} \right)\). Then \({q_n}\)is given by \({q_n} = pr\left( {\bigcup\nolimits_{i = 1}^n {{A_i}} } \right)\) .

Compute the probability

Here we use this theorem to solve is

\(pr\left( {\bigcup\nolimits_{i = 1}^n {{A_i}} } \right) = \sum\limits_{i = 1}^n {pr\left( {{A_i}} \right) - \sum\limits_{i < j} {pr\left( {{A_i} \cap {A_j}} \right) + \sum\limits_{i < j < k} {pr\left( {{A_i} \cap {A_j} \cap {A_k}} \right) + \ldots + {{\left( { - 1} \right)}^{n + 1}}pr\left( {{A_1} \cap {A_2}, \ldots , \cap {A_n}} \right)} } } \)

Since the letters are placed in the envelopes correctly at random, the probability\(pr\left( {{A_i}} \right)\)that any particular letter will be placed in the correct envelope is\(\frac{1}{n}\).

Then exactly one letter is placed in the correct envelope of probability is given by

\(\begin{aligned}{c}\sum\limits_{i = 1}^n {pr\left( {{A_i}} \right) = {q_{n - 1}}} \\{\rm{ = n \times }}\frac{{\rm{1}}}{{\rm{n}}}\\{\rm{ = 1}}\end{aligned}\)

Hence proving that exactly one letter is placed in the correct envelope is \({q_{n - 1}}\)