Skip to content

One slot, no take-backs (prophet inequalities)

A cache has one premium slot, and objects arrive one at a time. Each must be pinned now or never, and once the slot is filled it stays filled. Waiting for something better risks ending with nothing good; taking the first decent object risks missing the best one. This page explains the mathematics of such one-shot choices — prophet inequalities, catalog result 111 — what the classical results guarantee and under which assumptions, and which of the library's two helpers carries a guarantee: single_item_max_of_samples does, single_item_one_sample (one scalar bar) does not.

It assumes you know what an expected value and a probability distribution are. Symbols are collected on How to read these pages. This is a helper you call yourself, not one of the six checks on every decision.

The situation

Values \(v_1, v_2, \dots, v_n\) arrive in order: predicted hits for objects published today, bids for one seat, offers for one item. When \(v_i\) arrives you see it and must accept or reject it on the spot; you may accept at most one. A prophet who sees all the values in advance simply takes the largest and earns \(\mathbb E[\max_i v_i]\). A prophet inequality says that some online rule earns at least a fixed fraction of what the prophet earns, whatever the values are, provided their distributions satisfy stated assumptions.

The simplest online rules set a bar (a threshold) and take the first value that reaches it. The whole question is where the bar comes from.

Intuition: the bar must reflect the best value you will see, not a typical one

