[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][1] 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! ``` [1]: https://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_inequality