Monday, November 15, 2010

marriage problem

 Suppose you decide to marry, and to select your life partner you will interview at most 100 candidate spouses. The interviews are arranged in random order, and you have no information about candidates you haven’t yet spoken to. After each interview you must either marry that person or forever lose the chance to do so. If you have not married after interviewing candidate 99, you must marry candidate 100. Find a strategy to maximize the probability of choosing  the best spouse. For example, a simple strategy of marrying the first candidate will ensure best spouse with  probability 1/100. 
Posted by at

3 comments:

  1. VipulFebruary 19, 2011 at 12:02 PM

    Hi,

    Whats is the criteria to choose the candidate as spouse i.e. on what merits do we select the candidate. Otherwise this is very same problem as this one http://pratikpoddarcse.blogspot.com/2010/01/dont-roll-more.html

    Thanks,
    Vipul

    ReplyDelete
  2. cheraFebruary 20, 2011 at 10:49 AM

    vipul,

    criteria can be anything. for example u may want to marry most richest girl. problem is that u will know the relative ordering of spouses only after u have seen all of them.

    its different from pratik's post referred above because there u r rolling a dice and if u get a 6 on first trial then u will stop.

    to be more specific, define a random variable
    X=1 , if u choose best spouse,
    X=0 otherwise

    problem is to find a strategy to maximize E[X] i.e. maximize probability that X=1

    ReplyDelete
  3. Pratik PoddarDecember 19, 2011 at 6:28 AM

    Ha. Happy to see my blog referenced here. :) @chera.. I am surprised how I missed your blog.


    Instead of the Don't Roll More, the problem that would be exactly the same would be http://pratikpoddarcse.blogspot.com/2009/12/problem-you-are-chief-guest-at-auction.html

    ReplyDelete

Subscribe to: Post Comments (Atom)