Pith. sign in

REVIEW 4 minor 7 references

The classical DKW-Massart bound on empirical distribution functions follows from a discrete reverse martingale and a saddle-point argument.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-11 19:31 UTC pith:XHYKEBM7

load-bearing objection Clean discrete-martingale + Sion proof of classical DKW–Massart; pedagogical, not transformative, but the math checks out.

arxiv 2607.04387 v1 pith:XHYKEBM7 submitted 2026-07-05 math.PR math.STstat.TH

An Elementary Proof of the Dvoretzky--Kiefer--Wolfowitz--Massart Inequality

Jean-Yves Le Boudec This is my paper
classification math.PR math.STstat.TH MSC 60E1562G3060G42
keywords Dvoretzky-Kiefer-Wolfowitz inequalityMassart boundempirical distribution functiondiscrete reverse martingaleSion minimax theoremPinsker inequalityconcentration inequality
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves the one-sided Dvoretzky–Kiefer–Wolfowitz–Massart inequality: the probability that the empirical distribution of n i.i.d. samples exceeds its true cumulative distribution by more than ε is at most exp(−2nε²). Earlier proofs were long and technical; a recent continuous-time martingale proof is shorter but still involved. This work supplies a shorter, elementary argument that works entirely with a discrete reverse martingale, Doob’s inequality, Sion’s minimax theorem, and Pinsker’s inequality. The same bound is recovered without continuous-time machinery or the original technical estimates, making the classical concentration result more transparent for use in statistical tests and confidence bands.

Core claim

For any n and any ε > 0 the probability that the empirical distribution function ˆF_n exceeds the true F by more than ε is at most e^{−2nε²}. The bound is obtained by reducing to the uniform case, constructing a discrete reverse martingale from binomial counts, applying Doob’s inequality, interchanging an infimum and a maximum via Sion’s minimax theorem on a quasi-concave/quasi-convex function g, and finishing with Pinsker’s inequality on binary relative entropy.

What carries the argument

The function g(x, λ) = n log(1+λ) − x log(1 + λ/(x/n − ε)) on the rectangle [i*, n] × (0, ∞). Quasi-concavity in x and quasi-convexity in λ allow Sion’s theorem to turn the martingale bound into a clean minimization of binary Kullback–Leibler divergence, which Pinsker then converts into the exponential rate −2nε².

Load-bearing premise

That the auxiliary function g is quasi-concave in its first argument and quasi-convex in its second, so that Sion’s minimax theorem legitimately interchanges the infimum over the free parameter with the maximum over the discrete index.

What would settle it

Exhibit a pair (x, λ) inside the claimed domain for which the second-derivative case analysis of the auxiliary function h fails to establish quasi-concavity of g, or produce a numerical counter-example in which the resulting saddle value exceeds −2nε².

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The classical one-sided DKW-Massart bound holds for every ε > 0 by an elementary discrete argument.
  • Statistical tests and confidence bands that rely on the bound can cite a short, self-contained proof that uses only standard martingale and minimax tools.
  • The same reduction-to-uniform plus reverse-martingale template may be reused for other one-sided empirical-process inequalities.
  • The two-sided version follows at once by the union bound, recovering the familiar factor of 2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Because the argument never leaves discrete time, it may adapt more readily to lattice or integer-valued observations than continuous-time constructions.
  • Replacing Pinsker by a tighter divergence inequality could yield sharper constants for moderate ε without changing the rest of the proof.
  • The same saddle-point reduction might simplify concentration proofs for other empirical processes that admit a reverse-martingale representation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper proves the classical one-sided DKW–Massart inequality P(sup_x (ˆF_n(x)−F(x))>ε)≤e^{−2nε^{2}} for all ε>0 by a short elementary argument. After the standard reduction to the uniform case, it constructs a discrete reverse martingale M_i from binomial counts N_i, applies Doob’s inequality, relaxes the resulting discrete max to a continuous function g(x,λ), verifies that g is quasi-concave in x and quasi-convex in λ, invokes Sion’s minimax theorem to interchange inf and max, evaluates the saddle value as −n kl(x/n,x/n−ε), and finishes with Pinsker’s inequality. The two-sided form follows by the union bound. The argument is self-contained and uses only classical external tools (Doob, Sion, Pinsker).

Significance. The DKW–Massart bound is a foundational tool in nonparametric statistics and empirical-process theory; any genuinely shorter and more elementary proof is of lasting pedagogical and technical value. The manuscript replaces Massart’s long original argument and Reeve’s continuous-time martingale construction by a discrete reverse martingale plus a transparent saddle-point calculation. The derivation is fully explicit, free of fitted parameters, and recovers the sharp constant 2 via Pinsker. These features make the note a useful reference for both research and teaching.

minor comments (4)
  1. Lemma 1 is stated without proof and simply cites Dudley p. 39. A one-sentence sketch of the probability-integral-transform argument would make the note self-contained for readers who do not have Dudley at hand.
  2. In the definition of g (Eq. 5) and the subsequent display (16), the argument of the logarithm is written “1+λ/(x/n−ε)”. Parentheses around the denominator would eliminate any momentary ambiguity.
  3. The sentence after (13) that introduces log δ^*(λ) is slightly dense; a short clarifying clause that δ^* is chosen precisely so that {N_i≥i}⊂{M_i≥δ^*} for every i would improve readability.
  4. Typographical: “random variabiles” (p. 2), “left-handsides” (p. 1), and the inconsistent spacing around “i^*” appear in a few places; a light copy-edit would remove them.

Circularity Check

0 steps flagged

No circularity: self-contained derivation from Doob, Sion and Pinsker with no fitted parameters or self-referential definitions.

full rationale

The paper proves the classical one-sided DKW-Massart bound by a discrete reverse martingale (Mi), Doob’s inequality, an elementary quasi-concavity/quasi-convexity analysis of the function g that legitimates Sion’s minimax interchange, explicit evaluation of the resulting saddle value as -n kl(·,·), and Pinsker’s inequality. Every step is either a standard external theorem or a direct calculation performed inside the paper; no quantity is defined in terms of the target bound, no parameter is fitted to data, and the only citations are classical results (Doob, Sion, Pinsker, Dudley’s reduction to the uniform case). The derivation is therefore independent of its conclusion and exhibits zero circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

Pure mathematical derivation. No free parameters or invented physical entities. The load-bearing external ingredients are classical theorems of probability and convex analysis, each cited and used in their standard form.

axioms (4)
  • standard math Doob’s maximal inequality for non-negative reverse martingales
    Invoked in (12) to bound the probability that the reverse martingale M_i ever exceeds a threshold.
  • standard math Sion’s minimax theorem for quasi-concave/quasi-convex continuous functions on a compact convex set times a convex set
    Applied in Lemma 5 to interchange inf_λ max_x g = max_x inf_λ g after quasi-concavity and quasi-convexity of g are established.
  • standard math Pinsker’s inequality: kl(p+ε,p)≥2ε²
    Used in the final step (Section 2.4) to convert the binary KL lower bound into the quadratic exponent −2nε².
  • standard math The DKW inequality for a general continuous F reduces to the uniform[0,1] case
    Lemma 1, cited to Dudley; used to justify working exclusively with uniform order statistics.

pith-pipeline@v1.1.0-grok45 · 10163 in / 2295 out tokens · 36379 ms · 2026-07-11T19:31:46.574144+00:00 · methodology

0 comments
read the original abstract

The Dvoretzky--Kiefer--Wolfowitz--Massart inequality gives an upper bound on the probability that the empirical distribution function of a finite sequence of independent random variables deviates from its theoretical value. It is widely used in statistics in tests and in the production of confidence intervals. The original proof by Massart, later reformulated by Dudley, is very long and technical. Recently, Reeve slightly extends Dvoretzky--Kiefer--Wolfowitz--Massart inequality and presents an alternative, much shorter proof, that uses a continuous time martingale. We present a simpler and less technical proof of the original Dvoretzky--Kiefer--Wolfowitz--Massart inequality, based on a discrete-time martingale and Sion's minimax theorem.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

7 extracted references · 1 linked inside Pith

  1. [1]

    Asymptotic minimax character of the sam- ple distribution function and of the classical multinomial estimator.The Annals of Mathematical Statistics, pages 642–669, 1956

    Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sam- ple distribution function and of the classical multinomial estimator.The Annals of Mathematical Statistics, pages 642–669, 1956

    1956

  2. [2]

    The tight constant in the dvoretzky-kiefer-wolfowitz inequality.The annals of Probability, pages 1269–1283, 1990

    Pascal Massart. The tight constant in the dvoretzky-kiefer-wolfowitz inequality.The annals of Probability, pages 1269–1283, 1990

    1990

  3. [3]

    A short proof of the Dvoretzky–Kiefer–Wolfowitz–Massart inequality.arXiv preprint arXiv:2403.16651, 2024

    Henry WJ Reeve. A short proof of the Dvoretzky–Kiefer–Wolfowitz–Massart inequality.arXiv preprint arXiv:2403.16651, 2024

    Pith/arXiv arXiv 2024

  4. [4]

    Cambridge university press, 2014

    Richard M Dudley.Uniform central limit theorems, volume 142. Cambridge university press, 2014

    2014

  5. [5]

    On general minimax theorems

    Maurice Sion. On general minimax theorems. 1958

    1958

  6. [6]

    Elementary proof for Sion’s minimax theorem.Kodai mathematical journal, 11(1):5–7, 1988

    Hidetoshi Komiya. Elementary proof for Sion’s minimax theorem.Kodai mathematical journal, 11(1):5–7, 1988

    1988

  7. [7]

    Springer Science & Business Media, 2008

    Raymond W Yeung.Information theory and network coding. Springer Science & Business Media, 2008. 5

    2008