Summary

Proceedings of the 2013 International Symposium on Nonlinear Theory and its Applications

2013

Session Number:B1L-C

Session:

Number:213

Super-efficiency and Approximate Super-efficiency in Monte Carlo Simulation Methodology

Cheng-An Yang,  Kung Yao,  Ken Umeno,  Ezio Biglieri,  

pp.213-216

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.2.213

PDF download (450.1KB)

Summary:
Monte Carlo (MC) simulation methods are widely used to solve complex engineering and scientific problems. Unlike other deterministic methods, MC produce solution with uncertainty through statistical sampling. As the sample size N growths, the uncertainty of the solution reduces. It is well-know that the variance of the error decreases as 1/N. However, for large problems like high-dimensional integrations and computationally intensive simulations this can take months or even years to obtain the solution with acceptable tolerance. The Super-efficient Monte Carlo simulation method, originated by Umeno, produced a solution that converges as fast as 1/N2. However it only applies to a small class of problems that possess certain properties. We proposed an Approximate Super-efficient Monte Carlo simulation method that is applicable to a wider class of problems than the original Umeno method, where the convergence rate is as fast as 1/Nα for 1 ≤ α ≤ 2.

References:

[1] R. Y. Rubinstein, Simulation and the Monte Carlo method. Wiley series in Probability and Mathematical Statistics, Wiley, 1981.

[2] K. Umeno, “Chaotic Monte Carlo Computation: A Dynamical Effect of Random-Number Generations,” Japanese Journal of Applied Physics, vol. 39, pp. 1442-1456, Mar. 2000.

[3] V. I. Arnol'd, Ergodic problems of classical mechanics, vol. 50. New York: Benjamin, 1968.

[4] K. Yao, “An Approximate Superefficient MC Method is Better Than Classical MC Method.” Unpublished Report, 2009.

[5] E. Biglieri, “Some notes on ”superefficient” Monte Carlo methods.” Unpublished Report, 2009.

[6] K. Umeno, Japanese Patent No. 3711270 (submitted on March 30, 2002, and granted on August 19, 2005), recorded in Japanese.