From n samples, the unseen can be predicted only about n·log n observations further, and that horizon is provably the best possible (Orlitsky, Suresh & Wu 2016)

statistics-of-the-unseengood-turingextrapolation-limitcompletenessinformation-theory

The unseen tail is estimable, but not indefinitely. Orlitsky, Suresh & Wu (PNAS 2016) proved that from a sample of size n, the number of newly appearing elements can be predicted reliably only about n·log n further observations out — and that this range "is the best possible," via a matched achievability result and minimax lower bound (claim-orlitsky-suresh-wu-nlogn-horizon-proven-optimal-via-matched-minimax-lower-bound). The memorable title "a bird in the hand is worth log n in the bush" is Orlitsky, Suresh & Wu's own — it is the subtitle of their own arXiv preprint, not Valiant & Valiant's (corrected 2026-08-25; see Correction history below). Valiant & Valiant's 2015 paper does independently reach the same n·log n-scale range, but by a different, provably weaker error metric (claim-valiant-2015-nlogn-range-matches-osw-but-error-metric-exponentially-weaker); their real non-concurrent antecedent is a distinct, earlier 2011 paper on a different problem (claim-valiant-2011-stoc-paper-is-real-nonconcurrent-nlogn-antecedent). Beyond the n·log n horizon the tail is provably unknowable: no estimator, however clever, can extrapolate further from the sample alone.

This is the hard caveat that the diagnostic (claim-singletons-are-the-diagnostic-of-the-unseen) and the coverage machinery (claim-paleobiology-reinvented-coverage-based-rarefaction-as-quorum-subsampling) do not by themselves supply. It bears directly on the vault's No-Change Assumption: treating "no new facts arriving" as proof that a region is complete is licensed only inside a log-factor window. For a heavy-tailed corpus, the absence of new captures certifies completeness only out to ≈ n·log n; past that, the rare tail is formally beyond reach, and silence is not evidence of exhaustion. It is the information-theoretic backstop under the vault's gap-detection thread (claim-obligatory-attributes-as-gap-signal, question-gap-detection).

Resolved 2026-08-25. The bound and its optimality are now confirmed directly against Orlitsky, Suresh & Wu's own arXiv preprint (Tier 1) — question-verify-orlitsky-nlogn-unseen-horizon-primary is answered. The note stays seedling per house convention for a directly-confirmed but not yet independently cross-audited note (see the Chao-1984 notes for the same pattern).

Correction history.

• 2026-08-25 — The note previously read: "Valiant & Valiant reached the same limit concurrently, memorably titling the phenomenon 'a bird in the hand is worth log n in the bush.'" A direct read of Orlitsky, Suresh & Wu's own arXiv preprint (arXiv:1511.07428) found the title is theirs — it is the subtitle printed on their own paper's header — not Valiant & Valiant's. It also found the "reached the same limit concurrently" framing had compressed two distinct Valiant-authored papers, four years apart, on two distinct problems, into one sentence. See claim-valiant-2015-nlogn-range-matches-osw-but-error-metric-exponentially-weaker and claim-valiant-2011-stoc-paper-is-real-nonconcurrent-nlogn-antecedent for the corrected accounting, and 10-inbox/raw/2026-08-25-verify-the-nlog-n-unseen-prediction-horizon-and.md for the capture that found it.