Hacker News new | past | comments | ask | show | jobs | submit login

For a known fixed value of n, you can get amazing convergence rates. For example, the basic midpoint rule gives O(1/n^2) and Simpson's rule gives O(1/n^4).

Despite this, there are two major use cases for quasirandom sequences: The first is when n is not known upfront and so you can't create a lattice; and the second is in higher dimensions. The reason for this latter situation is because the number of points required to make a lattice in D dimensions scales exponentially in D, whereas the convergence rates for random or quasirandom sampling are (amazingly!) independent on the dimension.

I think that you would really like Owen's paper on this topic. It is very comprehensive and yet extremely readable [1]

1[ ]http://statweb.stanford.edu/~owen/mc/Ch-quadrature.pdf




Yes, with a fixed n you can essentially do what some fields call DOE [1]. If your sampling process is open-ended things are different.

[1] https://en.wikipedia.org/wiki/Design_of_experiments


I certainly agree re:high dimensions. This is because to integrate, you don't need to approximate the function everywhere.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: