Mengapa menggunakan metode Monte Carlo dan bukannya grid sederhana?

25

ketika mengintegrasikan fungsi atau dalam simulasi yang kompleks, saya telah melihat metode Monte Carlo banyak digunakan. Saya bertanya pada diri sendiri mengapa orang tidak menghasilkan kisi poin untuk mengintegrasikan fungsi alih-alih menggambar titik acak. Bukankah itu membawa hasil yang lebih tepat?

monte-carlo Alexander Engelhardt
sumber

Jawaban:

27

Saya menemukan bab 1 dan 2 dari catatan kuliah ini bermanfaat ketika saya mengajukan pertanyaan yang sama beberapa tahun yang lalu. Ringkasan singkat: Kotak dengan titik dalam ruang 20 dimensi akan menuntut evaluasi fungsi . Itu banyak. Dengan menggunakan simulasi Monte Carlo, kita menghindari kutukan dimensi hingga batas tertentu. Konvergensi dari simulasi Monte Carlo adalah yang, walaupun sangat lambat, berdimensi dimensional .N 20 O ( N - 1 / 2 )NN20O(N−1/2)

Har
sumber
2
+1 Balasan ini bersinar karena ia menawarkan alasan kuantitatif dalam dukungannya.
whuber
11

Tentu itu; namun ia hadir dengan penggunaan CPU yang jauh lebih besar. Masalahnya meningkat terutama di banyak dimensi, di mana grid menjadi tidak dapat digunakan secara efektif.


sumber
0

Sementara satu hal yang khas dari sampel penolakan ketika mempertimbangkan Monte Carlo, Rantai Markov Monte Carlo memungkinkan seseorang untuk mengeksplorasi ruang parameter multi-dimensi lebih efisien daripada dengan grid (atau sampel penolakan dalam hal ini). Bagaimana MCMC dapat digunakan untuk integrasi dinyatakan dengan jelas dalam tutorial ini- http://bioinformatics.med.utah.edu/~alun/teach/stats/week09.pdf

Sameer
sumber
-2

Dua hal -

  1. Konvergensi yang lebih cepat dengan menghindari kutukan dimensi. Karena sebagian besar poin dalam grid terletak pada bidang yang sama tanpa memberikan informasi tambahan yang signifikan. Poin acak mengisi ruang dimensi-N secara merata. LDS bahkan lebih baik.

  2. Kadang-kadang untuk metode Monte carlo kita membutuhkan poin acak secara statistik tanpa urutan tertentu. Urutan titik kisi yang dipesan akan menghasilkan properti statistik yang buruk.

r00kie
sumber
2
Bisakah Anda menjelaskan mengapa poin-poin yang terletak pada hyperplane yang sama tidak berkontribusi "informasi tambahan" tentang integral? Saya membayangkan situasi generik di mana domain dari fungsi bernilai real terukur pada adalah sampel dan integral dari f diperkirakan oleh rata-rata f pada sampel. Saya tidak dapat melihat alasan apa pun secara umum mengapa f seperti itu tidak dapat bervariasi secara substansial pada semua hyperplanes yang memotong domainnya. Mungkin Anda memikirkan simulasi Monte Carlo dalam arti yang berbeda? Rnfff
whuber