# Approximate discrete probability distribution

I have a discrete probability distribution with can take a large number of discrete values, say $$x \in \{1,\ldots,N\}$$. I know $$p(x)$$ for all these $$x$$. Typically, quite many of the values have a small probability $$p(x)$$, and are therefore not very relevant when I want to do further operations with this distribution (like computing the means for functions of $$x$$, but also other inferential operations). What I want to do is to approximate the distribution $$p_0(x)$$ by a distribution taking only $$N_0 \ll N$$ number of discrete values, which I can then use to get approximations to the various operations.

I have a few options:

1) Sampling with replacement from $$p(x)$$ until I get $$N_0$$ unique numbers, and then creating $$p_0(x)$$ based on the sampled frequencies of the unique $$x$$.

2) Just use $$x$$ with the $$N_0$$ largest probabilities, and set $$p_0(x)$$ proportional to $$p(x)$$ for those values.

I am pretty sure 1) would lead to unbiased estimates of say means etc., but it just feels very inefficient to throw away the original $$p(x)$$.

Method 2) feels much more efficient when computing say a mean, but I guess it being deterministic may lead to biased estimates.

Any thoughts about what would be the best approximation $$p_0(x)$$ to $$p(x)$$, taking only $$N_0$$ distinct values?

Any pointers to methods or literature to look into is also highly appreciated.

Edit:

I will just add some additional information to my problem, which may or may not help you answer my question.

Let $$S = \{1,\ldots,N\}$$ and $$S_0 \subset S$$ be the subset of the approximate distribution taking $$|S_0|=N_0$$ unique values.

Although it is not the only thing I want to do, we can assume that for some function $$h$$, which is very expensive to evaluate, I want to estimate $$E[h(X)] = \sum_{j=1}^N h(x=j)p(x=j)$$ by $$\sum_{j \in S_0} h(x=j)p_0(x=j)$$ for some $$S_0$$ and $$p_0$$.

Further, $$N=2^K$$, where $$K$$ is the number of distinct probabilities that $$p(x)$$ takes. You may think of this as $$K$$ different groups of different sizes. The large groups have relatively small probabilities compared to the small groups. Note however, that the values $$h(x)$$ may in theory be very different within each group. Thus, just evaluating $$h(x)$$ for a single $$x$$ within each group, say, and using that value for all $$x$$ within that group, is probably not a good idea.

Without knowledge about $$h$$, I am thinking that I need an approximate distribution which "covers" as much of the original distribution as possible, that is an $$S_0$$ where $$\sum_{x \in S_0} p(x)$$ is as large as possible, and still being (close to) unbiased. I might be looking at this the wrong way though...

• In both cases you seem to be assuming that the values that didn't appear via sampling on among largest $N_0$ (both approaches are in fact equivalent) have $p_0(x)=0$..? This does not seem to be a reasonable assumption... – Tim Mar 13 at 10:45
• Is it necessary that the new set of $N_0$ distinct values be a subset of the old values or can they be from a set of values I choose? – Glen_b Mar 13 at 11:48
• @Tim: I agree that this is an assumption in both cases. While it may not be a perfect assumption, it is, as far as I can tell, the only way to reduce the number of distinct values. Agree? – Mark Mar 13 at 12:12
• @Glen_b: I guess that could form a subset of value of your choosing. However, the main reason I want to do this is that it is expensive to perform any evaluation involving $x$. I am therefore not sure how grouping values would help... I will update the question to make my intentions clearer. – Mark Mar 13 at 12:16

As I understand it, you have set of possible values $$x \in S$$ of size $$|S| =N$$. Because of some computational issues, you want to make $$N$$ much smaller by somehow "ignoring" the values of $$x$$ that come with small probability $$p(x)$$.

The simple solution that comes to my mind, is to select subset $$S_0$$ of the $$N_0$$ values that come with largest probabilities, and for all the other values assume same probability, that is equal to the average their probabilities. Now your distribution $$p_0$$ is defined in terms of $$N_0+1$$ unique probabilities:

$$p_0(x) = \begin{cases} p(x) &\text{if}& x \in S_0 \\ c &\text{if}& x \in S -S_0 \end{cases}$$

where $$c=\frac{\sum_{x'\in S -S_0} p(x')}{N-N_0}$$ is a constant. This makes $$p_0$$ exact for the most probable values, and approximate otherwise.

• Thank you. It is good idea, but I wonder how I could compute say $E[h(x)]$ under this approximation? – Mark Mar 14 at 14:17
• @Mark same as with $p(x)$, you take $E[h(x)] = \sum_x p_0(x) h(x)$. – Tim Mar 14 at 14:50
• This requires evaluation of $h$ at every $x$, which it pointless to do the approximation in the first place (see the edited question)... Right? – Mark Mar 18 at 11:42
• @Mark I missed the edit. Given the edit, it seems that your question is not at all about approximating the distribution, but rather about calculating expected value, isn't it? – Tim Mar 18 at 12:08
• No, I want to do different inferential things with the distribution. Computing the expected value is just one such thing, which I though would make the question a bit more concrete. – Mark Mar 18 at 13:37

You could just collapse the probability of groups of adjacent values of $$x$$ to single points.

If you let $$N_0 = \lceil N/k\rceil$$ for some $$k \geq 2$$, then you can have $$p(y_i) = \sum\limits_{j=i\cdot k + 1}^{j_{max}} p(x_j)$$ for $$i \in \{0, \dots, N_0-1\}$$, where $$j_{max} = \min(N,\,(i+1)\cdot k))$$.

It's fast and doesn't throw away any probability.

• This is bad if high probable points are close to each other. – gunes Mar 13 at 11:15
• @gunes it depends on what exactly does OP expect and how does his data look like. – Tim Mar 13 at 12:06
• Thanks for the suggestion. Taking the computation of say $E[h(x)]$ as a example, this approach seems to assume that $h(x=j)$ and $h(x=j+1)$ are similar, which they might not be. And what value should I use for $y_i$ when evaluating a function? Note also that I updated the question with some more information. Using this approach on the $K$ groups would make sense, but again the $h(x)$ may not be similar and I don't know how to choose a representative $x$ for that group when evaluating $h$. – Mark Mar 13 at 12:48