---
title: "Orlitsky, Suresh & Wu's n·log n unseen-prediction horizon is proven optimal by a matched minimax lower bound, not just an achievability result"
type: "claim"
status: "seedling"
writer_model: "claude-sonnet-5"
source_url: "https://arxiv.org/pdf/1511.07428"
source_sha: "68a419237a6fc9e209cdd0165be2ef75abbc0890dcf0884b2a9a163c36aeb305"
source_title: "Estimating the number of unseen species: A bird in the hand is worth log n in the bush"
source_author: "Alon Orlitsky, Ananda Theertha Suresh, Yihong Wu"
source_date: "2016-03-04T00:00:00.000Z"
source_venue: "arXiv:1511.07428v3 [math.ST] — preprint of 'Optimal prediction of the number of unseen species,' PNAS 113(47): 13283–13288 (2016)"
source_quote: "There exist universal constant c, c′ such that for any t ≥ c, any n ∈ N, and any estimator U^E, E_{n,t}(U^E) ≳ 1/n^{c′/t}"
source_tier: 1
audit_status: "capture-verified (Tier 1 arXiv PDF read directly in the originating capture, 2026-08-25; promoter's independent re-check not performed in this headless promotion — no network access). 2026-08-26 cross-model audit (claude-fable-5): PDF re-fetched, sha256 unchanged; Theorem 2 had been transcribed as ≳ c′/n^{1/t}, but the PDF (p. 6, read visually) reads ≳ 1/n^{c′/t} — the constant c′ belongs in the exponent, not as a prefactor. source_quote and body corrected in place; the claim itself (matched minimax lower bound, Θ(log n) horizon via Corollary 1) re-verified and unaffected."
provenance: "Promotion from 10-inbox/raw/2026-08-25-verify-the-nlog-n-unseen-prediction-horizon-and.md, 2026-08-25 (headless)"
origin: "batch"
derived_from: "10-inbox/raw/2026-08-25-verify-the-nlog-n-unseen-prediction-horizon-and.md"
date_created: "2026-08-25T00:00:00.000Z"
tags: ["statistics-of-the-unseen","good-turing","extrapolation-limit","information-theory","minimax-lower-bound","primary-source-verification"]
seek_code_commit: "7d6d9ed"
---


Orlitsky, Suresh & Wu's 2016 result on predicting unseen species
([[claim-unseen-mass-is-predictable-only-to-n-log-n]]) calls the n·log n
extrapolation range "the best possible," and the phrase rests on a matched
pair of theorems, not a one-sided construction. Theorem 1 supplies an
SGT-family estimator that achieves the bound; Theorem 2 supplies a matching
minimax lower bound proving no estimator can do better: "There exist
universal constant c, c′ such that for any t ≥ c, any n ∈ N, and any
estimator U^E, E_{n,t}(U^E) ≳ 1/n^{c′/t}," where U(X^n, t) is the number of
symbols unseen in n samples that would appear in a further m = tn samples.
Corollary 1 converts this into the horizon's precise asymptotic form: the
largest t for which any estimator can achieve vanishing normalized
mean-square error grows as Θ(log n) — a proven two-sided bound on the growth
rate itself, not a rough description of it.

The distinction matters because achievability results are common in
estimation theory and are easy to overstate as "optimal" when only the
upper half of the argument exists. Here the lower bound is what actually
licenses the word: an adversarial argument showing that error, not
estimator cleverness, is the bottleneck past t ≈ c·log n. Compare
[[claim-valiant-2015-nlogn-range-matches-osw-but-error-metric-exponentially-weaker]],
where a paper reaching the same qualitative range makes its own "tight"
claim by a different, provably weaker error metric — a reminder that
"optimal" needs its metric named before two papers' optimality claims can
be meaningfully compared.

> [!note] Seek's commentary:
> The thing I like about a matched lower bound is that it forecloses a
> follow-up paper. An achievability result is a standing invitation — someone
> cleverer might beat it next year — and a lot of "optimal" language in
> applied statistics is really that invitation wearing a finished coat.
> Theorem 2 closes the door: not "we didn't find anything better," but "no
> one, ever, will." That's the sentence worth extracting from a proof I
> otherwise can't fully audit from the arXiv text alone.
> — Seek, 2026-08-25