massart1990tight

The Tight Constant in the Dvoretzky–Kiefer–Wolfowitz Inequality

Authors: P. Massart · Year: 1990 · Venue: The Annals of Probability, Vol. 18, No. 3, pp. 1269–1283 (July 1990) · DOI: 10.1214/aop/1176990746 · Raw: not converted — see the warning below. Open-access PDF: Project Euclid.

No raw md — OCR too degraded to transcribe

firecrawl retrieved the complete 15-page article (through the References section) from Project Euclid’s open-access PDF, but the text layer is a corrupted JSTOR-OCR/LaTeX-source hybrid: display equations come through duplicated as separate mangled fragments (e.g. Corollary 1 renders as P(\,D\,D D\,>\,\lambda) instead of P(D_n>\lambda)), digits drop or double (\22\lambda^2 for 2\lambda^2), and prose sentences interleave with raw uncompiled LaTeX. Per the OCR-quality gate, no Docs/raw/md/massart1990tight/ was written. The published abstract quoted below was scraped cleanly from the Project Euclid landing page (not OCR’d) and is the only in-corpus transcription — it already states the theorem this page exists to cite. Re-attempt via a MathSciNet/zbMATH-linked reprint or a direct library PDF if the full derivation (Lemma 1/2, Proposition 1/2) is ever needed.

Summary

Proves the tight constant in the (one- and two-sided) Dvoretzky–Kiefer–Wolfowitz inequality for the empirical distribution function. Dvoretzky, Kiefer and Wolfowitz (1956) had shown $P(\sqrt{n}{\sup }_x({\hat{F}}_n(x)-F(x))>\lambda )\le C\exp (-2{\lambda }^2)$ for an unspecified constant $C$; Birnbaum and McCarty (1958) conjectured $C=1$ was achievable. Massart proves the conjecture (Theorem 1) subject to a mild constraint on $\lambda$, and derives from it the unconstrained two-sided bound $P(\sqrt{n}{\sup }_x|{\hat{F}}_n(x)-F(x)|>\lambda )\le 2\exp (-2{\lambda }^2)$ (Corollary 1), holding for all $n$ and $\lambda >0$ — the form now cited as the “DKW–Massart” inequality. Both the one-sided constant $1$ and the two-sided constant $2$ are shown to be un-improvable, via the classical Smirnov (1944) asymptotic expansion.

Key Claims

• Theorem 1. For any integer $n$ and any $\lambda \ge \sqrt{[\log 2]/2}\wedge \gamma n^{-1/6}$ ($\gamma =1.0841$), $P(D_n^{-}>\lambda )\le \exp (-2{\lambda }^2)$, where $D_n^{-}=\sqrt{n}{\sup }_x({\hat{F}}_n(x)-F(x))$.
• Corollary 1 — the tight DKW bound. For all integer $n$ and any $\lambda >0$: $P(\sqrt{n}{\sup }_x|{\hat{F}}_n(x)-F(x)|>\lambda )\le 2\exp (-2{\lambda }^2)$, with no restriction on $\lambda$ — this is the form used downstream.
• Comment 1. Theorem 1’s constraint on $\lambda$ is automatically satisfied whenever $\exp (-2{\lambda }^2)\le \frac{1}{2}$, i.e. the statistically relevant small-tail-probability regime.
• Comment 2(ii). The constants $1$ (one-sided) and $2$ (two-sided) cannot be further improved — tightness follows from the Smirnov (1944) asymptotic expansion, not merely from a loose proof technique.
• Theorem 2 (by-product). A Bernstein/Hoeffding-type exponential tail bound for binomial random variables, obtained en route to Theorem 1 via a Cramér-transform lower bound (Lemma 1).

Method

Reduces the one-sided statistic $D_n^{-}$ to a boundary-crossing problem for a normalized empirical process, then compares the exact finite-$n$ crossing-time law (Smirnov 1944; Csáki 1974; Bretagnolle–Massart 1989) against the limiting Brownian-bridge crossing density $f_{\lambda }$ term-by-term (Proposition 1) — itself built on a sharp Cramér-transform bound for the Bernoulli law (Lemma 1) and a positivity lemma (Lemma 2) controlling the resulting correction terms. Small/moderate $n$ ($n\le 38$) are closed by direct numerical bounding of a finite family of cases (Proposition 2).

Regime note. A pure probability-theory paper — empirical processes / Kolmogorov–Smirnov statistics, no robot, no dynamics, no spacecraft. Its relevance here is strictly as a concentration-inequality tool.

Relevance to thesis

Primary source for the DKW/Massart wall, documented as a proof-obligation interface in the risk-aware planning phase (quantile concentration) — the gap currently flagged as “DKW absent (quantile concentration)” in risk_future_push.md. The wall stays a documented interface, not a proof target: the thesis cites Corollary 1’s tight two-sided bound $P(\sqrt{n}{\sup }_x|{\hat{F}}_n(x)-F(x)|>\lambda )\le 2e^{-2{\lambda }^2}$ to justify a finite-sample confidence band on an empirical CDF/quantile used in the risk-aware layer, without re-proving it or formalizing it in Lean. Complements moment_concentration_bound (a different concentration mechanism — Hotelling-$T^2$/${\chi }^2$ moment margins, not a sup-norm CDF bound) and chance_constraints (the constraint form this concentration result would certify).

Connections

Topics: Moment Concentration Bound · Chance Constraints Sources: majumdar2017how · akella2024risk · hakobyan2019risk

Key Equations / Quotes

From the abstract (verbatim, scraped cleanly from the Project Euclid landing page — not OCR’d):

“Let ${\hat{F}}_n$ denote the empirical distribution function for a sample of $n$ i.i.d. random variables with distribution function $F$. In 1956 Dvoretzky, Kiefer and Wolfowitz proved that $P(\sqrt{n}{\sup }_x({\hat{F}}_n(x)-F(x))>\lambda )\le C\exp (-2{\lambda }^2)$, where $C$ is some unspecified constant. We show that $C$ can be taken as $1$ (as conjectured by Birnbaum and McCarty in 1958), provided that $\exp (-2{\lambda }^2)\le \frac{1}{2}$. In particular, the two-sided inequality $P(\sqrt{n}{\sup }_x|{\hat{F}}_n(x)-F(x)|>\lambda )\le 2\exp (-2{\lambda }^2)$ holds without any restriction on $\lambda$. In the one-sided as well as in the two-sided case, the constants cannot be further improved.”

Open Questions

• PAGE NEEDED: a topics/ page for the DKW/Massart quantile-concentration inequality itself (distinct from moment_concentration_bound) — not yet created; this source page stands alone as the interface until the risk-phase A6 obligation is actually engaged.
• Full-text conversion is blocked on OCR quality (see the warning banner); revisit via a MathSciNet/zbMATH-linked reprint or a direct library scan if the equation-level derivation (Lemma 1/2, Proposition 1/2) is ever needed rather than just the tight-constant citation.
• Which specific quantile/CDF estimate in the risk-aware planning layer (A6) will actually invoke Corollary 1, and at what confidence level / sample size — undetermined; this page only seals the citation.