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
  • 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$ Sep 10, 2011 at 11:26
  • $\begingroup$ @DanaMoshkovitz: maybe this could be an answer ? $\endgroup$ Sep 10, 2011 at 20:28
  • 2
    $\begingroup$ Ok, I posted it as an answer. $\endgroup$ Sep 10, 2011 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, 2018 at 12:18

3 Answers 3

8
$\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$
1
  • 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$ Sep 11, 2011 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$
1
  • $\begingroup$ The link is broken, I guess the new one is: nrbook.com/devroye $\endgroup$
    – bonanza
    Feb 26, 2019 at 11:47
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 and acknowledge you have read our privacy policy.

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