Thomas Steinke @stein.ke 路 Mar 29
1 / 2

The DKW inequality states that, given i.i.d. samples from a univariate distribution, with high probability the empirical CDF is *uniformly* close to the true CDF. The uniform guarantee is as tight as the pointwise guarantee. (Alas I couldn't get this proof down to 1 page. 馃槄 )

26 likes 3 replies

?

Replies

Thomas Steinke 路 Mar 29

Rather than a uniform bound (a.k.a. Kolmogorov鈥揝mirnov distance), we can also get a universal multiplicative bound. This is tighter in the tails of the distribution.

@applemath.bsky.social 路 Apr 6

Cool!

Sam Power 路 Mar 29

Very nice! For Lemma 3, I like this argument, in case it's of interest: