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!

Comments

  1. Can be done by induction:
    assume 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

    ReplyDelete
  2. Isn't the question just an extension to a previous question: http://pratikpoddarcse.blogspot.com/2010/01/correct-letters.html

    As 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 :)

    ReplyDelete
  3. @Shaunak.

    Expectation 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!

    ReplyDelete
  4. Elegant solution indeed.

    The 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.

    ReplyDelete
  5. @Chera.. Thanks. Your observation is correct!

    ReplyDelete
  6. One related question : What is expected number of rounds any man has to wait before he gets his own hat ?

    ReplyDelete
  7. Nice 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.

    If 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?

    ReplyDelete
  8. Got to think some more and the Wald equation approach doesn't quite work. The X_i aren't independent of N after all.

    ReplyDelete
  9. Thanks Dinesh. Please help us solve the problem we are not able to solve (refer to unsolved tag) :)

    Wald's equation approach will not work here. In fact, one can only conclude that E(S|N) = NE(X)

    ReplyDelete
  10. @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.

    The problem collection is truly awesome. Keep up the great work.

    ReplyDelete
  11. Expected number of rounds for 2 people to get their correct hats = 1*1/2 +2*(1/2)^2 + 3*(1/2)^3 (ArithmeticoGeometric)

    This 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

    ReplyDelete

Post a Comment