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.



Best approximation of normal with $m$ atoms in Kolmogorov-Smirnov distance
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.


