# How to arrange the multivariate DKW inequality to an upper bound on n?

The multivariate DKW inequality is given by

$$\Pr \left[ \sup_{t \in \mathbb{R}^k} \left| F_n(t) - F(t) \right| > \epsilon \right] \leq (n+1)k e^{-2n\epsilon^2},$$

where $$F_n(t)$$ is the eCDF, $$F(t)$$ is the population CDF, $$\epsilon \in \mathbb{R}_{>0}$$, and $$n,k \in \mathbb{N}$$.

What I want to find is an upper bound for $$n$$ given the other inputs. I attempted using the Lambert $$W$$ function but I was unsuccessful in arranging things into the right form to apply it.

• This is really a purely mathematical question, because it looks like you are asking to find the largest positive zero of a function of the form $(n+1)e^{-\alpha^2 n} - c$ where $c\ge 0.$ Use a numerical root finder or, if you need theoretical results, analyze this function using ordinary Calculus techniques. You have many options depending on the magnitude of $\alpha$ or the expected magnitude of $n.$ For instance, with $n\gg 1,$ you could approximate this as $$\log(n) = \log(c) + \alpha^2 n.$$ In any event, a few iterations of Newton-Raphson ought to do the trick.
– whuber
Commented May 12 at 15:31

You are looking for the largest (real) root of the function

$$f(n; p,k,\epsilon) = \log(1 + n) - \log(p/k) - 2\epsilon^2 n$$

where $$p$$ is the probability on the left hand side and I have taken logarithms after dividing both sides by $$k\ge 1.$$

Because $$0 \lt p/k \ll 1$$ and we may assume $$0 \lt \epsilon \lt 1,$$ the graph of $$f$$ generically looks like this solid black curve (plotted for $$p=0.05,$$ $$k=2,$$ and $$\epsilon = 1/10$$):

The maximum of $$f$$ is found by equating its derivative to $$0,$$ with the solution

$$n_* = \frac{1}{2\epsilon^2}-1.$$

The Taylor series of $$f$$ at this point is

$$f(n) = f(n_*) - \frac{1}{2} \frac{1}{(1 + n_*)^2} (n - n_*)^2 + O((n-n_*)^3).$$

The red curve in the figure plots this quadratic approximation.

You can readily check that the constraints on $$p/k$$ and $$\epsilon$$ imply the quadratic is always less than $$f$$ for $$n\gt n_*$$ and that in this region (to the right of the peak) $$f$$ is concave down. Thus, we can easily find the zero of the quadratic approximation in this region (shown with the vertical dotted red line) and compute the derivative of $$f$$ there, thereby obtaining the equation of the tangent line to $$f$$ as shown by the dotted black line.

The concavity of $$f$$ implies the zero of this tangent line exceeds the rightmost zero of $$f:$$ it is an upper bound. It tends to be a pretty good one, as suggested by the figure. But if you want a better one, take one or more Newton-Raphson steps (because that's what we're doing): these will continually improve the upper bound, converging (extremely rapidly) to the root from above.

The resulting formulas get ever more complex, but they are rational functions of $$\epsilon^2,$$ its logarithm, and $$\log(p/k),$$ because all the derivatives of $$f$$ are rational functions.

If you need to, you can obtain bounds on the error of this approximation using any version you like of the Taylor theorem with remainder. In this manner you can consider this approach both a numerical algorithm, useful in practice, as well as an analytical (asymptotic) formula useful for proving general results.