Episode 111, October 2026

One sample is enough?

A claimed matroid prophet inequality with one sample per element, against an adversary who sees everything

Covers result 111 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 111: One sample is enough? Bars for arriving values, a sample marker beside each, a dashed threshold, the gambler’s pick in teal and the prophet’s maximum in orange.

5:55. English captions available. The video loads from YouTube when you press play.

Chapters

The claims, in plain words

A prophet inequality compares a gambler with a prophet. Nonnegative values arrive one at a time; the gambler must accept or reject each on the spot, while the prophet sees them all and takes the best. With independent values from known distributions and a single choice, the gambler can always get half of the prophet’s expected value, and one half is best possible (Krengel and Sucheston, crediting Garling). One rule accepts the first value above half the prophet’s expected maximum.

Matroids generalize the constraint: the accepted set must stay independent, like edges that never close a cycle in a graph. Kleinberg and Weinberg extended the one-half guarantee to every matroid when the distributions are known and the order reacts only to values already seen. Without the distributions, one sample from each distribution can stand in for knowledge, and for a single choice the largest sample is a good threshold. For general matroids, a one-sample 1/2 appeared in September 2026 for arrival orders fixed in advance; when the order may depend on the values, one sample gave guarantees shrinking like one over log log of the rank, and constants needed many samples per element.

Result 111 is one OpenAI preprint (27 pages) dated September 23, 2026. It claims a single rule, using one sample per element and no description of the distributions, that earns in expectation at least 2⁻³¹⁰ times the prophet’s expected optimum on every finite matroid known in advance. The guarantee holds against an almighty adversary, who chooses the arrival order after seeing every sample, every value and the rule’s entire random seed. The values must be independent and nonnegative with finite expected optimum. The same argument gives a secretary rule that survives adversarial reordering after its observation phase.

What it doesn’t claim

No polynomial-time implementation is claimed, and the constant, about 5 × 10⁻⁹⁴, is far too small to matter in practice. The point is that it is a constant: it does not depend on the matroid, its size or rank, or the distributions.

Where it stands

Posted as a preprint: OpenAI, 27 pages, dated September 23, 2026
Peer reviewed: Not yet
Checked in Lean: OpenAI published a Lean proof of the theorem, its fixed-weight version and the secretary consequence; we have not run the check

Last checked October 19, 2026. The preprint has not been revised. OpenAI published a Lean formalization matched against the one-sample theorem and the fixed-weight and secretary statements: 125 files and 14,585 lines in the import closure of the one-sample and fixed-weight theorems, and 151 files and 17,139 lines with the secretary consequence, nothing outside Mathlib, with no unproved steps that we could find. The Lean proof reaches 2⁻²⁹³ and weakens it to the stated 2⁻³¹⁰. We have not run the check. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

Fixed hidden weights. Start from fixed hidden weights. A random mask, drawn from the seed, reveals some of them before any arrival, and those labels are sacrificed. The target is the expected minimum over all arrival orders, so the adversary may pick a different order for every seed; the fixed-weight version reaches 2⁻²⁹³. A coupling transfers this to the sample model: use the samples on the mask and the true values elsewhere; whatever the seed, the glued vector has exactly the law of the values.
Two branches. Weights are rounded down to powers of B = 2³². With probability one half, a maximum branch accepts the first unmasked label that outranks every revealed one, by rounded weight and then by label; with probability one quarter the top label is unmasked and the second masked, so this branch averages a quarter of the largest rounded weight even in the worst order for each seed. Otherwise the main branch builds nested paths of flats, sets closed under the matroid’s span, from the revealed weights, group by group from low to high, and accepts greedily within the layers between alternate flats; nesting keeps the union independent in every arrival order.
Three losses. Lighter arrivals may block a heavy group: independent guards enlarge each flat one step early, and exposing them backwards shows that a fixed fraction of the revealed labels stay safe. Those safe labels were revealed, so they are sacrificed: a counting bound on marked pivot patterns, with a union bound, shows that enough rank remains on unsacrificed labels. Enlarging the flats can reduce rank: a telescoping conditional-rank identity charges this only once along each path. After thinning, the remaining rank is a lower bound on the accepted count, for every order at once.
The constant. When no single label dominates, the main branch earns tγ/(16κ) of the rounded optimum, with t = 2⁻¹⁴⁰, γ = 2⁻¹⁶ and κ = 2¹⁰⁰; otherwise the maximum branch gives more. Mixing the branches and undoing the rounding gives tγ/(32κB) = 2⁻²⁹³; the theorem states 2⁻³¹⁰, with slack.

The numbers in the video

