Noisy Secretary Problem Thresholds

ISEF Category: Mathematics

Subcategory: Probability and Statistics  ·  Difficulty: Advanced  ·  Setup: Home Setup  ·  Time: Full Year

The Hook

Imagine trying to hire the best person for a job when every resume is a little noisy. One strong signal can hide a weak candidate, and one weak signal can hide a star. That mix of uncertainty turns a classic puzzle into a real decision problem. You can study where to stop, where to keep looking, and how much noise changes the answer.

What Is It?

The secretary problem asks a simple question with a tricky answer. If you see candidates one by one and must pick immediately or reject forever, what rule gives you the best shot at choosing the best one? In the classic version, you only know relative rank. In this version, you get partial information, which means each candidate comes with a noisy quality signal, like a test score that is useful but not perfect.

Think of it like fishing with a blurry camera. You can still see shapes and movement, but not every detail. A threshold policy says, "Keep watching until the signal crosses a cutoff, then stop." Your job is to figure out how that cutoff should change when the signal is noisy, and how much that policy loses compared with an ideal decision maker. Regret is the gap between what your rule gets and what the best possible rule would get.

Why This Is a Good Topic

This topic works well for a science fair because you can turn a pure math idea into a testable model. You can change the noise level, the number of candidates, or the quality of the signals, then measure how the stopping rule performs. That gives you clear graphs, clear comparisons, and clear statistics. You also learn probability, simulation, optimization, and how to judge whether a rule stays strong when the data get messy.

Research Questions

• How does signal noise change the best stopping threshold in a secretary-style selection model?
• What is the effect of candidate pool size on the regret of a threshold policy?
• Does a threshold policy with a noise-adjusted cutoff outperform a fixed 37 percent rule?
• To what extent does asymmetric noise in early versus late candidates change the optimal stopping point?
• Which threshold rule gives the lowest average regret across repeated Monte Carlo trials?
• How does the distribution of signal quality affect the chance of selecting the top candidate?

Basic Materials

• Laptop or desktop computer.
• Spreadsheet software or Python.
• Python with NumPy and SciPy.
• Python with Matplotlib or Seaborn.
• Random number generator for simulation.
• Notepad or lab notebook for tracking assumptions.
• Basic graphing tool or spreadsheet charting features.

Advanced Materials

• Laptop or desktop computer with enough memory for large simulations.
• Python with NumPy, SciPy, pandas, Matplotlib, and statsmodels.
• Jupyter Notebook or JupyterLab.
• Symbolic math tool such as SymPy.
• Version control with Git.
• Access to a statistics reference or probability text.
• Optional cloud compute for repeated Monte Carlo runs.

Software & Tools

• Python: Runs simulations, computes regret, and tests threshold rules.
• Jupyter Notebook: Lets you document assumptions, code, results, and graphs in one place.
• NumPy: Handles random sampling and fast array-based calculations.
• Matplotlib: Plots stopping thresholds, regret curves, and simulation results.
• SciPy: Supports optimization and statistical calculations for model checking.

Experiment Steps

1. Define the decision problem clearly, including what counts as a candidate, a signal, and a correct choice.
2. Choose one noise model for the quality signal, then decide how you will represent uncertainty in code.
3. Derive or estimate a stopping threshold rule, and write down the assumptions that make it valid.
4. Build a baseline model with a known simple rule, then compare your new rule against it.
5. Run Monte Carlo simulations across different noise levels and candidate pool sizes.
6. Summarize performance with regret, success rate, and confidence intervals, then check whether the results match the theory.

Common Pitfalls

• Treating the noisy signal as if it were the true rank, which removes the whole challenge of partial information.
• Changing the noise model halfway through, which makes the threshold derivation and the simulation compare different problems.
• Using too few simulation trials, which makes regret estimates jump around and hides the real pattern.
• Comparing a new rule to the wrong baseline, which can make weak performance look stronger than it is.
• Ignoring boundary cases such as very short candidate lists or very large noise, which can break the threshold rule outside the main test range.

What Makes This Competitive

A strong version of this project does more than simulate one rule. You can compare several noise models, prove why your threshold changes in a specific way, and test whether the rule still works when the signal gets skewed or uneven across candidates. A deeper statistical analysis, such as confidence intervals for regret and sensitivity tests across parameters, makes the work feel much stronger. Clear theory plus clean simulation is what lifts this from a classroom model to a serious research project.

Project Variations

• Change the signal from normal noise to a bounded score scale and test whether the threshold stays stable.
• Compare a one-shot stopping rule with a two-stage rule that allows an early screen and a late final choice.
• Test how the policy changes when the quality signal is correlated with candidate order instead of independent.

Learn More

• MIT OpenCourseWare, Introduction to Probability and Statistics: Search MIT OpenCourseWare for probability lectures and problem sets on random variables, expectation, and decision making.
• Stanford Online or MIT OpenCourseWare, stochastic processes and optimization lectures: Search for free lecture notes on optimal stopping and sequential decision problems.
• PubMed: Search for review articles on decision theory and sequential sampling if you want a biomedical example of noisy choices.
• arXiv: Search for preprints on optimal stopping, secretary problems, and threshold policies to see current research directions.
• National Institute of Standards and Technology, Engineering Statistics Handbook: Search the handbook for guidance on simulation, uncertainty, and confidence intervals.
• Journal of Applied Probability: Search for published papers on secretary problems and optimal stopping models.