Monte Carlo İntegrasyonunda Varyans Azaltıcı Yeni Bir Teknik

Year 2012, Volume: 9 Issue: 3, 1 - 16, 14.12.2012

Fatin Sezgin

Abstract

Monte Carlo tekniği, rasgele sayılar kullanarak yüzey alanlarını veya cisim hacimlerini bulmaya yarayan bir istatistik deney metodu olarak kullanılabilir. Karmaşık fonksiyonlarda veya düzgün olmayan şekillerde özellikle yüksek boyutlu uzaylar için yararlıdır. Monte Carlo tekniğine yeni bir yaklaşım sunan bu çalışmamızda mültinom dağılıştan hareketle nokta atışlarındaki İsabet-veya- İsabetsizlik integrasyonuna farklı bir bakış açısı getirilmekte ve Genelleştirilmiş Monte Carlo İntegrasyonu diye adlandırdığımız bir teknik tanıtılmaktadır. Burada, tek değişkenli integral işlemi yapılırken, üzerinde çalışılan alanın değişik eğrilerle ifade edilmesiyle elde edilecek farklı tahmin edicilerin ortalaması alınmakta ve böylece hesaplama hızı makul bir sınırda tutulurken, tahminin etkinliği arttırılmaktadır. Birim kare şeklindeki bir düzlemde kullanılan tek değişkenli fonksiyonlar yardımıyla bu yeni tekniğin uygulaması gösterilmiştir. Metod daha yüksek boyutlara da genelleştirilebilir. Öte yandan, fizik, kimya, tıp, genetik ve biyolojide, alanı veya hacmi hesaplanacak yüzey veya şekilleri ifade eden belli bir fonksiyonun bulunmadığı yaygın durumlar vardır. Bu durumlarda farklı fonksiyon ifadeleri yerine, yüzey veya cisim değişik yansımalara ve döndürmelere tabi tutulabilir. Teklif ettiğimiz yeni tekniği üstün kılan seçici özelliklerden birisi, bu tür problemlere uygulanabilmesidir. Metodun çok işlemcili bilgisayar ortamlarına uygulanabilmesi de üzerinde durulmaya değer bir husustur.

Keywords

Etkinlik, Ham Monte Carlo, İsabet-veya-isabetsizlik integrasyonu, Monte Carlo, Monte Carlo integrasyonu, Rastgele sayı üreticisi, Varyans azaltılması

A New Method of Variance Reduction in Monte Carlo Integration

Abstract

The Monte Carlo technique can be used as a method of statistical trials to calculate surface areas or object volumes by employing random numbers. It is especially helpful for complicated functions or irregular shapes in higher dimensional spaces. In this work, relying on a multinomial distribution, we give a fresh new look on Hit-or-Miss integration and present a technique called Ertended Monte Carlo lntegration (EMCI) by expressing the integral area of univariate functions in different forms. By taking the average of estimates from these forms it is possible to increase efficiency while maintaining a reasonable calculation speed. The application of this technique is demonstrated by using single-variable functions in the unit square. The method can be generalized to higher dimensions. There are very common cases in physics, chemistry, medicine, genetics and biology where there is no explicit function defining the region or the volume to be estimated. In these cases, instead of various function expressions, different rotations and reflections of the figure or object can be used. A distinct advantage of our method is its applicability to these problems. Investigating the suitability of the method to multi-core processors also seems promising.

Keywords

Crude Monte Corlo, Efficiency, Hit-or-Miss integration, Monte Carlo, Monte Carlo integration, Random number generator, Variance reduction

References

• De Koning, M., Cai. W.• Sadigh. B .• Oppelstrup, T., Kalos, M. H., Bulatov, V. V., 2005. Adaptive Importance Sampling Monte Carlo Simulation of Rare Transition Events. J. Chem. Phys. 122. Article 074103.
• Evans. M., Swartz. T., 1999. Approximating Integrals via Monte Carlo and Deterministic Methods. Oxford University Press. United Kingdom.
• Fishman. G. S., 1996. Monte Carlo Concepts. Algorithms, and Applications. Springer.
• Gentle. J. E.. 2005. Random Number Generation and Monte Carlo Method. Second Edition. Springer.
• Law. A. M., Kelton. W. D., 2000. Simulation Modeling and Analysis. Third Edition. McGraw-Hill.
• L’Ecuyer. P., 1994. Efficiency Improvement and Variance Reduction. in: Tew. J. D., Manivannan. S., Sadowski. D. A., and Seila. A. F. (eds) Proceedings of the 1994 Winter Simulation Conference, pp. 122-132.
• Lemieux, C., 2009, Monte Carlo and Quasi-Monte Carlo Sampling, Springer Science+Business Media.
• McGeoch, C.. 1992. Analyzing Algorithms by Simulation: Variance Reduction Techniques and Simulation Speedups. ACM Comput. Surveys, 24, 195-212.
• Naiman, D. Q., Priebe, C. E., 2001. Computing Scan Statistic p Values Using Importance Sampling, With Applications to Genetics and Medical Image Analysis, J. Comput. Graph. Statist., 2, 296-328.
• Priebe, C. E., Naiman. D. Q., Cope, L. M., 2001. Importance Sampling for Spatial Scan Analysis: Computing Scan Statistic P-values for Marked Point Processes, Comput. Statist. Data Anal. 35, 475-485.
• Romano, R., Paris, D. B., Acernese, F., Barone, F., Motta, A., 2008. Fractional Volume Integration in Two-dimensional NMR Spectra: CAKE, a Monte Carlo Approach. Joumal of Magnetic Resonance 192 294-301.
• Ross, S.M., 2006. Simulation. Fourth Edition. Elsevier Academic Press. pp. 129-195.
• Saftoiu, A., Ciurea, T., Gorunescu, F., Rogoveanu, Georgescu, I., 2004. Stochastic Modeling of the Tumor Volume Assessment and Growth Patterns in Hepatocellular Carcinoma. Bulletin du cancer 91, Issue 6, E162-166.
• Sezgin F., 2010. A new method of variance reduction in Monte Carlo Integration, MCQMC Conference, Warsaw, http://mcqmc.mimuw.edu.pl/Presentations/sezgin.pdf, and http://mcqmc.mimuw.edu.pl/materialy/mcqmc2010program.pdfp. 94.
• Takano, Y., Liou, K. N., 1995. Radiative Transfer in Cirrus Clouds. Part III: Light Scattering by Irregular Ice Crystals. (1994) J. Atmospheric Sci., 52 No. 7, 818--837.
• Vlasov, A. Y., You, X. M., Masters, A. J., 2002. Monte-Carlo Integration for Virial Coefficients Re-visited: Hard Convex Bodies, Spheres with a Square-well Potential and Mixtures of Hard Spheres, Molecular Phys., 100, No. 20, 3313- 3324.