# What would be an efficient way of representing a known discrete distribution with a number of samples?

So, say that I have a known discrete probability distribution, for example:

  [1]    [2]    [3]    [4]    [5]
0.08072 0.0642 0.2853 0.3206 0.2492


What I want to do is to represent this distribution as well as possible using a sample of size $n$ (say 10). For the particular distribution above a decent sample of size 10 would be:

1, 2, 3, 3, 3, 4, 4, 4, 5, 5


That is, each value is represented roughly proportional to its probability. My question is:

What would be a good method for going from a know discrete probability distribution to a representative sample of a given size?

Here I'm wondering both about what would be a good measure of representativeness (my guess would be the Kullback-leibler divergence between the original prob. distribution and the new prob. dist. the sample represents), and what could be an efficient way of calculating what the representative sample should be.

Two ways that, sort of, works but that I consider "sub-optimal" are:

(1) You could draw a random sample according to the known probability distribution. If $n$ is large then the resulting sample would probably be a good representation of the known probability distribution, but at small $n$ I will often be pretty bad. Here is, for example, a random draw from the known probability distribution above (which didn't turn out so well):

2 3 3 3 4 4 5 5 5 5


(2) You can multiply the known probability values by $n$, round them off, and then use this as your sample. For example, for the known probability distribution above multiplying by 10 would give

 [1]    [2]   [3]   [4]   [5]
0.8072 0.642 2.853 3.206 2.492


and after rounding you get:

[1]  [2]  [3]  [4]  [5]
1    1    3    3    2


which you can turn into the sample:

1, 2, 3, 3, 3, 4, 4, 4, 5, 5


But this method only works well in the special case when you have a much larger $n$ than the number of outcomes in the probability distribution. If you have a probability distribution with a large number of outcomes, each with a small probability, then all might round off to zero.

• Using a random sample introduces extra noise. Using a sample of size $n$ such the frequency of $i$, $n_i$, is optimised towards approaching the $p_i$'s for instance by maximising $$\sum_i p_i\,\log n_i$$ is a possibility. However, you should start with a loss function, i.e., a game-theoretic characterisation of why you are interested in this approximation. From there, you can derive your optimal solution, rather than the reverse. – Xi'an Mar 27 '15 at 10:45
• Your last sentence seems to suggest that you want at least one point in each bin regardless of how small the probability for the bin is ? Does this mean that you assume $n >$ number of outcomes ? – wij Mar 27 '15 at 10:52
• @WIJ No, not necessary. I just want to have $n$ samples if I asked for that. For example, representing the prob. dist. 1: 0.33 , 2: 0.33 , 3: 0.33 by 2 samples will give me 3 samples if I use method no. 2. – Rasmus Bååth Mar 27 '15 at 10:57
• @Xi'an Hmm, my use of this would be as an alternative to sampling at random from the known distribution (but without specific information regarding what the sample will be used for). A quirk with using $\log(n_i)$ is that counts of zero will be "impossible". But perhaps that is a good thing. – Rasmus Bååth Mar 27 '15 at 12:22
• I did not think of small samples, but you can instead use a Laplace normalisation $\sum_i p_i\,\log \{1+n_i\}$. Have you thought further about the purpose of this exercise and hence the choice of a proper loss function? – Xi'an Mar 27 '15 at 15:48