# Generate random numbers that are sums of hidden variables

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

-
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