Hey, recently got a brain teaser with an unexpected result and am looking for clarification...
The question was "if you write ten letters and place them into envelopes at random how many letters on average would end up in the right envelopes?"
The answer given was 1 and was calculated "independently and identically distributed" with no autocorrelation but I'm not sure that is correct. I thought autocorrelation would apply here and that would alter the outcome. I though "independently and identically distributed" was more for calculating probability of say a dice rolling a 6 as there is always an equeal chance.
Please Help.

The way around it would be to find the probability of getting all the different outcomes.

1. No letter match their envelope.
2. 1 letter only matches its envelope.
3. 2 letters only match their envelope.
.
.
9. 8 letters only match their envelope.
10. All letters match their envelope.

Then, the expectation would be:
0 multiplied by 1st probability,
1 multiplied by 2nd probability,
2 multiplied by 3rd probability,
3 multiplied by 4th probability,
.
.
8 multiplied by 9th probability,
10 multiplied by 10th probability.

Having 9 letters in the envelope correct is not possible, since the last letter has to be in the correct envelope :)

Then you add all those 10 products.

Expectation = \Sigma(n \ \times \ Probability)

The hard part is coming up with the individual probabilities. Calculating the probability that all 10 are correct is easy, but the others are a lot more difficult.

However, if you simplify the problem to only 2 letters into 2 envelopes it's trivial to write out all possible combinations. What you find is that the expected value is indeed 1, since 1/2 x 0 + 1/2 x 2 = 1. Then try it with 3 letters into 3 envelopes, and you get an expected value of 1: 2/6 x 0 + 3/.6 x 1 + 1/6 x 3 = 1. And then try it with 4 letters into 4 envelopes: 0/24 x 0 + 8/24 x 1 + 6/24 x 2 + 1/24 x 4 = 1.

Hmm, seems like a pattern is developing! This certainly is not a proof, but it makes you think that it's probably true for any number N letters and N envelopes.

Follow up - one way to prove that the expected value is always 1 is through an inductive proof. Show that its's true for the case of n = 1 (one letter and one envelope, which is trivial), then show that that if it's true for the case n=k it's also true for the case n=k+1.

If we define N(n,c) as meaning the number of ways that c letters can be arranged correctly into n envelopes, and P(n,c) is the probability of c correct letters in n envelopes, then P(n,c) = N(n,c)/n!, and we can show that P(n+1,c+1) = P(n,c)/(c+1). Here's why: given c are correct in a sample of n, there are C(n,c) ways for those c letters to be arranged into the correct envelopes, and there are N(n-c, 0) ways for the remaining n-c letters to all be placed into incorrect envelopes. So N(n,c)= C(n,c )*N(n-c,0). And the probability is P(n,c) = N(n-c,0) *C(n,c)/n!. For n+1 letters the probability of c+1 being placed correctly is:

P(n+1,c+1) = N(n+1-(c+1),0)*C(n+1,c+1)/(n+1)! ={ N(n-c,0)*C(n,c)*(n+1)/(c+1)}/{(n+1)*n!}
= P(n,c)/(c+1).

To show that this works here's an example: if N=3 then P(3,0) = 1/3, P(3,1) = 1/2, P(3,2) = 0, and P(3,3) = 1/6. From the formula P(N+1,C+1) = P(N,C)/(C+1) we deduce that for four cards P(4,1) = (1/3)/1 = 1/3, P(4,2) = (1/2)/2= = 1/4, P(4,3) = 0/3 = 0, and P(4,4) = (1/6)/4=1/24. If you write out all 24 possible combinations of 4 letters into 4 envelopes you'll see that these values are correct.

Now for the inductive proof - let "Exp(k)" mean the expected value of k letters into k envelopes:


Exp(k+1) = P(k+1,1) \times 1 + P(k+1,2) \times 2 + P(k+1,3) \times 3 + ..+P(k+1,k+1) \times (k+1) \\
= \frac {P(k,0)} 1 \times 1 + \frac {P(k,1)} 2 \times 2 + \frac {P(k,2)} 3 \times 3 + ...+\frac {P(k,k)} {k+1} \times (k+1) \\
= P(k,0) + P(k,1) + P(k,2) + ...+ P(k,k)


Since the sum of all possible probabilities of k letters into k envelopes equals 1, then Exp(k+1) = 1. Hence if Exp(k) = 1 then Exp(k+1) =1 . Thus the expected value is always1. QED.