Skip to main content
7 of 9
added 5 characters in body
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Violating an order statistic inequality?

[Edit: for posterity, I'm adding two small comments to the code explaining how to fix it, in light of Iosef Pinelis' answer below. Look for "Should be:" to find the corrections.]

Suppose we draw a sample of $n$ i.i.d. observations from some continuous distribution on $\mathbb{R}$. Sort these observations from smallest to largest and call them $x_1,\ldots,x_n$. We consider the quantile corresponding to each observation, $q_1,\ldots,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,\ldots,n}\left|q_i-\frac{i}{n}\right|>\varepsilon\right] \leq 2 e^{-2n\varepsilon^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 with disparity below the DKW bound
prob_true = np.sum(disparity_list < epsilon_DKW) / num_trials
# Compute the *actual* bound such that prob_DKW fraction of
# trials have disparity below the bound
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!