The Kolmogorov Distance between the Binomial and Poisson Laws: Efficient Algorithms and Sharp Estimates

Abstract

We give efficient algorithms, as well as sharp estimates, to compute the Kolmogorov distance between the binomial and Poisson laws with the same mean λ. Such a distance is eventually attained at the integer part of λ+1/2−λ+1/4. The exact Kolmogorov distance for λ≤2−2 is also provided. The preceding results are obtained as a concrete application of a general method involving a differential calculus for linear operators represented by stochastic processes.