Bagaimana seharusnya seseorang menyetujui masalah Project Euler 213 ("Flea Circus")?

Saya ingin menyelesaikan Project Euler 213 tetapi tidak tahu harus mulai dari mana karena saya orang awam di bidang Statistik, perhatikan bahwa jawaban yang akurat diperlukan agar metode Monte Carlo tidak akan berfungsi. Bisakah Anda merekomendasikan beberapa topik statistik untuk saya baca? Tolong jangan posting solusinya di sini.

Kutu Sirkus

Kisi kotak 30 × 30 berisi 900 kutu, awalnya satu kutu per kotak. Ketika bel berbunyi, setiap kutu melompat ke kotak yang berdekatan secara acak (biasanya 4 kemungkinan, kecuali untuk kutu di tepi kisi atau di sudut).

Berapakah jumlah kotak kosong yang diharapkan setelah 50 dering bel? Berikan jawaban Anda dibulatkan ke enam tempat desimal.

Kamu benar; Monte Carlo tidak praktis. (Dalam simulasi naif - yaitu, yang persis mereproduksi situasi masalah tanpa penyederhanaan apapun - setiap iterasi akan melibatkan 900 gerakan kutu. Perkiraan kasar proporsi sel kosong adalah , menyiratkan varian dari Monte Perkiraan -Carlo setelah iterasi tersebut kira-kira Untuk menjabarkan jawaban ke enam tempat desimal, Anda harus memperkirakannya dalam 5.E. -7 dan, untuk mencapai kepercayaan 95 +% (katakanlah), Anda harus membagi dua presisi itu menjadi 2,5E-7. Memecahkan memberiN 1 / N 1 / e ( 1 - 1 / e ) = 0,2325 … / N $1/e$$N$$1/N 1/e (1 - 1/e) = 0.2325\ldots /N$N>4E$\sqrt(0.2325/N) \lt 2.5E-7$$N > 4E12$kira-kira. Itu akan menjadi sekitar 3,6E15 gerakan kutu, masing-masing mengambil beberapa kutu CPU. Dengan satu CPU modern yang tersedia, Anda akan membutuhkan komputasi (sangat efisien) setahun penuh. Dan saya agak salah dan terlalu optimis mengasumsikan jawaban diberikan sebagai proporsi alih-alih hitungan: sebagai penghitungan, itu akan membutuhkan tiga angka yang lebih signifikan, yang melibatkan peningkatan satu juta kali lipat dalam perhitungan ... Bisakah Anda menunggu lama?)

Sejauh solusi analitis berjalan, beberapa penyederhanaan tersedia. (Ini juga dapat digunakan untuk mempersingkat perhitungan Monte Carlo.) Jumlah sel kosong yang diharapkan adalah jumlah probabilitas kekosongan atas semua sel. Untuk menemukan ini, Anda bisa menghitung distribusi probabilitas angka hunian setiap sel. Distribusi tersebut diperoleh dengan menjumlahkan kontribusi (independen!) Dari setiap kutu. Ini mengurangi masalah Anda untuk menemukan jumlah jalur panjang 50 sepanjang 30 dengan 30 kisi antara setiap pasangan sel pada kisi itu (satu adalah asal kutu dan satunya lagi adalah sel yang ingin Anda hitung probabilitas dari hunian kutu).

Bisakah Anda tidak mengulangi melalui probabilitas pendudukan sel untuk setiap kutu. Artinya, kutu awalnya dalam sel (i (k), j (k)) dengan probabilitas 1. Setelah 1 iterasi, ia memiliki probabilitas 1/4 di masing-masing 4 sel yang berdekatan (dengan asumsi ia tidak berada di tepi atau di sebuah sudut). Kemudian iterasi berikutnya, masing-masing tempat itu akan "dioleskan" pada gilirannya. Setelah 50 iterasi Anda memiliki matriks probabilitas pekerjaan untuk kutu. Ulangi lebih dari 900 kutu (jika Anda mengambil keuntungan dari simetri ini mengurangi hampir faktor 8) dan menambahkan probabilitas (Anda tidak perlu menyimpan semuanya sekaligus, hanya matriks kutu saat ini (hmm, kecuali Anda sangat pintar, Anda mungkin ingin matriks kerja tambahan) dan jumlah matriks saat ini). Menurut saya ada banyak cara untuk mempercepat ini di sana-sini.

