5
$\begingroup$

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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What you describe is a method to approach that problem, I believe it is a bit more complex with the integrality constraints on the chosen numbers (the percentiles may contain no integers, or several). I suggested a solution on the linked Mathematica forum, but I am looking for references on the problem itself (which I assume may refer to solution methods). $\endgroup$
    – A.G.
    Commented Jan 7, 2014 at 7:40
  • $\begingroup$ @A. G.: I thought you had a reference request for the terms statisticians use for representing a distribution by a set of representative samples which are not in general constrained to be integers. If you are looking for a way that you can choose a multiset of $1000$ integers to represent a distribution as simple as $N(1.3,0.001)$ then I don't think you can do it. You can't even simultaneously approximate the mean and the standard deviation well using only integer values, much less approximate the distribution. $\endgroup$
    – Douglas Zare
    Commented Jan 7, 2014 at 7:54
  • $\begingroup$ Yes, quite clearly it would make little practical sense to approximate a normal distribution such as that which you mention. There are however cases where an integer multiset approximation would be pertinent. I guess some measure or inspection of the solution is always in order. I understand though that my question could have been clearer, I will see what I can do. Best. --A.G. $\endgroup$
    – A.G.
    Commented Jan 8, 2014 at 22:39
2
$\begingroup$

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}

Improve this answer
$\endgroup$
1
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! My first attempts on the linked thread was indeed an integer program with a sum-of-squares-type objective. Mathematica had a very hard time with even for $n=5$, but then again I did not attempt any tweaking. $\endgroup$
    – A.G.
    Commented Jan 8, 2014 at 22:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .