# How to sample from a product-of-sums distribution?

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

-
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