# 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 21, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9336127042770386, "perplexity_flag": "head"}