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

[Tclack]

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:

http://www.math.uah.edu/stat/urn/Secretary.html

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.

:::::::::ow 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?

 

[pbuk]

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)

No, when k=2 it means that AT LEAST 1 candidate is eliminated.

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?

You have (correctly) identified the 12 possibilities where you select the second candidate. But that is not what you want - you want the number of possibilities where the candidate you select using the strategy k=2 is the best candidate (i.e. candidate labelled "1").

So for instance you should not count 3214 (because you select the candidate ranked 2), but should count 3412 (because you select the candidate in position 3 which is ranked 1).

 

[Tclack]

Thanks for catching that!

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