Ini tidak melibatkan simulasi sama sekali. Namun, itu memang melibatkan cukup banyak perhitungan; seharusnya tidak terlalu sulit untuk menentukan ukuran simulasi yang diperlukan untuk memberikan jawaban yang lebih baik daripada akurasi 6 dp dengan probabilitas tinggi dan mencari tahu pendekatan mana yang akan lebih cepat. Saya berharap pendekatan ini akan mengalahkan simulasi dengan beberapa margin.

Sementara saya tidak keberatan dengan ketidakmungkinan praktis (atau ketidakpraktisan) dari resolusi Monte Carlo masalah ini dengan ketepatan 6 tempat desimal yang ditunjukkan oleh whuber , saya akan berpikir resolusi dengan enam digit akurasi dapat dicapai.

$t+1$$t$$K$

$K^2$

$\hat{p}_0$$50$$(\mathbf{X}^{(t)})$

pot=rep(c(rep(c(0,1),15),rep(c(1,0),15)),15)*c(2,
    rep(3,28),2,rep(c(3,rep(4,28),3),28),2,rep(3,28),2)
pot=pot/sum(pot)
sum((1-pot)^450)-450
[1] 166.1069

$166.11$

Seperti dikomentari oleh whuber , estimasi harus dikalikan dengan 2 untuk menjawab pertanyaan dengan benar, sehingga nilai akhir 332.2137,

Suatu pendekatan analitis mungkin membosankan dan saya belum memikirkan seluk-beluknya tetapi inilah pendekatan yang mungkin ingin Anda pertimbangkan. Karena Anda tertarik pada jumlah sel yang diharapkan yang kosong setelah 50 cincin, Anda perlu menentukan rantai markov di atas "Tidak ada kutu dalam sel" daripada posisi kutu (Lihat jawaban Glen_b yang memodelkan posisi kutu sebagai rantai markov. Seperti yang ditunjukkan oleh Andy dalam komentar untuk jawaban itu bahwa pendekatan mungkin tidak mendapatkan apa yang Anda inginkan.)

Secara khusus, biarkan:

$n_{ij}(t)$$i$$j$

Kemudian rantai markov dimulai dengan status berikut:

$n_{ij}(0) =1$$i$$j$

Karena, kutu pindah ke salah satu dari empat sel yang berdekatan, keadaan sel berubah tergantung pada berapa banyak kutu di dalam sel target dan berapa banyak kutu yang ada di empat sel yang berdekatan dan probabilitas bahwa mereka akan pindah ke sel itu. Dengan menggunakan pengamatan ini, Anda dapat menulis probabilitas transisi keadaan untuk setiap sel sebagai fungsi dari keadaan sel itu dan keadaan sel yang berdekatan.

Jika Anda mau, saya bisa memperluas jawabannya lebih lanjut tetapi ini bersama dengan pengantar dasar untuk rantai markov harus membantu Anda memulai.

jika Anda akan pergi ke rute numerik, pengamatan sederhana: masalah tampaknya tunduk pada paritas merah-hitam (kutu di kotak merah selalu bergerak ke kotak hitam, dan sebaliknya). Ini dapat membantu mengurangi ukuran masalah Anda menjadi setengah (pertimbangkan saja dua gerakan pada satu waktu, dan hanya lihat kutu di kotak merah, katakanlah.)

Saya menduga bahwa beberapa pengetahuan tentang rantai Markov waktu diskrit terbukti bermanfaat.