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

Improve this question
$\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$
    – Dana Moshkovitz
    Sep 10, 2011 at 11:26
  • $\begingroup$ @DanaMoshkovitz: maybe this could be an answer ? $\endgroup$
    – Suresh Venkat
    Sep 10, 2011 at 20:28
  • 2
    $\begingroup$ Ok, I posted it as an answer. $\endgroup$
    – Dana Moshkovitz
    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

Reset to default
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.

Improve this answer
$\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$
    – Mahdi Cheraghchi
    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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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