Secretary Problem
en.wikipedia.org
en.wikipedia.org
From wikipedia:
> In large part, this work has shown that people tend to stop searching too soon. This may be explained, at least in part, by the cost of evaluating candidates.
and then
> For example, when trying to decide at which gas station to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than they might had they searched longer.
So you might pay more for gas if you don't use the optimal strategy, but waste more money in fuel costs searching for the cheaper price than you save buy purchasing at that price.
Perhaps most interestingly, there is a formulation of the problem that requires a decision to be made within a certain time period, from an unknown number of candidates who arrive over that time period. If you know (or can estimate) the arrival times of the candidates, you can use a very similar strategy to achieve optimal results.
Essentially, wait until you have seen 1/e of expected candidates in the time frame you have allowed for (based on the arrival density function you know or estimated) then pick the next best option.
This puts a limit on the amount of searching you do, and so provides an optimal strategy with a bounded limit on how long you search for; it provides a bound on the cost involved in the search assuming the cost is related to time taken.
In the searching for gas example, you could use this strategy if you knew roughly how often you pass a gas station, and how long you are willing to search for.
However, it's worth pointing out that the strategy is unacceptable for the gas station scenario, because of the high probability of total failure.
The premise is that people come on the show with, what they consider to be, a valuable artifact. They then have the chance to take it to 4 collectors who will offer them a sum of money for said artifact.
The aim is to come away with the best offer you can get - but you only get one shot with each collector, you can't go back to a previous one because all other offers have been lower.
Although it's not clear how they avoid timing attacks.
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.
* you can improve your character: confidence is important, if you feel ugly sometimes you can do stuff about it (i.e. go to gym). Ditto if you are a boring talker, or if you are a poor listener.
* grind. If you are, like I was, a guy that has a couple hours on a weekend to meet a new possible date it's hard to find the "right" one. Try to increase the chances (go out more, frequent new places) and do try more.
These days I am just lazily sending out messages on OKCupid. And when I do go out to bars, I almost never approach.
So the "grind" reminder is totally fair.
(just kidding and don't take it personal - this one was too easy to pass up...)
If you want excitement, you'll get excitement. If you want stability, you'll get stability. If you want to confirm an opinion of yourself as undateable - guess what, that's what you'll get.
Most people say they want one thing but actually don't work towards that thing. They just pay it lip service.
Then laugh drunkenly at your own joke - that bit's important.
Worked for me - married over 10 years now.
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]
It's always a problem when you're on holiday and you know there are n pubs around, but you don't want to spend all your time going around and checking each and every pub 'cos that gets tedious. The question is - how many pubs should I visit before I give up?
As a general rule is this saying you should visit n/e pubs and then just pick the next best 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.
Freeform thoughts from here:
1/e is the probability of failing (every time) if you try a 1/n chance n times, where n is large.
To get the optimal choice, there are two (generously defined) requirements:
- #1 does not occur in the discarded group
- #1 occurs before everyone else who was not discarded, but exceeds the maximum of the discarded group
The second one seems hairy to me, so I'll wrap things up here. ;p
> As for real-world applications, the only one that comes readily to mind is rolling up a D&D character
This was introduced to me as a marriage problem, and wikipedia also notes it by that name. The analogy never seemed inaccurate to me; it's frowned upon to evaluate candidates simultaneously and rare to accept someone other than the latest candidate.
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..
Edit: It is also totally possible many people upvoted this article only because it is interesting. If that is true ignore my post.
For example, I know a proprietary trader who uses a concept similar to this from the field of Optimal Stopping for his trading system exclusively, i.e., his entire trading strategy, managing tens of millions of dollars for a big bank, is basically an application of Optimal Stopping to the markets!
One solution might be to try and find the the best candidate after (N/M)/e candidates, rather than N/e candidates. Then find the best candidate after (N_remaining/(M-1))/e candidates. That is recurse, by finding one candidate at a time, and discarding less then N/e each time to ensure you get enough candidates.
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.
Here is a link to my paper: http://www.cim.mcgill.ca/~yogesh/publications/crv2009.pdf
http://jsbin.com/woyehiyu/1/edit
(JavaScript, Console tabs. Click Run)
Single candidate: http://jsbin.com/cupiloye/1/edit
M candidates: http://jsbin.com/woyehiyu/1/edit
You might also be able to recognize a rock star secretary immediately or recognize obviously incompetent people. There's a competence threshold that's present here and has to be addressed if you dissect the analogy. Going for 'best' here has diminishing returns beyond a certain level of competence. The immediate need to decline/accept also really doesn't make sense if we're trying to explain this with a hiring analogy.
However, the Game of Googol nails it and I really like this approach much better when explaining this problem. It's a game with arbitrary rules so I can't easily use my worldly experience biases to solve the problem.
I first heard about this problem in a politically incorrect variation: a tribe chief is given the opportunity to choose a wife from a pool of n women, presented in a random order, one at a time. He can choose any woman, but can't choose a woman who he has already passed up. What's the strategy for the chief to choose the most beautiful wife?
Seriously, if you want to go the accurate route, probably best to pick a specific people where that's what actually happens. Not having done that, the problem as stated advances stereotypes of peoples that are referred to as "tribes" as being primitive and misogynistic.
Perhaps use "nation" instead, or better yet, formulate the problem differently.
Come to think of it, maybe I'd argue even stronger: when I was younger, I had a hard time understanding programming problems that were explained in terms of 'foo / bar' classes or function names. 'Applied' examples with cars and wheels made more sense, even if I could easily have come up with 'not every car has 4 wheels' counterarguments. Nowadays, I like foo / bar better, because they expose the problem directly, without an additional layer of real-world application, but only because I've gotten better at abstract reasoning.
(Aside: This is why I think you should work first, study later. University deals with abstract concepts, but without experience these abstract concepts often mean nothing to you)
What you're describing with the rock star vs incompetent people scenario is about bringing prior knowledge in there. You see a rock star as first candidate. You figure that, in your lineup of 10 people, odds are that no one will be better than that rock star. So you pick him/her.
This makes the theoretical solution at best a kind of intuitive justification in practical settings, but you shouldn't apply it mechanically without using your judgment.