0
$\begingroup$

Given $n$ blue letters and $n$ pink letters (in total $2n$ letters) to place in $n$ envelopes. on each envelop there's an address written, and the letters also have $n$ different addresses. In each envelope we randomly choose 2 letters - 1 pink and 1 blue.

Let $X$ be the number of envelopes which has at least one correct letter in them. what is the Expected value of $X$?

I understand that if we have $n$ letters, then $E[X] = n\cdot \frac{1}{n} =1$

I want to find the probability of putting 2 correct letters in an envelope, and to use the Complement of it to find the probability of at least 1 correct letter, but the probability for the $j$-envelope is depended on the previous $j-1$ envelopes and this is where I get lost.

$\endgroup$
1
  • $\begingroup$ Hint: You may want to use the derangements tag for this question. $\endgroup$
    – Vectorizer
    Commented Jan 25, 2020 at 16:34

1 Answer 1

3
$\begingroup$

We can use linearity of expectation here. Let $X_i$ be $1$ or $0$ according to whether the $i$-th envelope has at least one correct letter in it or not.

Then $E[X_i]=P($ at least one correct letter in envelope $i)=\frac1n+\frac1n-\frac{1}{n^2}$ (Using inclusion-exclusion on pink letter correct or blue letter correct.)

We're interested in $E[X_1+\cdots+X_n]$. But by linearity of expectation this is equal to

$E[X_1]+\cdots+E[X_n]=n\cdot \left( \frac1n+\frac1n-\frac{1}{n^2}\right)=2-\frac1n$

$\endgroup$
2
  • $\begingroup$ isn't $P(X_i)$ depended on the results of the previous envelopes? I mean, if we put the wrong letter in the wrong envelope, doesn't that change the probability for putting a correct letter in an envelope that we've already used? $\endgroup$
    – Noa Even
    Commented Jan 25, 2020 at 17:02
  • 1
    $\begingroup$ @Jneven: This temporal perspective on the problem is not useful. If you work out the entire temporal sequence, with all possible combinations of previously chosen wrong or correct letters, you'll find that later envelopes have the same probability as the first envelope; but there's no need to go through those motions, since this is the case by symmetry. (By the way, you wrote in the question that you understand the case of a single set of $n$ letters. The same symmetry considerations that you applied there also apply in the case of two sets of letters.) $\endgroup$
    – joriki
    Commented Jan 26, 2020 at 7:10

You must log in to answer this question.

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