Coin Tossing Algorithms for Integral Equations and Tractability

Novak Erich and Pfeiffer Harald

Monte Carlo Methods and Applications, 2004, vol. 10, issue 3-4, 491-498

Abstract: Integral equations with Lipschitz kernels and right-hand sides are intractable for deterministic methods, the complexity increases exponentially in the dimension d. This is true even if we only want to compute a single function value of the solution. For this latter problem we study coin tossing algorithms (or restricted Monte Carlo methods), where only random bits are allowed. We construct a restricted Monte Carlo method with error ε that uses roughly ε−2 function values and only d log2 ε random bits. The number of arithmetic operations is of the order ε−2 + d log2 ε. Hence, the cost of our algorithm increases only mildly with the dimension d, we obtain the upper bound C · (ε−2 + d log2 ε) for the complexity. In particular, the problem is tractable for coin tossing algorithms.

Date: 2004
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/mcma.2004.10.3-4.491 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

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:bpj:mcmeap:v:10:y:2004:i:3-4:p:491-498:n:31

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/mcma.2004.10.3-4.491

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().