Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$A$ is a $M$x$N$ matrix whose entries are positive. $x$ is a $N$ dimensional binary (i.e. consisting of $0$s and $1$s) vector and the number of $1$s in $x$ is constant. Let $y = Ax$. The distribution of $x$ is given by

$$p(x) \propto \prod_{i=1}^M y_i$$

where $y_i$ is the $i^{\rm th}$ element of $y$.

How can one fairly and efficiently sample from this distribution?

I'm planning to do Gibbs sampling but its computational complexity is high (drawing a random $x$ is $\mathcal{O}(MN)$). I'm looking for a more efficient sampling method or tricks to make Gibbs faster.

share|cite|improve this question
Please let me ask you. You have $M$ dimensional $y$ and you are interested in the multivariate density of first $N$ multiplications, $A$ is a deterministic matrix and $x$ is a random vector. Are my observations correct? thanks. – Seyhmus Güngören Sep 16 '12 at 10:36
Thanks for your comment, I noticed and corrected an error. The product should be from 1 to M. – emrea Sep 17 '12 at 1:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.