1
$\begingroup$

I want to sample from a discrete distribution with probability vector $p \in \mathbb R^n$, where $n$ is large.

Suppose that $p_i = f_i / Z$, where $Z$ is a normalization constant. I can compute the elements $f_i$ easily, but instantiating the full vector of the $f_i$ (or the $p_i$) is expensive in terms of computer memory.

Is there an algorithm to sample from $p$ without instantiating the full probability vector? Suppose you are able to make several passes over the $f_i$.

$\endgroup$
  • $\begingroup$ Is anything known about the $p$'s (even bounds may be useful)? For example, is it unimodal? (and if so, do we know the mode?) Can we identify the most probable $i$ values? $\endgroup$ – Glen_b -Reinstate Monica Oct 8 at 11:06
  • $\begingroup$ @Glen_b No. But I don't mind traversing the values of $p_i$ several times. I just want to avoid allocating the full array of values in memory. $\endgroup$ – becko Oct 8 at 11:53
  • $\begingroup$ The most general case is hard and any additional information may lead to huge speedups. On that most general case, would something of the order of $\sqrt{n}$ random variable values and their probabilities be small enough to fit easily in memory? $\endgroup$ – Glen_b -Reinstate Monica Oct 9 at 0:23
  • $\begingroup$ Oh, and is there a lot of variation in size of $p_i$ values (say at least a couple of orders of magnitude between a large $p$ and a small $p$), or is there not much variation? (less than say an order of magnitude) $\endgroup$ – Glen_b -Reinstate Monica Oct 9 at 0:50
  • $\begingroup$ Is your access to the full list of elements sequential (like on tape) or is 'random access' possible? (in the computing sense, not the statistical sense, like on disk) $\endgroup$ – Glen_b -Reinstate Monica Oct 9 at 1:15
1
$\begingroup$

Yes. In general this is called reservoir sampling. For this particular question, there is a detailed explanation of how to implement an "online sampler":

http://timvieira.github.io/blog/post/2014/08/01/gumbel-max-trick-and-weighted-reservoir-sampling/

$\endgroup$

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.