Non User
Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	Business Non User Industries Finance Tax

Home > Quasi-Monte Carlo method

a quasi-Monte Carlo method is a method for the computation of an integral (or some other problem) which is based on low-discrepancy sequences. This is in contrast to a Monte Carlo method, which is based on sequences of pseudorandom numbers.

Monte Carlo and quasi-Monte Carlo methods are stated in a similar way. The problem is to approximate the integral of a function f as the average of the function evaluated at a set of points x₁, ..., x_N.

In a Monte Carlo method, the set x₁, ..., x_N is chosen as a subsequence of pseudorandom numbers. In a quasi-Monte Carlo method, the set is a subsequence of a low-discrepancy sequence.

The approximation error of a method of the above type is bounded by a term proportional to the discrepancy of the set x₁, ..., x_N, by the Koksma-Hlawka inequality. The discrepancy of sequences typically used for the quasi-Monte Carlo method is bounded by a constant times

In comparison, with probability one, the expected discrepancy of a uniform random sequence (as used in the Monte Carlo method) has an order of convergence

by the law of the iterated logarithm.

Thus it would appear that the accuracy of the quasi-Monte Carlo method increases faster than that of the Monte Carlo method. However, Morokoff and Caflisch cite examples of problems in which the advantage of the quasi-Monte Carlo is less than expected theoretically. Still, in the examples studied by Morokoff and Caflisch, the quasi-Monte Carlo method did yield a more accurate result than the Monte Carlo method with the same number of points.

Morokoff and Caflisch remark that the advantage of the quasi-Monte Carlo method is greater if the integrand is smooth, and the number of dimensions of the integral is small.

References

• Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math., 1651, Springer, Berlin, 1997, BooksEnthsiast.com
• Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. BooksEnthsiast.com
• Harald G. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957--1041
• William J. Morokoff and Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), no. 6, 1251--1279 (At CiteSeer:[1])
• William J. Morokoff and Russel E. Caflisch, Quasi-Monte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218--230. (At CiteSeer: [2])

Politics	Business	Finance

Topics: Quasi-Monte Carlo Method Quasi-monte Monte Sequences Caflisch...

---

QuasigroupIn abstract algebra, a quasigroup is a algebraic structure resembling a group in the sense that " division" is always possible. Quasigroups differ from groups mainly in that they need not be associative. Definitions Formally, a quasigroup is a magma Q ), Quasi-autonomous non-governmental organisationThe term Quasi-Autonomous Non-Governmental Organisation (or QUANGO , attributed to Sir Douglas Hague, was originally invented as a joke, but fell into common usage in the United Kingdom to describe the agencies produced by the growing trend of government Quasispecies modelThe quasispecies [kwaa'-zei-spee"-seez] model is a description of the process of the Darwinian evolution of self-replicating entities within the framework of physical chemistry. It is useful mainly in providing a qualitative understanding of the evolution Quasi-WarThe Quasi-War was an undeclared war fought entirely at sea between the United States and France from 1798 to 1801. The pirates of the Mediterranean Sea caused the United States Congress in 1794 to begin building a navy for the protection of commerce. QuasicrystalQuasicrystals are a peculiar form of solid in which the atoms of the solid are arranged in a seemingly regular, yet non-repeating structure. They were first observed by Dan Shechtman in 1982. Patterns in quasicrystals In a normal crystalline solid the pos Quasi-analog signalIn telecommunication, a quasi-analog signal is a digital signal that has been converted to a form suitable for transmission over a specified analog channel. Note: The specification of the analog channel should include frequency range, bandwidth, signal-to Quasi-empiricism in mathematics Quasi-empiricism Quasi-empirical methods Quasi-biennial oscillation Quasi-delict Quasi-contract Quasiperfect number Quasimodo Quasi-Monte Carlo method