Cracking the Code of Decision Making: The Secret Behind the Secretary Problem

Discover the Strategy to Maximize Success with Mathematical Insights and Real-World Applications

Photo by Meizhi Lang on Unsplash

Introduction

Imagine you’re the hiring manager for a company, tasked with finding the best candidate for a critical position. You have to interview n candidates one by one and make an immediate decision after each interview: either hire the candidate on the spot or reject them and move on to the next. You want to maximize your chances of hiring the best candidate, but once you reject someone, you can’t go back. This is the essence of the Secretary Problem, also known as the Optimal Stopping Problem.

In this post, we’ll explore the mathematics behind the optimal stopping rule, derive why the optimal strategy works, and demonstrate it with a cool Python example. We’ll also weave in stories and intuitive explanations to make the concept easy to grasp.

The Scenario

To make it more relatable, let’s imagine you’re in a real-world scenario:

You are the head coach of a basketball team. You need to pick the best player from a pool of n players. You can only watch each player once, and after watching, you must decide whether to recruit them or not. How do you ensure you have the best chance of picking the top player?

The Optimal Stopping Rule

The optimal stopping rule for this problem is surprisingly elegant and revolves around a simple principle:

1. Observe but do not select the first k candidates.
2. After the first k candidates, select the next candidate who is better than all the previous candidates.

But how do we choose k? It turns out that the optimal k is approximately n/e ​, where e is the base of the natural logarithm, approximately 2.718.

Mathematical Derivation

1. Probability that the best candidate is in the first k candidates:

However, we won’t select any of these candidates, so this probability is not useful directly.

2. Probability that the best candidate is in the remaining n−k candidates:

3. Conditional Probability of Selecting the Best Candidate: If the best candidate is in the remaining n−k candidates, we want to know the probability that we will select them.

For a candidate at position j (where k+1≤ j ≤ n) to be the best, all previous j−1 candidates must be worse than the candidate at j. Given that we are observing but not selecting the first k candidates, this probability is:

4. Summing the Probabilities:

For large n, this sum can be approximated by an integral:

Evaluating the integral:

Thus, the optimal strategy gives us a probability of approximately 1/e (about 36.79%) of selecting the best candidate.

Python Example

Let’s implement this strategy in Python with a simulation to see it in action.

import random
import math

def secretary_problem(n, trials=10000):
    success = 0
    
    for _ in range(trials):
        candidates = list(range(1, n+1))
        random.shuffle(candidates)
        
        k = math.ceil(n / math.e)
        best_in_first_k = max(candidates[:k])
        
        for candidate in candidates[k:]:
            if candidate > best_in_first_k:
                if candidate == n:
                    success += 1
                break
                
    return success / trials

n = 100
probability = secretary_problem(n)
print(f"Probability of selecting the best candidate: {probability:.4f}")

Example 1: Varying Number of Candidates

In this example, we’ll explore how the success probability changes with different numbers of candidates. We’ll plot the probability of selecting the best candidate for n ranging from 10 to 200.

def secretary_probabilities(n_range, trials=10000):
    probabilities = []
    for n in n_range:
        probabilities.append(secretary_problem(n, trials))
    return probabilities

n_range = range(10, 201)
probabilities = secretary_probabilities(n_range)

plt.figure(figsize=(21, 10))
plt.plot(n_range, probabilities, marker='o', linestyle='-', color='tab:blue')
plt.axhline(y=1/math.e, color='r', linestyle='--', label='1/e')
plt.title('Probability of Selecting the Best Candidate')
plt.xlabel('Number of Candidates (n)')
plt.ylabel('Success Probability')
plt.legend()
plt.grid(lw=2,ls=':')
plt.show()

Example 2: Comparison with Random Selection

In this example, we’ll compare the optimal stopping strategy with a random selection strategy. We’ll plot the success probabilities of both strategies as the number of candidates increases.

def random_selection(n, trials=10000):
    success = 0
    
    for _ in range(trials):
        candidates = list(range(1, n+1))
        random.shuffle(candidates)
        if candidates.index(n) == random.randint(0, n-1):
            success += 1
                
    return success / trials

def compare_strategies(n_range, trials=10000):
    optimal_probs = []
    random_probs = []
    for n in n_range:
        optimal_probs.append(secretary_problem(n, trials))
        random_probs.append(random_selection(n, trials))
    return optimal_probs, random_probs

n_range = range(10, 201)
optimal_probs, random_probs = compare_strategies(n_range)

plt.figure(figsize=(18, 10))
plt.plot(n_range, optimal_probs, marker='o', linestyle='-', color='b', label='Optimal Stopping')
plt.plot(n_range, random_probs, marker='x', linestyle='-', color='g', label='Random Selection')
plt.axhline(y=1/math.e, color='r', linestyle='--', label='1/e')
plt.title('Optimal Stopping vs Random Selection')
plt.xlabel('Number of Candidates (n)')
plt.ylabel('Success Probability')
plt.legend()
plt.grid(lw=2,ls=':')
plt.show()

Conclusion

The Secretary Problem provides a fascinating look into decision theory and optimal stopping rules. By following the simple yet powerful strategy of observing the first n/e candidates and then selecting the next best one, you can maximize your chances of making the best choice. While the probability of success is about 36.79% (or approximately 1/e), this strategy is the best possible approach given the constraints of the problem.

Why 36.79% is Better Than Random Choice

Let’s delve into why the 36.79% success probability given by this strategy is significantly better than just making a random choice:

1. Random Selection Probability: If you randomly select a candidate without any strategy, the probability of choosing the best candidate is simply 1/n. For example, if you have 100 candidates, your probability of randomly selecting the best one is just 1%.
2. Improvement with Optimal Stopping Rule: The optimal stopping rule boosts your probability to about 36.79%, regardless of the number of candidates. This is a remarkable improvement over random choice. With 100 candidates, the optimal strategy is about 36 times more likely to select the best candidate compared to random selection.
3. Mathematical Insight: The 36.79% probability comes from a balance of risks. By observing the first n/e​ candidates, you gain information about what constitutes a “good” candidate. This information helps you make a more informed decision when you start selecting candidates, significantly increasing your chances of picking the best one.
4. Optimality Proof: The optimal stopping theory proves that no other strategy gives a higher probability of selecting the best candidate.

Final Thoughts

The beauty of the Secretary Problem lies in its applicability to various real-life scenarios, from hiring decisions to dating and even investment choices. Understanding and applying this optimal stopping rule can give you an edge in making better decisions. By leveraging a strategy grounded in probability and decision theory, you can greatly improve your chances of success compared to random selection.

Happy decision-making!