<p>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. </p>

CC BY-SA 3.0
2011-09-11T00:28:44.903Z
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
CC BY-SA 3.0
2011-09-10T20:31:02.267Z
2011-09-10T20:31:02.267Z
Dana Moshkovitz
<p>A related pointer (though not a complete answer) is <a href="http://cg.scs.carleton.ca/~luc/rnbookindex.html" rel="noreferrer">the book by Luc Devroye</a> 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. </p>

CC BY-SA 4.0
2019-02-26T11:47:57.593Z
The link is broken, I guess the new one is: http://www.nrbook.com/devroye/
bonanza
CC BY-SA 3.0
2011-09-11T03:22:45.957Z
2011-09-11T03:22:45.957Z
Suresh Venkat
<p>Donald Knuth's <a href="http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming#Chapters" rel="nofollow">The Art of Computer Programming</a> has algorithms for generating many common distributions in volume two, chapter three.</p>

CC BY-SA 3.0
2011-09-12T17:41:33.060Z
2011-09-12T17:41:33.060Z
Raphael
<p>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.</p>

<p>Thank you</p>

CC BY-SA 3.0
2011-09-10T11:26:29.813Z
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
CC BY-SA 3.0
2011-09-10T20:28:26.023Z
@DanaMoshkovitz: maybe this could be an answer ?
Suresh Venkat
CC BY-SA 3.0
2011-09-10T20:31:43.153Z
Ok, I posted it as an answer.
Dana Moshkovitz
CC BY-SA 4.0
2018-08-22T12:18:12.753Z
FYI In the case of a finite distribution (not what op asks!), $O(1)$ time is (in theory) possible.  See https://cstheory.stackexchange.com/questions/37648/random-sampling-data-structure-with-removal.
Neal Young
<cc.complexity-theory><counting-complexity><randomness><pr.probability>
Computational complexity of random sampling
Santiago
# Computational complexity of random sampling

(Asked by: username_0 on 2011-09-10)

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

**Tags:** cc.complexity-theory, counting-complexity, randomness, pr.probability
> **Comments:**
> **username_1**: 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.  
> **username_2**: @DanaMoshkovitz: maybe this could be an answer ?  
> **username_1**: Ok, I posted it as an answer.  
> **username_3**: FYI In the case of a finite distribution (not what op asks!), $O(1)$ time is (in theory) possible.  See https://cstheory.stackexchange.com/questions/37648/random-sampling-data-structure-with-removal.  

---

## 3 answers

### Answer by username_1 on 2011-09-10. Score: 8

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.

> **Comments:**
> **username_4**: 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$.  

---

### Answer by username_2 on 2011-09-11. Score: 5

A related pointer (though not a complete answer) is [the book by Luc Devroye](http://cg.scs.carleton.ca/~luc/rnbookindex.html) 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.

> **Comments:**
> **username_5**: The link is broken, I guess the new one is: http://www.nrbook.com/devroye/  

---

### Answer by username_6 on 2011-09-12. Score: 2

Donald Knuth's [The Art of Computer Programming](http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming#Chapters) has algorithms for generating many common distributions in volume two, chapter three.


---

