# Computational complexity of random sampling

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

• 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. – Dana Moshkovitz Sep 10 '11 at 11:26
• @DanaMoshkovitz: maybe this could be an answer ? – Suresh Venkat Sep 10 '11 at 20:28
• Ok, I posted it as an answer. – Dana Moshkovitz Sep 10 '11 at 20:31
• 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/…. – Neal Young Aug 22 '18 at 12:18

• 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$. – Mahdi Cheraghchi Sep 11 '11 at 0:28