How Many Random Bits Do We Need for Monte Carlo Integration?

Stefan Heinrich (), Erich Novak () and Harald Pfeiffer ()
Additional contact information
Stefan Heinrich: FB Informatik, Universität Kaiserslautern
Erich Novak: Mathematisches Institut, Universität Jena
Harald Pfeiffer: Mathematisches Institut, Universität Jena

A chapter in Monte Carlo and Quasi-Monte Carlo Methods 2002, 2004, pp 27-49 from Springer

Abstract: Summary We study Monte Carlo methods (randomized algorithms) that use only a small number of random bits instead of more general random numbers for the computation of sums and integrals. To approximate N -1 ∑ i=0 N-1 f i for f ∈ R N ,the classical Monte Carlo method uses n function values, that is, coordinates of f, and n random numbers. Our method gives the same error with only 2[log2 N] random bits, independently of n. To approximate ∫[0, 1] d f (x) dx for f from a Sobolev space, the classical Monte Carlo method uses n function values and d.n random numbers. We present a method with the optimal order of convergence that uses only at most (2 + d) log2 n random bits.

Date: 2004
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-18743-8_2

Ordering information: This item can be ordered from
http://www.springer.com/9783642187438

DOI: 10.1007/978-3-642-18743-8_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().