Question

3. (Matching) A person types n letters that are to be sent to n distinct addresses, types the addresses on n envelopes, and then places each letter in an envelope in a random manner Fori .. , n, let Xi-1 if the ith letter is placed in the correct envelope and let Xi0 otherwise. (Hint: May look for answers in the textbook.) (a) What is the distribution of X,? (b) Are X, and X for i independent? (c) Define X -X X, to be the number of letters that are placed in the correct envelopes Find E(X), i.e., the expected number of correctly placed letters

Answer 1

We know different letters can be placed in envelopes in ways.

Let the event $A_i \textup{ or }\left ( X_i=1 \right )$ be the event that $i\left ( 1\leqslant i\leqslant n \right )$ -th letter is placed in the correct envelope. This can be done in $\left (n-1 \right )!$ ways.

Then

a) The cardinality $\left | A_i \right |=\left (n-1 \right )!;1\leqslant i\leqslant n$ . The distribution of $X_i$ is

$P\left ( A_i \right )=\frac{\left (n-1 \right )!}{n!}=\frac{1}{n}\\ P\left ( X_i =1\right )=\frac{1}{n}\\ P\left ( X_i =0\right )=1-\frac{1}{n}$

b) Generally, $\left |A_i\cap A_{i'} \right | =\left (n-2 \right )!;1\leqslant i,i'\leqslant n,i\neq i'$

$P\left ( A_i\cap A_{i'} \right )=\frac{\left (n-2 \right )!}{n!}=\frac{1}{n\left ( n-1 \right )},1\leqslant i,i'\leqslant n,i\neq i'\\ P\left ( X_i=1\cap X_{i'}=1 \right )=\frac{1}{n\left ( n-1 \right )},1\leqslant i,i'\leqslant n,i\neq i'\\$

Since

$P\left ( X_i=1\cap X_{i'}=1 \right )=\frac{1}{n\left ( n-1 \right )}\neq \frac{1}{n^2}=P\left ( X_i=1 \right )P\left ( X_{i'}=1 \right ),1\leqslant i,i'\leqslant n,i\neq i'\\$

$X_i$, and  $X_{i'} 1\leqslant i,i'\leqslant n,i\neq i'$ are not independent.

c) From part (a),

$E\left (X_{i} \right )=1\times \frac{1}{n}+0\times\left ( 1-\frac{1}{n} \right )\\ E\left (X_{i} \right )= \frac{1}{n}$

The expected value of$X=\sum_{i=1}^{n}X_i$ using the linearity of expectation is

$E\left (X \right )=\sum_{i=1}^{n}E\left (X_i \right )\\ E\left (X \right )=\sum_{i=1}^{n}\frac{1}{n}\\ E\left (X \right )=n\times \frac{1}{n}\\ {\color{Blue} E\left (X \right )=1}$