Approximate discrete probability distribution

Question

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

Answer 1

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.

Answer 2

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.