Take the 2-minute tour ×
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.

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

 
discard

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

Browse other questions tagged or ask your own question.