[Edit: for posterity, I'm adding two small comments to the code explaining how to fix it, in light of the answer below. Look for "Should be:"]
Suppose we draw $n$ i.i.d. samples from some continuous distribution on $\mathbb{R}$. Sort these samples from smallest to largest and call them $x_1,...,x_n$. We consider the quantile corresponding to each sample, $q_1,...,q_n$. We are interested in the probability that the $q_i$ are all simultaneously close to $i/n$.
The DKW inequality shows that $$ \Pr\left[\max_{i=1,...,n}\left|q_i-\frac{i}{n}\right|>\epsilon\right] \leq 2 e^{-2n\epsilon^{2}} $$ Note that this result holds for all $n$ and there are no hidden constants.
It is extremely straightforward to run a Monte Carlo simulation of this process. The uniform distribution on $[0,1]$ is particularly convenient to use since a sample equals its own quantile (i.e., $x_i=q_i$). I've shared some Python code; 1 million Monte Carlo trials take about 10 seconds.
My simulation appears to violate the DKW inequality. Question: What's going on?
# Double-check the DKW Inequality
import numpy as np
################
# Set parameters
#
# "prob_target" is the probability of *satisfying* the bound
# (i.e., that the gap is less than epsilon)
prob_target = 0.99
# We consider the CDF of "n" samples
n=20
# We are going to use "num_trials" Monte Carlo runs, where each run
# consists of "n" draws from a Uniform distribution
num_trials=1000000
print(f"Parameters: n={n}, # trials={num_trials}, target probability={prob_target}")
#######################
# Compute DKW threshold
epsilon_DKW = np.sqrt(np.log(2.0 / prob_target) / (2.0 * float(n)))
# Should be:
# epsilon_DKW = np.sqrt(np.log(2.0 / (1-prob_target)) / (2.0 * float(n)))
# Double-check that we actually computed the intended probability;
# hopefully prob_target == prob_DKW
prob_DKW = 2 * np.exp(-2 * n * (epsilon_DKW**2))
# Should be:
# prob_DKW = 2 * np.exp(-2 * n * (epsilon_DKW**2))
assert np.isclose(prob_target, prob_DKW)
print(f"Computed parameters: epsilon_DKW ={epsilon_DKW:.6f}, prob_DKW={prob_DKW:.6f}")
########################
# Monte Carlo simulation
disparity_list = np.zeros(num_trials)
ecdf = np.arange(1, n+1)/n # = [1/n, 2/n, ..., n/n]
for trial in range(num_trials):
data = np.random.uniform(size=n)
data = np.sort(data)
quantiles = data # ...because uniform distribution on [0,1]
worst_disparity = np.max(np.abs(quantiles-ecdf))
disparity_list[trial] = worst_disparity
# Compute fraction of trials for which DKW bound holds
prob_true = np.sum(disparity_list < epsilon_DKW) / num_trials
# Compute the *actual* bound that acheives prob_DKW fraction of trials
epsilon_true = np.quantile(disparity_list, prob_DKW)
###############
# Print results
print(f"Measured threshold: epsilon_best={epsilon_true:.6f}")
if prob_true < prob_DKW:
print("\nWe have a problem.")
print(f"DKW promises success probability at least {prob_DKW:.6f}, ")
print(f"but we only observe probability {prob_true:.6f}")
print(f"The required epsilon is {epsilon_true / epsilon_DKW:.6f}x larger than DKW!")
else:
print(f"DKW Inequality works! Success probability={prob_true:.6f}>={prob_DKW:.6f}")
Here's the result of the run:
Parameters: n=20, # trials=1000000, target probability=0.99
Computed parameters: epsilon_DKW =0.132589, prob_DKW=0.990000
Measured threshold: epsilon_best=0.335025
We have a problem.
DKW promises success probability at least 0.990000,
but we only observe probability 0.333689
The required epsilon is 2.526787x larger than DKW!