0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Tim Mar 13 at 10:45
  • $\begingroup$ 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? $\endgroup$ – Glen_b Mar 13 at 11:48
  • $\begingroup$ @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? $\endgroup$ – Mark Mar 13 at 12:12
  • $\begingroup$ @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. $\endgroup$ – Mark Mar 13 at 12:16
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. It is good idea, but I wonder how I could compute say $E[h(x)]$ under this approximation? $\endgroup$ – Mark Mar 14 at 14:17
  • $\begingroup$ @Mark same as with $p(x)$, you take $E[h(x)] = \sum_x p_0(x) h(x)$. $\endgroup$ – Tim Mar 14 at 14:50
  • $\begingroup$ This requires evaluation of $h$ at every $x$, which it pointless to do the approximation in the first place (see the edited question)... Right? $\endgroup$ – Mark Mar 18 at 11:42
  • $\begingroup$ @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? $\endgroup$ – Tim Mar 18 at 12:08
  • $\begingroup$ 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. $\endgroup$ – Mark Mar 18 at 13:37
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is bad if high probable points are close to each other. $\endgroup$ – gunes Mar 13 at 11:15
  • $\begingroup$ @gunes it depends on what exactly does OP expect and how does his data look like. $\endgroup$ – Tim Mar 13 at 12:06
  • $\begingroup$ 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$. $\endgroup$ – Mark Mar 13 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.