Number of Rounds of Derangements
Source: Asked to me by Sudeep Kamath (Third year PhD Student, UC at Berkeley, EE IITB Alumnus)
Problem:
There are n men, n hats, one hat belonging to each person. A random permutation of hats is picked by the men, whoever gets their own hat, takes it and leaves and a random permutation of the remaining hats is picked and so on. What is the expected number of rounds it takes for everyone to
leave?
Hint: Answer is n
Update (21 Oct 2010):
Solution posted by Siddhant Agarwal (Senior Undergraduate, EE, IITB), and a more detailed explanation posted by me in comments!
Problem:
There are n men, n hats, one hat belonging to each person. A random permutation of hats is picked by the men, whoever gets their own hat, takes it and leaves and a random permutation of the remaining hats is picked and so on. What is the expected number of rounds it takes for everyone to
leave?
Hint: Answer is n
Update (21 Oct 2010):
Solution posted by Siddhant Agarwal (Senior Undergraduate, EE, IITB), and a more detailed explanation posted by me in comments!
Can be done by induction:
ReplyDeleteassume true till n-1
Let f_n = expected no of rounds required for everyone to leave if there were n people..
=>f_i=i for 1<=ip_2+p_3+...+p_n=1 ... eq1
Also it is clear that the expected no of persons that will get their own hat in first round is (1/n)+(1/n)+..(1/n)=1
=> (n-2)*p_2+(n-3)*p_3+..+1*p_(n-1) = 1 .. eq2
=> 2*p_2+3*p_3+...+(n-1)*p_(n-1) = (n-1) - n*p_n
Now f_n = p_n*(1+f_n) + p_(n-1)*(1+f_(n-1)) + ... + p_2*(1+f_2)
=> f_n = 1+p_n*f_n + (n-1) - n*p_n
=> f_n = n
Isn't the question just an extension to a previous question: http://pratikpoddarcse.blogspot.com/2010/01/correct-letters.html
ReplyDeleteAs proved in the correct-letters question, the expected number of men with correct hats would be equal to 1, independent of the value of n.
After every round, an expected number of 1 man leaves with his hat. Thus, the expected number of n rounds is taken for everyone to leave :)
@Shaunak.
ReplyDeleteExpectation in math is not expectation in english. [(You expect one person
to go down every day) => (In n days all of them would be eliminated)] does
not make sense. Try to write it mathematically and you will realise your
mistake.
@Siddhant.. Correct solution. I gave the same solution to Sudeep. \m/ \m/
My solution:
Define p(n,m) as the probability that in case of n hats, n men, after
one iteration the problem reduces to m hats, m men, i.e. n-m people
got it correct.
Also define E(n) as our answer, i.e expected number of iterations
So, E(n)= 1+(sum over m varies from 0 to n) p(n,m)E(m)
We have to prove that E(n)=n. Let us prove this by induction. So,
hypothesis: E(m)=m for all m less than n
So, E(n)(1-p(n,n))=1+(sum over m varies from 0 to n-1) p(n,m)m (say equation 1)
Remember the random derangement problem
(http://pratikpoddarcse.blogspot.com/2010/01/correct-letters.html)
(sum over m varies from 0 to n) p(n,m)(n-m) = 1
So,
(sum over m varies from 0 to n) p(n,m)(m) = n-1 (say equation 2)
From equation 1 and 2,
we get
E(n)(1-p(n,n))=n(1-p(n,n))
Hence, E(n)=n
Hence, proved!
Elegant solution indeed.
ReplyDeleteThe issue raised by sherminator is also interesting.
if expected number of rounds so that m men leave is f(m). Then the converse is not true i.e. expected number of people who leave after f(m) rounds say
g(f(m) will not be m.
In particular, expected number of people who leave after n rounds will not be n, but less. I guess, in general, g(f(m))<=m.
@Chera.. Thanks. Your observation is correct!
ReplyDeleteOne related question : What is expected number of rounds any man has to wait before he gets his own hat ?
ReplyDeleteNice puzzle and an excellent blog. I am a new reader and I found Sherminator's comment interesting. I think there is a mathematical way to justify that comment.
ReplyDeleteIf S = \sum_{i=1}^{N} X_i where X_i and N are independent rvs with all X_i having the same mean, then it can be shown that E(S) = E(N)E(X_i) (Wald's equation). In this problem, we can think of X_i as the number of fixed points of the random permutation chosen in the ith round. For every one to leave, the sum S must equal n and E(X_i) = 1. So E(N) which is the number of rounds needed must be n.
Does this make sense?
Got to think some more and the Wald equation approach doesn't quite work. The X_i aren't independent of N after all.
ReplyDeleteThanks Dinesh. Please help us solve the problem we are not able to solve (refer to unsolved tag) :)
ReplyDeleteWald's equation approach will not work here. In fact, one can only conclude that E(S|N) = NE(X)
@Pratik: I was too hasty with that Wald's equation comment. In fact, this setup is the very anti-thesis of the Wald's equation. We have S = \sum_{i=1}^N X_i but if S is a constant (as in this case), E(S|N) = S and we are left with S = S \times (\sum_{n=1}^{\infty} P(N=n)). Basically it becomes trivial.
ReplyDeleteThe problem collection is truly awesome. Keep up the great work.
Thanks :)
ReplyDeleteExpected number of rounds for 2 people to get their correct hats = 1*1/2 +2*(1/2)^2 + 3*(1/2)^3 (ArithmeticoGeometric)
ReplyDeleteThis comes out to 2.
Let E(n) be expected number of rounds for n people,
E(1) =1; E(2) = 2
E(n) = E(n-2) +E(2)
= E(n-2) +2
Recursively,
E(n) = n