Results 1 to 2 of 2

Math Help - Help me get a girlfriend with math (optimal stopping theory/secretary problem)

  1. #1
    Junior Member Tclack's Avatar
    Joined
    Oct 2009
    From
    No permanant location.
    Posts
    57
    Thanks
    1

    Help me get a girlfriend with math (optimal stopping theory/secretary problem)

    So, I'm trying to understand how to derive 1/e (~37%)

    If you are unfamiliar with the secretary problem watch this short uninformative (as far as proof goes) video:

    Note: the video focuses on getting a wife, but it's the same concept as choosing a secretary

    Now, I searched for a proof and I've found this:
    The Secretary Problem
    But I must not be getting something. Let me elaborate. After a brief intro into the definitions, the above site starts off with examples of choosing the best number of people to eliminate (k-1) out of n candidates and it starts out by having the reader manually write out the sequence of n=3, n=4, and n=5 candidates and choosing the best choice for k.

    I'm ok with n=3, but while evaluating n=4 candidates,
    I'm getting:
    for k=2 , 12/24
    for k=3, 8/24

    I then tried evaluating n=5
    and got:
    for k=2, 60/120
    and then I stopped

    From what I'm assuming, the lower the number, the better the candidate. And so if k=1, that means that 0 candidates are eliminated automatically and you see the probability that the next candidate you choose is the better than any of the previous candidates.

    ::::::::::How I got 12/24 for k=2 when working on n=4 candidates::::::::::::
    when k=2, that means that 1 candidate is eliminated (as you have to eliminate, 0,1 or 2 candidates.... you cannot eliminate all 3 because you won't get a secretary that way) So I took all 24 arrangements of 1,2,3,4 and got:

    1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

    So, by covering the first number with my thumb, I checked to see how many of the second numbers were better than the first (covered) number and got:
    2134 2143 3124 3142 3214 3241 4123 4132 4213 4231 4312 4321 . That's 12/24 instead of their answer of 11/24

    What did I do wrong?

    :::::::::::::Similarly for k=3 on n=4 candidates, I covered the first two and saw how many of the 3rd was better than the first two
    2314 2413 3214 3421 3412 4213 4312 4321 . That's 8/24 instead of their 10/24:::::

    Don't even get me started on n=5 candidates, My numbers were even further off.

    WHAT DID I DO WRONG? AM I MISUNDERSTANDING THIS?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member Tclack's Avatar
    Joined
    Oct 2009
    From
    No permanant location.
    Posts
    57
    Thanks
    1

    Re: Help me get a girlfriend with math (optimal stopping theory/secretary problem)

    I posted this on Physics forum (sorry for my infidelity) But thanks to MrAnchovy, we found the error:

    MY MISTAKE: After eliminating 0,1,2, etc. candidates, I choose the next best one and considered it a WIN if that number was better than all the previous. It should have only been a WIN if that number (their absolute rank) was a 1. I ran through it again and got the proper numbers

    Note: It took over 200 views in PF and 45 views here... almost 250 view before the error was caught. But hey, that's the power in numbers.

    Thanks to all who gave it a shot.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. optimal problem
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: October 21st 2012, 10:25 PM
  2. set theory / predicate logic math language problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2010, 12:21 AM
  3. Optimal Control Theory: About the Riccati Dfiferential Equation
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: June 28th 2010, 12:04 PM
  4. Integrating factor in optimal control theory
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: June 5th 2010, 02:39 PM
  5. Explain the math behind the secretary problem?
    Posted in the Calculus Forum
    Replies: 4
    Last Post: July 5th 2008, 04:55 AM

Search Tags


/mathhelpforum @mathhelpforum