Secretary Problem • Hacker News Board

Re: Secretary Problem

#11

Post by sk5t » Tue, Mar 04, 2014, 4:37 AM UTC

Quite interesting that discarding the first n/e candidates produces a 1/e probability of choosing the optimal one...

As for real-world applications, the only one that comes readily to mind is rolling up a D&D character, supposing one has only the patience for some predetermined n rolls. Somewhat ironically it is not a realistic fit for hiring, as there is seldom a need to accept or eliminate candidates immediately, interviewing more than 5-6 people for a role is torturous, and an interviewer uses his experience interviewing and interacting with people generally to have no mathematical prejudice against hiring the very first pretty-good option.

Re: Secretary Problem

#12

Post by judk » Tue, Mar 04, 2014, 5:06 AM UTC

forgotprevpass wrote: post #5

On a related note, can someone suggest a good textbook optimal stopping?

If you get a stream kf recommendations, how will you choose which one to read?

Re: Secretary Problem

#13

Post by kokey » Tue, Mar 04, 2014, 5:11 AM UTC

Interesting. It describes roughly the strategy that I've settled on when looking for accommodation to rent. I think it also has the added advantage of making you feel you've made a good decision.

Re: Secretary Problem

#14

Post by jmtame » Tue, Mar 04, 2014, 5:33 AM UTC

I worked on several iterations in the dating space for about a year, and this type of stuff was pretty interesting to me. Wrote a bit more about it here: https://medium.com/unfinished-thoughts/2cac1e6cc7b4

Re: Secretary Problem

#15

Post by Johnie » Tue, Mar 04, 2014, 5:37 AM UTC

The same strategy can be used in dating too.

When you live in a major city and the dating options are boundless, there is always someone around the corner that is "perfect" or more perfect than the current person that you are dating. Next thing you know, you're in your late 30s and still single.

Re: Secretary Problem

#16

Post by hoonose » Tue, Mar 04, 2014, 5:41 AM UTC

vehementi wrote: post #7

What about needing to hire M candidates out of N applicants?

There's a large body of work on variations of the secretary problem. The one I know of which is most relevant to your question is section 4 of the following: http://www.cs.cornell.edu/~rdk/papers/secArt4.pdf

Section 6 is particularly interesting, where you're further restricted - you want to choose multiple secretaries, but there's certain constraints on the sets you can choose. For example, the secretaries might be edges in a graph, and you can't pick a subset of edges which would result in a cycle (this is a "graphic matroid," which is an example of a mathematical object known as a matroid). The reason why this formulation of the problem is interesting is because the best known algorithm is O(sqrt(log k))-competitive (where k is the rank of the matroid), whereas it is conjectured that an O(1)-competitive algorithm exists.

Re: Secretary Problem

#17

Post by gargarplex » Tue, Mar 04, 2014, 5:47 AM UTC

Johnie wrote: post #15

The same strategy can be used in dating too. When you live in a major city and the dating options are boundless, there is always someone around the corner that is "perfect" or more perfect than the current person that you are dating. Next thing you know, you're in your late 30s and still single.

I always feel bad when I see these posts. I'm 26 and in a major city, but finding dates is a serious problem for me. My looks are only slightly below average (4/10) but my personality is probably the deal breaker.

Re: Secretary Problem

#18

Post by mchusma » Tue, Mar 04, 2014, 5:48 AM UTC

gargarplex wrote: post #4

_xhok wrote: post #2

Is it possible to explain in layman's terms why 1/e is the magic number?

The function that approximates the best ideal solution can be approximated with the log function. It's kind of like why the taylor polynomials means that e^pi*i = -1

I don't think that was exactly a lay explanation. Was interested myself.

Re: Secretary Problem

#19

Post by aegiso » Tue, Mar 04, 2014, 5:50 AM UTC

Johnie wrote: post #15

The same strategy can be used in dating too. When you live in a major city and the dating options are boundless, there is always someone around the corner that is "perfect" or more perfect than the current person that you are dating. Next thing you know, you're in your late 30s and still single.

This only works if you stick with every partner long enough to get a perfectly accurate assessment of them as a long term mate, that your assements are perfectly objective, independent, and stable, and that you know n.

The amount of ifs, ands, and buts in this caveat means it's time to defer to one of my favorite xkcd's of all time. [0]

[0] http://xkcd.com/55/

Re: Secretary Problem

#20

Post by gargarplex » Tue, Mar 04, 2014, 5:55 AM UTC

mchusma wrote: post #18

gargarplex wrote: post #4

Earlier quoted context omitted.

The function that approximates the best ideal solution can be approximated with the log function. It's kind of like why the taylor polynomials means that e^pi*i = -1

I don't think that was exactly a lay explanation. Was interested myself.

Yeah, it totally wasn't. I failed.

Okay, so one of the really interesting properties of mathematics is that complicated functions can sometimes be simplified by simple functions.

For example, the gamma function is an extension of the factorial function (4! = 432*1).

http://upload.wikimedia.org/math/a/c/5/ac57cb1b5db9b61155d86...

Amazingly, you are able to represent one idea in another, different way.

So, with the secretary problem, you are able to break down the optimal solution as this:

http://upload.wikimedia.org/math/6/f/4/6f4d3a757d9efe51b8b17...

The | notation means "given". So x|b means "x, given b".

For these abstract formulations, they are reduced to already-existing calculations..

Finally, you get the big sigma symbol. This is called a Summation. Summations tend to be able to be approximated using integrals, since an integral is the area under the curve, which is also a summation of sorts.

Many integrals can be defined using the "log" function, which has base "e". In this case, when you add in "infinity" for the summation, it converges towards 1/e.

Hope this helps some. If it doesn't, well, I was fired from my job TA'ing calculus =B so..