An optimal approximation of discrete random variables with respect to the Kolmogorov distance
This work addresses a fundamental problem in probability theory and computational statistics, with potential applications in data compression, simulation, and machine learning, though it appears incremental as it builds on existing approximation methods.
The paper tackles the problem of approximating a discrete random variable with a smaller support while minimizing the Kolmogorov distance, presenting an algorithm that achieves this optimal approximation with theoretical correctness and computational complexity analysis, and includes empirical evaluation across various applications.
We present an algorithm that takes a discrete random variable $X$ and a number $m$ and computes a random variable whose support (set of possible outcomes) is of size at most $m$ and whose Kolmogorov distance from $X$ is minimal. In addition to a formal theoretical analysis of the correctness and of the computational complexity of the algorithm, we present a detailed empirical evaluation that shows how the proposed approach performs in practice in different applications and domains.