How do you call the problem of approximating a continuous distribution with a simple discrete distribution?

Question

The following problem came up on the Mathematica forum as "Generating a list of integers that roughly satisfy a distribution": Given $n$, find $n$ integers (possibly with duplicates) whose distribution approximates a given normal distribution.

For example, given a normal with mean 25 and standard deviation 7, the following multiset could be a decent candidate :

{11,15,17,18,20,21,22,23,24,25,25,26,27,28,29,30,32,33,35,39}

I understand that the term "approximates" is not properly defined and there may be several ways of fixing that. For example, one could specify that random samples taken from the discrete distribution should "look like" (again, need to specify what "looks like means") they are drawn from the continuous distribution (conditioning the normal distribution on integrality or after rounding).

Are there references on that problem?

Answer 1

It sounds like you want evenly spaced quantiles of a distribution. If you have to represent a distribution with one number, the median may be a reasonable choice. If $n=9$, then you can use the $10$th percentile, $20$th percentile, ... $90$th percentile.

If you want a random sample which better represents the distribution, you might want a systematic sample. For $n=10$, you could choose $x\in[0,10]$ uniformly, and then use the $x$ percentile, $x+10$th percentile, ... $x+90$th percentile.

If the population is divided into pieces (strata) with different characteristics, you may want to use stratified sampling particularly if you can adjust the number of points. This avoids samples which are not representative because there are too many or too few points from a stratum.

Answer 2

The literature on order statistics might suggest approximating $X$ with $\{E[X_{k:n}]:1\le k\le n\}$.
For your $X$ with $n=20$, this gives

{11.9, 15.1, 17.1, 18.6, 19.8, 20.9, 21.9, 22.8, 23.7, 24.6,
25.4, 26.3, 27.2, 28.1, 29.1, 30.2, 31.4, 32.9, 34.9, 38.1}

So in a sample of size 20 from $X$, 11.9 is the expectation for the smallest element, and 15.1 is the expectation for the second-smallest element. Then rounding gives

{12, 15, 17, 19, 20, 21, 22, 23, 24, 25, 25, 26, 27, 28, 29, 30, 31, 33, 35, 38}

Answer 3

It is possible to formulate a variant of this problem as a multiobjective integer linear program.

The idea is based on discrete approximations of probability distributions (see the paper of Eric A. DeVuyst and Paul V. Preckel for the multi-dimensional case). On p.788-789 they propose a linear program. We have to add an additional constraint:

$p_{i}\in \left \{ \frac{1}{n},\frac{2}{n}, ..., \frac{n-1}{n},\frac{n}{n} \right \}$

where

$n$ – number of integers.

It can be impossible to match the moments exactly. We have a multi-objective optimization problem. Our objective functions are to minimize deviations from the exact values of the moments. The solution of the program is a reference distribution. We generate the integer vector. If this vector is interpreted as a sample then its empirical distribution coincides with the reference distribution.
We can also add an objective function in the form of the Kullback–Leibler divergence (see the paper by Tanaka, K. I., & Toda, A. A).