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