6
$\begingroup$

I am using some randomized algorithms (particle filters) and I would like to know what is the computational complexity of obtaining one random sample of a continuous distribution (for instance from a multivariate Gaussian), in terms of elemental operations... or what computational complexities have conventional algorithms.

Thank you

$\endgroup$
  • 4
    $\begingroup$ It depends on your computational model. Sometimes people just assume you can generate a Gaussian as a unit operation. However, if all you can generate is, say, random bits, and you want an approximate Gaussian, the complexity depends on the approximation you want. $\endgroup$ – Dana Moshkovitz Sep 10 '11 at 11:26
  • $\begingroup$ @DanaMoshkovitz: maybe this could be an answer ? $\endgroup$ – Suresh Venkat Sep 10 '11 at 20:28
  • 2
    $\begingroup$ Ok, I posted it as an answer. $\endgroup$ – Dana Moshkovitz Sep 10 '11 at 20:31
  • $\begingroup$ FYI In the case of a finite distribution (not what op asks!), $O(1)$ time is (in theory) possible. See cstheory.stackexchange.com/questions/37648/…. $\endgroup$ – Neal Young Aug 22 '18 at 12:18
7
$\begingroup$

The answer depends on your computational model. Sometimes people just assume you can generate a Gaussian as a unit operation. However, if all you can generate is, say, random bits, and you want an approximate Gaussian, the complexity depends on the approximation you want.

$\endgroup$
  • 3
    $\begingroup$ A more precise question would be, if you want to sample a distribution from random iid bits that is $\epsilon$-close to a Gaussian in total variational distance, what is the running time dependence of the sampler in $\epsilon$. $\endgroup$ – MCH Sep 11 '11 at 0:28
5
$\begingroup$

A related pointer (though not a complete answer) is the book by Luc Devroye on generating random draws from different kinds of distributions. While the book doesn't have detailed complexity analysis, it outlines a number of very specific algorithms for sampling from different densities, and provides good pointers to do a proper running time analysis.

$\endgroup$
2
$\begingroup$

Donald Knuth's The Art of Computer Programming has algorithms for generating many common distributions in volume two, chapter three.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.