How to sample a from p-variate discrete distribution when p is high Suppose I have a $p$-dimensional random vector $X$, with probability mass function
$f(x) = P(X = x)$, $x \in \mathbb \{0,1\}^p$. Each of the $p$ variables is binary. If I want to sample from the distribution described by $f$, I can calculate the probability of each of the possible $2^p$ outcomes, divide the the $[0,1]$ interval in $2^p$ sub-intervals so that the $i$-th sub-interval has length equal to $P(X = i\text{-th possible outcome})$, sample a pseudonumber $u$ from a uniform distribution on $[0,1]$ and then select $X = i\text{-th possible outcome}$ if $u \in $ the $i$-th sub-interval.
The problem is that this method requires a $2^p$-dimensional vector containing the probabilities of all outcomes, and it does not fit in memory if $p$ is too big (and for my problem I need something like $p$ > 150).
Is there a more efficient way to do this sampling?
Thank you very much
 A: If I understand correctly, you are describing a joint distribution over p binary variables.
If you can't store the distribution anywhere (BTW you could store on disk instead of RAM, but that still might not be enough), then obviously you cannot do any calculations on it because you can't even specify what the distribution is.
So you really need to simplify the distribution somehow. One way is to use probabilistic graphical models, which were developed exactly for this type of problem. They can model very complicated probability distributions by taking advantage of conditional dependencies. Given data and/or prior knowledge about the distribution, you can estimate the dependencies.
Beyond that, if you are dealing with learning from data, there are many things you can do to simplify, from Principal Component Analysis (PCA) to various advanced machine learning techniques. PCA for example may allow you to find if your data can be accurately described by fewer variables (in a lower dimension).
