1
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ This probably isn't the best answer, but you could try using a Generative Adversarial Network (GAN). $\endgroup$
    – JacKeown
    Commented Jul 31, 2018 at 15:54
  • $\begingroup$ I assume the $p$ variables are not independent? $\endgroup$
    – A. Donda
    Commented Jul 31, 2018 at 17:42
  • $\begingroup$ No, there are no hypotesis on the dependecy relationships between the variables $\endgroup$
    – Möbius
    Commented Jul 31, 2018 at 18:45
  • $\begingroup$ Can you factor the probability mass function of your length 150 vector into a product of 150 conditional probability mass functions? If you can, then you can construct a sequence by sampling cell by cell. For instance, if the sequence satisfies the Markov property. $\endgroup$
    – Kevin Li
    Commented Jul 31, 2018 at 18:55
  • $\begingroup$ Also, I just want to point out that if your $ x $'s are binary, then it's not true that $ x \in \mathbb{R}^p $, but rather $ x \in \{ 0, 1 \}^p $. As a result of this, you can map these vectors into $ \mathbb{Z} $, and maybe you can get an interesting approximation of your distribution expressed as integers from 0 to $ 2^{151}-1 $? $\endgroup$
    – Kevin Li
    Commented Jul 31, 2018 at 20:14

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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