Solving optimal stopping problems with statistical algorithms
Enough Is Enough
When is it statistically favorable to conclude, say, the search for a suitable employee with a chosen one? Solid algorithms point the way to success.
The saying goes that you should quit when you're ahead. Making a decision on when to conclude a selection process is often not that easy in real life. In mathematical statistics, a puzzle known as the "secretary problem" [1] sums this up nicely. A number of candidates are applying for a secretary position at a company. In the selection process, the employer must decide after each interview, whether to accept the candidate or reject them and hope for a more suitable applicant later on. The decision is final, the employer is not allowed to invite back any rejected applicants.
An employer who is thinking logically should carefully check the first few candidates and not simply take the first one. Later, when the line starts to come to an end, the employer will possibly take on a more-or-less suitable candidate for fear of being left with only unsuitable candidates, and – not having any other options – grudgingly just bite the bullet, and grab whoever is left.
Ideal: 37 Percent
How should the employer proceed to mathematically ensure the best possible odds of finding an above-average candidate? How long should the try-before-buy phase last, in which the employer explores the unknown capabilities of candidates before immediately snapping up the one that is better than all the previous ones and hopefully scores favorably against future candidates further down the line? Mathematicians have been tackling stop problems [2] for thousands of years.
As the recently published book Algorithms to Live By [3] entertainingly explains, the answer is 37 percent, or more precisely 1/e * 100%
. Given 100 candidates, an employer is well advised to check out the first 37 without any intention to employ anyone, just to gain some idea of the talents available on the labor market. As of candidate number 38, smart bosses then immediately sign a contract if one candidate is obviously better than all the previous ones.
Love-Crazed Stargazers
This task is also known as the wedding problem. The story of the famous star gazer Johannes Kepler, who was desperately looking for a new wife after the death of his first wife in 1611, is legendary. With meticulous mathematical skills, he launched himself into a lengthy process of research, looking at no less than 11 candidates. Completely exhausted and remorseful, he then returned to candidate number five, proposed to her, and to his great joy luckily received a glowing "Yes!" as an answer to his question.
Simulating Reality
To work your way through the secretary problem with a Perl program, the script needs to make some assumptions about the distribution of the supply in the labor market. The controversial "20-70-10" rule of American tycoon Jack Welch [4] dictates that the 20 percent top performers in a company return exceed expectations, 70 percent work quite well, and 10 percent are unproductive. For the experiment, we let the labor market also follow this scheme; the available talents thus roughly lie on the bell curve of a Gaussian normal distribution (Figure 1).
Because the candidates arrive in random order, the script needs a random generator that outputs a normally distributed pool of talents. The random_normal
function of the Math::Random
CPAN module already has such a generator; in Listing 1 [5], it uses the parameters 100_000, 10, 2
to return 100,000 random values that fluctuate around the mean value of 10 with a standard deviation of 2.
Listing 1
histo-normal
To check whether the distribution also roughly meets the requirements visually, Listing 1 uses the get_histogram()
function from the Statistics::Histogram CPAN module to print a histogram of distributed values as ASCII art on the command line. The bell shape is indeed visible (Figure 2), and although the maximum of the random data is at around 10, the frequency drops off towards both sides, and there are hardly any values less than 4.5 or greater than 15.5.
The script for simulating the secretary interviews (Listing 2) takes on the randomly arriving candidates one by one. Following the 37 percent rule, it breaks down the @data
array into two parts. The first part, stored in @look
, contains the first 37 percent of the random numbers, which are merely for analysis of the labor market without any intention to employ; the second part (@act
) contains the other 63 percent; the employer will immediately make a decision here if one of the candidates is better than all previous encountered ones. Line 41 stops the script when this occurs.
Listing 2
secretary
If no better candidate shows up by the end of the array, the boss has lost out and has to employ the last candidate as a final option, which is what line 46 does. If the script is called with the --verbose
option, line 9 of Listing 2 switches Log4perl's logging function to debug mode to produce diagnostic messages on how the hiring process is proceeding.
The script then outputs a number of messages to standard output at run time. Figure 3 shows that the bar for the candidates during the screening stage was at 11.05, and then at 11.52. In employment mode, a number of candidates with suitability values below the previous record of 11.52 then follow, before one with a value of 11.68 gets the job.
Although the procedure has been proven to be optimal, it still often goes wrong. Figure 4 shows a run in which a candidate with an extremely high suitability value (12.84) interviews during the test phase, a value that puts all the others later in the employment round to shame. Bad luck, the boss has to take the last candidate with a rating of 9.36.
How often do these embarrassing and significant suboptimal outcomes occur in the algorithm? To measure this, Listing 3 calls the secretary
script 100 times and measures how often a candidate is given preference although they are below average. The Stats::Histogram CPAN module shows the distribution.
Listing 3
secretarystats
Figure 5 shows that the procedure finds a useful candidate in about 80 percent of the cases, including some superstars with ratings of 12 and more. However, it failed in 20 percent of cases where the boss had to take on the last candidate, whether they were a star or a clown. All told, the strategy is optimal; check out [1] for the mathematical proof.
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News
-
Juno Computers Launches Another Linux Laptop
If you're looking for a powerhouse laptop that runs Ubuntu, the Juno Computers Neptune 17 v6 should be on your radar.
-
ZorinOS 17.1 Released, Includes Improved Windows App Support
If you need or desire to run Windows applications on Linux, there's one distribution intent on making that easier for you and its new release further improves that feature.
-
Linux Market Share Surpasses 4% for the First Time
Look out Windows and macOS, Linux is on the rise and has even topped ChromeOS to become the fourth most widely used OS around the globe.
-
KDE’s Plasma 6 Officially Available
KDE’s Plasma 6.0 "Megarelease" has happened, and it's brimming with new features, polish, and performance.
-
Latest Version of Tails Unleashed
Tails 6.0 is based on Debian 12 and includes GNOME 43.
-
KDE Announces New Slimbook V with Plenty of Power and KDE’s Plasma 6
If you're a fan of KDE Plasma, you'll be thrilled to hear they've announced a new Slimbook with an AMD CPU and the latest version of KDE Plasma desktop.
-
Monthly Sponsorship Includes Early Access to elementary OS 8
If you want to get a glimpse of what's in the pipeline for elementary OS 8, just set up a monthly sponsorship to help fund its continued existence.
-
DebConf24 to be Held in South Korea
Busan will be the location of the latest DebConf running July 28 through August 4
-
Fedora Unleashes Atomic Desktops
Fedora has combined its solid distribution with rpm-ostree system to make it possible to deliver a new family of Fedora spins, called Fedora Atomic Desktops.
-
Bootloader Vulnerability Affects Nearly All Linux Distributions
The developers of shim have released a version to fix numerous security flaws, including one that could enable remote control execution of malicious code under certain circumstances.