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

  • Thread starter Thread starter Tclack
  • Start date Start date
AI Thread Summary
The discussion focuses on understanding the optimal stopping theory, specifically the secretary problem, and deriving the 1/e (~37%) solution. The original poster struggles with calculating probabilities for selecting the best candidate among a set of options, particularly when eliminating candidates based on the value of k. They initially miscounted the successful outcomes by incorrectly defining a "win" as selecting any candidate better than previous ones, rather than specifically the best candidate. After clarification, they realize their error and adjust their calculations accordingly. The conversation emphasizes the importance of correctly interpreting the rules of the problem to achieve accurate results.
Tclack
Messages
37
Reaction score
0
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.

::::::::::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?
 
Last edited by a moderator:
Physics news on Phys.org
Tclack said:
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.

Tclack said:
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).
 
  • Like
Likes 1 person
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
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top