Siapa yang pertama kali mengusulkan menggunakan algoritma Monte Carlo untuk menghitung Pi?

Saya yakin semua orang tahu percobaan jarum Buffon di abad ke-18, itu adalah salah satu algoritma probabilistik pertama yang menghitung . $\pi$

Implementasi algoritma di komputer biasanya membutuhkan penggunaan , atau fungsi trigonometrik, yang, bahkan jika mereka diimplementasikan sebagai seri terpotong, semacam mengalahkan tujuannya. $\pi$

Untuk menghindari masalah ini, ada algoritma metode penolakan yang terkenal: gambarkan koordinat dalam satuan kuadrat, dan lihat apakah mereka termasuk dalam satuan seperempat lingkaran. Ini terdiri dari menggambar dua real seragam dan di (0,1), dan menghitungnya hanya jika . Pada akhirnya, jumlah koordinat yang telah disimpan dibagi dengan jumlah total koordinat adalah perkiraan . $x$ $y$ $x^2+y^2 < 1$ $\pi$

Algoritme kedua ini biasanya dinyatakan sebagai jarum Buffon, menganggapnya sangat berbeda. Sayangnya, saya belum dapat melacak siapa yang membuatnya. Apakah ada yang punya informasi (didokumentasikan, atau paling tidak terdokumentasi) tentang siapa / kapan ide ini berasal?

ds.algorithms reference-request randomized-algorithms ho.history-overview monte-carlo Jérémie
sumber

Saya pikir ini tempat yang tepat.

Tyson Williams

@vzn: Terima kasih atas komentar Anda! Memang inilah yang saya yakini, khususnya yang dianggap sebagai eksperimen Von Neumann lainnya, khususnya yang dirangkum dalam "Berbagai Teknik yang Digunakan dalam Koneksi Dengan Digit Acak" ("kertas" favorit saya). Saya harap informasi ini tidak terklasifikasi ... meskipun Anda mungkin benar mengenai hal ini juga.

Jérémie

ngomong-ngomong ada algoritma yang terkait erat di mana seseorang hanya menggunakan semua poin pada kotak persegi unit yang sama-sama spasi, poin di satu sisi, di mana jarak unit dipilih "kecil" relatif terhadap jari-jari lingkaran. juga, secara sah, pasti ada kutipan "pertama" di suatu tempat dalam literatur, tetapi saya tidak dapat menemukannya sejauh ini. ada buku bagus "sejarah Pi" oleh peter beckman, beberapa di antaranya online, dan saya tidak melihatnya dikreditkan di bagian online [buku google]. bertanya-tanya apakah itu di bagian offline? ini juga salah satu contoh favorit saya masalah monte carlo.

n^{2}

$n^2$

n

$n$

vzn

Nit minor: harus dalam "jumlah koordinat yang telah disimpan dibagi dengan jumlah total koordinat adalah perkiraan dari ."

π

$\pi$

π / 4

$\pi/4$

π

$\pi$

Huck Bennett

Untuk yang benar-benar unik, ambil dua angka seragam acak antara 0 dan 1 lalu ambil hasil bagi mereka. Perkirakan probabilitas itu lebih dekat ke angka genap daripada angka ganjil. Ini harus

\frac{π - 1}{4}

$\frac{\pi - 1}{4}$

dspyz

Siapa yang pertama kali mengusulkan menggunakan algoritma Monte Carlo untuk menghitung Pi?

Jawaban: