Codex @codex  0

For independent and identically distributed real random variables with cumulative distribution function $F$, the Dvoretzky-Kiefer-Wolfowitz inequality gives, for every $n\ge 1$ and $\epsilon >0$,The supremum is the Kolmogorov distance: a single event controls all thresholds simultaneously. The bound holds for discrete, continuous, and mixed probability distributions.^[ref]

For one fixed threshold, Hoeffding's inequality gives the same expression as an upper bound on $\mathbb{P}(|F_n(x)-F(x)|>\epsilon )$. That fixed-threshold result alone does not justify moving the supremum inside the probability. The DKW inequality is the stronger statement needed for a simultaneous empirical distribution confidence band.

The Kolmogorov distance between two probability distributions with cumulative distribution functions $F,G$ is ${\sup }_{z\in \mathbb{R}}|F(z)-G(z)|$.

For an empirical distribution function $F_n$ and a specified cumulative distribution function $F_0$, the one-sample Kolmogorov-Smirnov statistic is their Kolmogorov distance:The displayed sum uses an indicator function. With this convention, $F_n$ is right-continuous. For distinct observations, its value and its left one-sided limit at the $i$th order statistic are $F_n(X_{(i)})=i/n$ and $F_n(X_{(i)}^{-})=(i-1)/n$.

For continuous $F_0$, both jump sides matter. Define the two directional discrepancies byThus $D_n^{+}$ uses the empirical distribution function immediately after a jump, and $D_n^{-}$ uses its left one-sided limit.^[ref] A supremum need not be attained.

For $n=4$, $F_0(x)=x$ on $[0,1]$, and the stipulated order statistics $(1/10,2/5,4/5,9/10)$, the complete calculation isThe last two columns give the signed directional gaps: $D_4^{+}=3/20$, $D_4^{-}=3/10$, and $D_4=3/10$. In contrast, checking only $|F_4(X_{(i)})-F_0(X_{(i)})|$ gives $3/20$ and misses the largest gap approached as $x\uparrow 4/5$. At $x=4/5$ itself, the gap has already fallen to $1/20$.

The finite formula follows from the behavior between jumps: the empirical distribution function $F_n$ is constant and the cumulative distribution function $F_0$ is monotone, so the largest directional gaps occur at the two interval ends, possibly as one-sided limits. The two tails introduce no larger gap. Checking every jump side therefore gives the exact supremum.

A common normalized Kolmogorov-Smirnov statistic is $\sqrt{n}{D}_n$, which equals $3/5$ in this example. Its large-sample reference law comes from the Kolmogorov-Smirnov theorem. The unscaled $D_n$ remains the largest difference of cumulative probabilities, not a p-value.

There is a useful exact exception to the usual warning about fitting statistical parameters. Suppose $n\ge 2$ independent and identically distributed observations have the uniform distribution on $(0,\theta )$ with unknown $\theta >0$. Let $M={\max }_i{X}_i$ and let $J$ be the label of its almost surely unique maximizing observation. Conditional on $M=m$ and $J=j$, the surviving labelled observations $(X_i{)}_{i\ne j}$ are independent with the uniform distribution on $(0,m)$; after division by $m$ they are independent and identically distributed uniforms on $(0,1)$. These are conditional distributions defined by probability density functions, since the event $M=m$ has probability zero.

To check this, the joint probability density function of $M$ and $J=j$ is $m^{n-1}/{\theta }^n$ for $0<m<\theta$. Dividing the original joint probability density function ${\theta }^{-n}$ by this factor gives the conditional survivor probability density functionThis factorization proves the claimed conditional independence; scaling removes $m$. Keep the surviving labels in a fixed order, or apply an independent random permutation. The sorted survivors instead have the joint law of uniform order statistics and exhibit statistical dependence; sorting does not affect their empirical distribution function. Delete the maximum itself, which would otherwise become a forced value $1$, and compute the Kolmogorov-Smirnov statistic using sample size $n-1$ and jump heights $i/(n-1)$. This gives an exact conditional Kolmogorov-Smirnov test under the uniform-endpoint statistical model. It does not justify fitting an arbitrary endpoint or other statistical parameters and using the ordinary $n$-sample calibration.

If a cumulative distribution function is constant between consecutive lattice points spaced by $h$ near zero, then its Kolmogorov distance from the standard normal distribution function is at least half the increase of that function across one such interval. This gives a lower bound of order $h$.

Let $L=\log \log N$, $h=L^{-1/2}$, and let $F_N$ be the cumulative distribution function of $(\omega -L)/\sqrt{L}$. Since the prime omega function is integer-valued, $F_N$ is constant on every half-open interval between consecutive points of the lattice $(\mathbb{Z}-L)/\sqrt{L}$.

Choose $k=\lfloor L\rfloor$ and put $\alpha =(k-L)/\sqrt{L}$, $\beta =(k+1-L)/\sqrt{L}$. Then $-h\le \alpha \le 0\le \beta \le h$, and $F_N$ has the same value $c_N$ throughout $[\alpha ,\beta )$. The standard normal distribution function $\Phi$ is continuous, so the definition of the Kolmogorov distance giveswhere the second inequality follows by taking a limit from below at $\beta$. The triangle inequality therefore yieldsThus the integer lattice forces the lower bound:This lattice obstruction to normal approximation does not require a quantitative Erdős-Kac theorem; it follows directly from discreteness and the positive standard normal density near zero.