Let $F\_n$ be the empirical distribution obtained from an i.i.d. sample
of the distribution $F:R ^d \to [0, 1]$.
[Kiefer (1961)](http://www.ams.org/journals/tran/1958-087-01/S0002-9947-1958-0099075-1/S0002-9947-1958-0099075-1.pdf) shows that the convergence of the empirical distribution is like
$$
P\left( \left\lVert F\_n - F\right\rVert\_\infty > z \right) \le K \exp \left( - \left(2 - \epsilon\right) n z^2 \right)
$$
where the constant $K$ depends on the dimension $d$ and the threshold $\epsilon >0$.


What is the order of the constant $K$?  

Is it like $2^d$ or is it much smaller?


In the prood for the case [$d=1$](http://projecteuclid.org/euclid.aoms/1177728174), I see that $K$ is approximatively the tail of some distribution, so it is small.
For higher dimensions, the proof proceed by induction and I don't see how the value of $K$ evolves.


Definition of $F\_n$:  

For a vector $x$ in $R^d$, DKW defines the empirical distribution as the number of sample point $X\_i$ satisfying $X\_i < x$, coordinate-wise; divided by the number of sampled points $n$.


Reference:  

[DKW wiki](https://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_inequality)  

[DKW d=1: Dvoretzky, Kiefer, Wolfowitz 1958](http://projecteuclid.org/euclid.aoms/1177728174)  

[DKW d>1: Kiefer, Wolfowitz, 1958](http://www.ams.org/journals/tran/1958-087-01/S0002-9947-1958-0099075-1/S0002-9947-1958-0099075-1.pdf)  

[DKW d>1, sharp exponent: Kiefer, 1961](http://msp.org/pjm/1961/11-2/pjm-v11-n2-p17-p.pdf) 



What is the order of the constant $K$ in the multidimensional Dvoretzky-Kiefer-Wolfowitz inequality($Ke^{-c z}$)?
For any distribution $F$ over the naturals $\mathbb{N}$, one can show the following DKW-type inequality:
$$ \mathbb{P}(||F-F\_n||\_\infty > 1/\sqrt{n}+\epsilon)
\le \exp(-2n\epsilon^2)
$$
(in fact, it's known for the more general Markov case, see
<http://projecteuclid.org/euclid.jap/1421763330>
)


I started to write something about $F$ being well-approximated by discrete distributions, but now I think the question may be ill-posed. How do you define the empirical $F\_n$ in dimension $d>1$? In $R^1$ you can count how many sample points appeared to the left of $x$; what's the higher-dimensional analogue? For that matter, what's the analogue of a CDF in higher dimensions?


I'm leaving my answer because I think it's relevant for some reasonable reformulation of the question. The bottom line is that you should get dimension-free constants.


