Correct Letters
Source: Jaadu a.k.a Anshum Agarwal (Fourth Year, CSE, IITB and to be Tower Research Analyst) gave me this question. Said question from Tutorial of Prof. Sundar's course "Approximation Algorithms"
Problem:
There are n letters and n envelopes. Your servant puts the letters randomly in the envelopes so that each letter is in one envelope and all envelopes have exactly one letter. (Effectively a random permutation of n numbers chosen uniformly). Calculate the expected number of envelopes with correct letter inside them.
Disclaimer: Not easy :P
Update (10/01/10): Solution: Posted by Giridhar (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!! Nice solution.
Update (21/01/10): With the help of Asad Ali (EE, IITB Alumnus), a different solution posted by me in comments!!
Problem:
There are n letters and n envelopes. Your servant puts the letters randomly in the envelopes so that each letter is in one envelope and all envelopes have exactly one letter. (Effectively a random permutation of n numbers chosen uniformly). Calculate the expected number of envelopes with correct letter inside them.
Disclaimer: Not easy :P
Update (10/01/10): Solution: Posted by Giridhar (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!! Nice solution.
Update (21/01/10): With the help of Asad Ali (EE, IITB Alumnus), a different solution posted by me in comments!!
Let I_i be a indicator random variable which takes
ReplyDelete1) value 1 if ith letter ends up in ith envelope.
2) value 0, otherwise
let I be r.v which indicates the number of letters which ended up in their respective envelopes.
Now, I= I_1 +I_2+....+I_n
E[I_i] = 1/n. for all i
Using Linearity of Expectations E[I]= 1/n + 1/n +...+1/n = 1.
Surprising result, on average only one letter ends up in correct envelope, independent of the number of letters that u start with!!
Nice.. Thanx a lot.. A real difficult one though.. I was trying to solve it using some recurrence relation but no luck. I was also not able to calculate the probability of exact "k" matches. Smart solution indeed. Thanx.
ReplyDeleteYes,nice solution.Infact many of the times it is easier to find the expectation value of random variable by breaking it into several random variable,i.e. breaking X as X1,X2,X3,... and the writing E[X] = E[X1]+E[X2]+E[X3]+.....
ReplyDeleteThought this comment might help.
ReplyDeleteHere I_1, I_2, ... I_n are not linearly independent (check the case of n=2). But the linearity of expectation holds even when the random variables concerned are not independent. Proof can be found in any undergraduate probability course (Rutgers Course Notes)
Here's the recursive approach:
ReplyDeleteLet E(n) be the expected no. of correct matches for n pairs.
Now consider the nth envelope. There are two cases that may occur -
1) It gets the correct letter, so the no. of correct matches = E(n-1)+1
2) It does not get the correct letter. Let's suppose, without the lack of generality, that letter no. 1 takes its place. Now the nth letter is inside the n-1 "system". The expected no. of correct matches is E(n-1) - (1/n-1)*E(n-1).
The 2nd term is because in the ideal n-1 "system" letter 1 would have contributed 1/n-1 to the expected value. Now since 1st letter has been replaced by nth letter, the expected no. is lessened by that term.
For final answer we multiply the results of two cases with their respective probabilities and sum.
Thus E(n) = (1/n)*[E(n-1)+1]+((n-1)/n)*[E(n-1) - E(n-1)*((n-1)/n)]
=> E(n) = 1/n + (n-1)*E(n-1)/n
This will give 1 as the solution since E(1) = 1
P.S. The subtraction of (1/n-1)*E(n-1) is a leap of faith :P. Can someone confirm it theoretically? - it sounds intuitive
@Asad.. Nice approach. Here's a proof to your intuition. I think I came up with another recurrence solution trying to prove yours. :)
ReplyDeleteYou said that the expected number of correct letters in a "n" system is E(n).
Also let the expected number of correct letters in a "n" system with 1 wrong letter is E'(n).
Your intuition says E'(n) = E(n) - E(n)/n.
Lets assume that the wrong letter had replaced letter 1, without loss of generalisation.
If the wrong letter reached envelope 1, then the answer is E(n-1) and if the wrong letter reaches any other envelope, then its the same when the letter 1 reached a wrong envelope in the general "n" system.
So, E'(n) = 1/n(E(n-1)) + (n-1)/n(E'(n-1))
So,
using your logic,
E(n) = (1/n)*[E(n-1)+1]+((n-1)/n)*[E'(n-1)]
So, we have two recurrence equations to solve:
E'(n) = 1/n(E(n-1)) + (n-1)/n(E'(n-1))
E(n) = (1/n)*[E(n-1)+1]+((n-1)/n)*[E'(n-1)]
Subtracting them,
E(n) - E'(n) = 1/n
So, E'(n) = E(n) - 1/n
Since, E(n) eventually turns out to be 1, this is what your intuition says. :)
Substituting in second recurrence relation:
E(n) = E(n-1)
and so, E(n) = E(1) = 1 :)
Interesting argument :) Thanx a ton.