A bar at a typical value (yesterday's median) accepts almost the first thing that arrives. That is fine when values are similar, and disastrous when a few rare arrivals are worth far more than the rest: the rule takes something ordinary early and never sees the rare one.

A good bar is about how large the best of today's values is likely to be. The classical rules all set the bar from the distribution of the maximum, or from one past draw for each arrival so that the largest past draw estimates the maximum.

Worked example: the cache slot

Run:

uv run grounded-decision examples cache_admission

Yesterday's predicted hits at the five publish slots were 2.0, 0.5, 6.0, 3.5 and 5.0 (one past sample per arrival), so the bar is the largest, 6.0. Today's arrivals are 1.0, 1.5, 9.0, 2.0, 12.0. single_item_max_of_samples skips 1.0 and 1.5, pins the 9.0 object (index 2), and never sees the 12.0 one. The example prints guarantee: on average >= 1/2 of the offline-best hit count (one past sample per arrival) and SLO claimed: on average >= 1/2 of the offline best (not every day): the promise is about the average over days, not about today.

Now a traffic pattern where a typical-value bar fails. Twenty objects arrive; each is viral (100 hits) with probability 5% and ordinary (1 hit) otherwise. This script runs the two helpers over 100,000 simulated days with three choices of bar:

import random
from grounded_decision.compare import single_item_max_of_samples, single_item_one_sample

rng = random.Random(0)


def draw():  # a viral object (100 hits) 5% of the time, otherwise 1 hit
    return 100.0 if rng.random() < 0.05 else 1.0


n, trials = 20, 100_000
prophet = median_bar = one_draw_bar = max_bar = 0.0
for _ in range(trials):
    values = [draw() for _ in range(n)]
    prophet += max(values)
    median_bar += single_item_one_sample(1.0, values)["value"]
    one_draw_bar += single_item_one_sample(draw(), values)["value"]
    max_bar += single_item_max_of_samples(values, [draw() for _ in range(n)])["value"]
for name, total in [
    ("prophet", prophet),
    ("median bar", median_bar),
    ("one past draw", one_draw_bar),
    ("max of 20 past draws", max_bar),
]:
    print(f"{name:22s} {total / trials:6.2f}  ratio {total / prophet:.3f}")

Its output (the expected values can also be checked by hand: the prophet earns \(100(1-0.95^{20}) + 0.95^{20} = 64.5\), the median bar \(0.05\cdot100 + 0.95 = 5.95\)):

Bar Average hits pinned Share of the prophet's 64.53
yesterday's median (always 1) 5.99 0.093
one past object's hits 8.91 0.138
the largest of 20 past objects (one per arrival), single_item_max_of_samples 43.66 0.677

With the median bar the rule pins the first object nearly every day, earning less than a tenth of the prophet. With the bar set to the largest of one past draw per arrival it earns two thirds, above the guaranteed half.

The precise statement

Setting. \(v_1, \dots, v_n\) are independent, nonnegative random values with distributions \(F_1, \dots, F_n\), revealed in a fixed order; an online rule accepts at most one, irrevocably.

Known distributions (Krengel–Sucheston, 1977; Samuel-Cahn, 1984). If the \(F_i\) are known, the rule "accept the first \(v_i \ge \tau\)", with \(\tau\) the median of the distribution of \(\max_i v_i\) (when the distributions have atoms, values equal to \(\tau\) are accepted with a suitable probability), earns at least \(\tfrac12\,\mathbb E[\max_i v_i]\). The factor \(\tfrac12\) cannot be improved in general.

One sample from each distribution (Rubinstein, Wang and Weinberg, 2020). If the \(F_i\) are unknown but you have one independent sample \(s_i \sim F_i\) for each arrival, the rule "accept the first \(v_i \ge \max_j s_j\)" earns at least \(\tfrac12\,\mathbb E[\max_i v_i]\).

Matroids. With known distributions, the factor \(\tfrac12\) extends to choosing a set of items subject to a matroid constraint (a family of "allowed" sets with an exchange property, such as "at most \(k\) items" or "at most one per category") (Kleinberg and Weinberg, 2012).

What no theorem gives. A bar equal to one scalar sample (one past draw, or a summary such as a median) has no constant guarantee, even when the values are independent and identically distributed. In the example above the ratio is 0.093; making viral objects rarer and arrivals more numerous drives it towards 0.

Where this result stands

In the wider literature: the single-item factor \(\tfrac12\) is a theorem with known distributions and with one sample from each distribution; the matroid factor \(\tfrac12\) is a theorem with known distributions. A constant factor for every matroid with only one sample per element, against an adversary who chooses the arrival order after seeing everything, is not established to our knowledge.

In this project's math catalog (result 111): such a rule exists for every matroid, with factor \(2^{-310} \approx 4.8\times10^{-94}\), with a Lean statement. The manuscript does not claim an efficient implementation.

What this library relies on: the single-item theorem with one sample per arrival (Rubinstein, Wang and Weinberg), for single_item_max_of_samples only; its module docstring carries the proof. Nothing from the catalog: it runs no matroid rule and never uses \(2^{-310}\) as a promise. See Where each result stands.

What the code does

Two helpers in grounded_decision/compare/prophet.py share one rule (take the first value that reaches the bar) and differ in where the bar comes from:

Helper Bar factor_claimed guarantee
single_item_max_of_samples(values, samples) the largest of samples, one past draw per arrival 0.5 "expected value >= 1/2 of the prophet's expected value, when values are independent and non-negative and each sample is an independent draw from the same distribution as its arrival (Rubinstein-Wang-Weinberg 2020)"
single_item_one_sample(sample, values) the scalar sample you pass None "none for an arbitrary scalar bar; 1/2 is guaranteed only for specific bars (use single_item_max_of_samples with one past sample per arrival)"

Both:

  1. Return the first index \(i\) with values[i] >= the bar.
  2. If none reaches the bar, return the last index (a nonempty stream always yields a choice).
  3. If values is empty, return index=None, value=None (single_item_max_of_samples instead raises ValueError when samples is empty or not the same length as values).

The result is a dictionary with index, value, threshold_sample (the bar), factor_claimed, guarantee, lean_factor=2**-310 (4.794e-94), the catalog reference and a note. It is not a decision record; nothing in it goes through the six checks unless you feed the choice into a module, as combo_cache_and_features does.

Every difference from the theorems:

  1. The samples must be what the theorem says. single_item_max_of_samples cannot check that each sample is an independent draw from the same distribution as its arrival. If yesterday's slot 3 is not like today's slot 3 (a weekday against a weekend), the 0.5 does not apply.
  2. factor_claimed=0.5 is about the average over many days, not any single day, and it compares with the prophet's average. Quote it in a service-level objective only in that form.
  3. A scalar bar carries no factor. single_item_one_sample reports None, whatever bar you pass, including a known-distribution median of the maximum (which does carry \(\tfrac12\) by Samuel-Cahn's theorem, but the helper cannot know that is what you passed).
  4. Independence and fixed order are assumed. If arrivals are correlated (a news event lifts every object) or the order depends on the values, the classical results do not apply as stated.
  5. One item only. There is no multi-slot or matroid version.
  6. The catalog factor is reported, never used. \(2^{-310}\) is on the result so an auditor can see that it was deliberately left out.

Limits, and what to do about them

Do not put 0.5 in an SLO for a median bar

The guarantee depends entirely on how the bar was chosen. With a bar from yesterday's median and heavy-tailed traffic, single_item_one_sample can earn a small fraction of the best value, as the table above shows, and it reports factor_claimed=None for that reason.

  • Getting a valid bar. Keep one past value per arrival slot (for example, the hits of the object published in the same hour yesterday) and call single_item_max_of_samples(values, samples) with them.
  • Check against your traffic. Replay last month: compare the value the helper would have pinned each day with the day's best. That ratio is your evidence; the 0.5 label is not.
  • More than one slot. Run a separate bar per slot only with care; the single-item guarantees do not compose. For \(k\) slots there are published rules for known distributions; this library does not implement them.
  • Fallback to the last item. If nothing reaches the bar, the helper takes the last arrival. If an empty slot is better than a poor object, check value against your own floor before pinning.