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,
for k=2 , 12/24
for k=3, 8/24
I then tried evaluating n=5
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?