Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

I have $Y = A X$ where:

  1. $Y$ is an $m$ vector of random variables
  2. $X$ is an $n$ vector of random variables, uniformly distributed in $[0, 1]$
  3. $m \ll n$, ($n$ ~ $m!$)
  4. $A$ is an $m \times n$ $0/1$ matrix, this matrix is not sparse, each row contains exactly as many zeroes as ones (n is even).

I would like to generate random vectors $y$ from the distribution of $Y$. Is there a more efficient way than generating random $x$ and computing $y$? Is there any algorithm that is sub-linear in $n$? It may depend on $m$ in any way (of course it would have to be $o(m!)$).

share|cite|improve this question
Suggestions that have $O(n)$ preprocessing and then low generation time for each random vector are also welcome. – aelguindy Apr 24 '12 at 11:16

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.