Best approximation of normal with $m$ atoms in Kolmogorov-Smirnov distance

Question

Let $d_{KS}(F,G)= \sup_{x} |F(x) -G(x)|$ be the Kolmogorov-Smirnov distance between two cdfs $F$ and $G$.

Question: Let $F_m$ be a cdf of distribution with $m$ atoms and let $\Phi$ bet the distribution of standard normal. What can we say about \begin{align} g(m)=\inf_{F_m} d_{KS}(F_m,\phi) \end{align} In other words, we are looking for the best approximation of Gaussian by $m$ atoms. I am especially interested if we know the lower bound on $g(m)$. I highly suspect that this problem is either solved or there are good bounds, but I couldn't find a solution in the literature.

Answer 1

The best difference is $\frac{1}{2m}$, attained by the distribution with $m$ atoms, each with mass $\frac{1}{m}$, at the points where the cdf of the normal distribution takes the values $\frac{2i-1}{m}$ for $i$ from $1$ to $m$.

Proof that this is optimal: One atom must have mass at least $\frac{1}{m}$. Call this $x$. Then \begin{align} \frac{1}{m} & \leq F_m(x+\epsilon) - F_m(x-\epsilon) \\ & \leq |F_m(x+\epsilon) -\Phi(x+\epsilon) | + | \Phi(x+\epsilon) -\Phi(x-\epsilon)| + |\Phi(x-\epsilon) - F_m (x-\epsilon)|\\ & \leq d_{KS} (F_m, \Phi)+ | \Phi(x+\epsilon) -\Phi(x-\epsilon)| + d_{KS}(F_m,\Phi) \end{align}

and as $\epsilon$ goes to $0$, $| \Phi(x+\epsilon) -\Phi(x-\epsilon)|$ goes to $0$ because $\Phi$ is continuous, so

$$\frac{1}{m} \leq 2 d_{KS}(F_m,\Phi)$$ showing the desired optimality.

Of course, this has nothing to do with the Gaussian, and works for any continuous distribution.