# Categorical sampling without instantiating probability vector

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

• 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? – Glen_b Oct 8 '19 at 11:06
• @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. – becko Oct 8 '19 at 11:53
• 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? – Glen_b Oct 9 '19 at 0:23
• 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) – Glen_b Oct 9 '19 at 0:50
• 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) – Glen_b Oct 9 '19 at 1:15