2
$\begingroup$

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

  • 0
    Suggestions that have $O(n)$ preprocessing and then low generation time for each random vector are also welcome.2012-04-24

0 Answers 0