Return to Question

# 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}")

# 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 = 1 - 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}")

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.

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 each obersvation in the 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.

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 sample, $q_1,\ldots,q_n$. We are interested in the probability that the $q_i$ are all simultaneously close to $i/n$.

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$.