Known distributions, threshold half the expected maximum, worst arrival order: the gambler kept 0.65, 0.63 and 0.60 of the prophet’s value for exponential, uniform and Pareto families, and 1/(2 − 0.01) ≈ 0.503 on the two-point example where one half is tight.
The complete graph with 4 vertices has 38 forests and 16 spanning trees. With edge weights 1, 2, 3, 10, 20 and 30, a naive rule facing light edges first takes 6, against the prophet’s 53.
The maximum branch, computed exactly over all masks in the worst order, averaged at least 0.251 times the largest weight on 300 random weight vectors.
Gluing samples on the mask to values elsewhere: coordinate means within 0.4% of the values’.
2⁻³¹⁰ ≈ 4.79 × 10⁻⁹⁴; 2⁻²⁹³ ≈ 6.28 × 10⁻⁸⁹.

Read the source

One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary (PDF), 27 pages.
The Lean scope note.
The collection’s catalog, where this is result 111.

The paper

OpenAI groups related papers into one result; this one has a single paper.

One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary

Transcript

Read the full script

0:00Prophets and samples

A prophet inequality compares a gambler with a prophet. Nonnegative values arrive one at a time, and the gambler must accept or reject each on the spot, while the prophet sees them all and takes the best. With independent values from known distributions and a single choice, the gambler can always get half of the prophet’s expected value, and one half is the best possible: a classical result of Krengel, Sucheston and Garling. One rule accepts the first value above half the prophet’s expected maximum. In our check, that rule kept at least half in every family we tried, even in the worst arrival order, and just over half on the example where one half is tight. Matroids generalize the constraint: the accepted set must stay independent, like edges that never close a cycle in a graph. Kleinberg and Weinberg extended the one-half guarantee to every matroid when the distributions are known and the order reacts only to values already seen. Without them, one sample from each distribution can stand in for knowledge, and for a single choice the largest sample is a good threshold. For general matroids, though, a one-sample constant had appeared only this September, for orders fixed in advance; when the order may depend on the values, one sample gave guarantees shrinking like one over log log of the rank, and constants needed many samples per element. In our check, on the complete graph with 4 vertices, a naive rule facing light edges first earned 6, against the prophet’s 53.

1:32The claim

Result 111 is one OpenAI preprint, 27 pages, dated September 23. It claims that one sample per element suffices on every finite matroid known in advance. A single rule, which never sees a description of the distributions, earns in expectation at least 2^−310 times the prophet’s expected optimum. The guarantee holds against an almighty adversary, who chooses the arrival order after seeing every sample, every value and the rule’s entire random seed. The values must be independent and nonnegative, with finite expected optimum, and no polynomial-time implementation is claimed. The same argument gives a secretary rule that survives adversarial reordering after its observation phase. The constant, about 5 × 10^−94, is far too small to matter in practice. The point is that it does not depend on the matroid, its size or rank, or the distributions; with one sample and an order that depends on the values, earlier guarantees decayed with the rank. OpenAI published a Lean formalization of the prophet inequality and of the fixed-weight result behind it, about 125 files and 15,000 lines, together with the secretary consequence. We have not run the check.

2:55How the proof goes

The proof starts from fixed hidden weights. A random mask reveals some of them before any arrival, and those labels are sacrificed: the rule must reject them. The target is the expected minimum over all arrival orders, so the adversary may pick a different order for every seed. A simple coupling transfers this to the sample model: use the samples on the mask and the true values elsewhere; whatever the seed, the glued vector has exactly the law of the values. In our check, the glued coordinates matched the values’ means to within half a percent. Weights are rounded down to powers of 2^32. With probability one half, the rule runs a maximum branch: accept the first unmasked label that outranks every revealed one, by rounded weight and then by label. With probability one quarter the top label is unmasked and the second masked, so even with the worst order for each seed, this branch averages a quarter of the largest rounded weight. In our check, the exact worst-order average was at least a quarter on 300 random weight vectors. Otherwise the main branch builds nested paths of flats, sets closed under the matroid’s span, from the revealed weights, group by group from low to high. Within the layers between alternate flats it accepts greedily, and nesting keeps the union independent in every arrival order. Three losses must be controlled. Lighter arrivals may block a heavy group: independent guards enlarge each flat one step early, and exposing them backwards shows that a fixed fraction of the revealed labels stay safe. But those safe labels were revealed, so they are sacrificed: a counting bound on marked pivot patterns, with a union bound, shows that enough rank remains on unsacrificed labels. And enlarging the flats can reduce rank: a telescoping conditional-rank identity charges this cost only once along each path. After thinning, the remaining rank is a lower bound on the accepted count, simultaneously for every order. Summing over weight levels, when no single label dominates, the main branch earns a fixed fraction of the rounded optimum, built from the constants 2^−140, 2^−16 and 2^100. Mixing the two branches and undoing the rounding gives 2^−293 for fixed weights, so the stated 2^−310 leaves slack.

5:22Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers the theorem, its fixed-weight version and the secretary consequence; we have not run it. It is not among the papers OSVerify reviewed, and we have seen no expert review. If it holds, one sample per element is enough for a constant-factor matroid prophet inequality, even against an adversary who sees everything; the constant is just astronomically small.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.