Saya punya pertanyaan tentang jalan acak dua raja di papan catur 3 × 3.
Setiap raja bergerak secara acak dengan probabilitas yang sama di papan catur ini - secara vertikal, horizontal dan diagonal. Kedua raja bergerak secara independen dari satu sama lain dalam papan catur yang sama. Keduanya mulai di alun-alun yang sama, dan kemudian mereka bergerak secara mandiri.
Bagaimana kita dapat menemukan probabilitas dalam waktu keduanya berada di bujur sangkar yang sama, ketika menuju tak terhingga?
Jawaban:
Mari kita manfaatkan simetri untuk menyederhanakan perhitungan.
Papan catur dan gerakannya tetap sama saat papan tersebut dipantulkan secara vertikal, horizontal, atau diagonal. Ini menguraikan sembilan kuadratnya menjadi tiga jenis, orbitnya di bawah grup simetri ini. Sejalan dengan itu, setiap raja dapat berada di salah satu dari tiga "negara": kotak sudut (C ), tepi kotak (E ), atau kuadrat pusat ("tengah") (M. ). (Negara mengabaikan kuadrat khusus mana raja berada dan hanya melacak kelas ekivalennya di bawah kelompok simetri.)
Hasil berikut ini langsung:
Dari kotak sudut, ada dua transisi ke kotak tepi dan satu transisi ke kotak tengah. Karena ketiga transisi tersebut dapat dilengkapi,
Ini memberikan baris dalam matriks transisi untuk status .( 0 , 2 / 3 , 1 / 3 ) ( C, E, M.)
Dari kotak tepi ada dua transisi ke kotak sudut, dua ke kotak tepi lainnya, dan satu ke kotak tengah. Ini memberikan baris kedua dalam matriks transisi.(2/5,2/5,1/5)
Dari kotak tengah ada empat transisi ke kotak sudut dan empat kotak ke tengah. Baris ketiga dari matriks transisi oleh karena itu adalah .(4/8,4/8,0)=(1/2,1/2,0)
Dalam grafik ini yang mewakili rantai Markov ini, probabilitas transisi diwakili oleh ketebalan tepi dan warna:
Dengan inspeksi atau sebaliknya, kami menemukan bahwa vektor eigen kiri dari matriks transisinya
is . Klaim ini mudah diperiksa dengan melakukan perkalian: Nilai eigen secara nyata adalah . Karena semua negara terhubung, memberikan probabilitas terbatas dari setiap raja di setiap negara; kita hanya perlu mengubah komponennya menjadi satu:ω=(3,5,2)′ ωP=1ω. 1 ω
(Sinilah kita menuai keuntungan dari mengeksploitasi simetri: alih-alih bekerja dengan sembilan oleh sembilan matriks elemen kita hanya perlu menghitung dengan tiga oleh tiga matriks elemen Pengurangan masalah dari sembilan negara ke tiga. terbayar secara kuadratik dengan mengurangi upaya komputasi dengan faktor )81 9 (9/3)2=9
Peluang (pembatas) bahwa kedua raja dalam keadaan (pembatas) probabilitas adalah karena para raja bergerak secara independen. Kesempatan yang baik raja berada di sel yang sama ditemukan oleh pendingin pada negara: dengan simetri, setiap sel dalam keadaan tertentu memiliki probabilitas membatasi sama, jadi jika kedua raja ditemukan dalam keadaan memiliki sel, kesempatan mereka keduanya di sel yang sama adalah . Dari mana solusinyas ωs ω2s s ks 1/ks
sumber
Karena kedua raja bergerak secara independen, Anda dapat mempertimbangkannya secara terpisah. Jika papan ukuran terbatas, dan tidak memiliki subbagian tertutup, ini adalah salah satu kasus di mana distribusi stasioner dapat ditemukan dengan menyelesaikan persamaan keseimbangan terperinci.
Dalam kasus ini, ketika menuju tak terhingga, probabilitas seorang raja berada di sebuah bujur sangkar menjadi proporsional dengan jumlah kuadrat yang berdekatan dengannya, yaitu tiga untuk setiap bujur sangkar sudut, lima untuk setiap bujur sangkar sudut, dan delapan untuk bujur sangkar tengah. Ini berjumlah , sehingga kemungkinan berada di alun-alun tengah adalah , di setiap sudut kuadrat adalah , dan di setiap tepi persegi adalah .n 40 8/40 3/40 5/40
Karena ini berlaku untuk kedua raja secara mandiri, kemungkinan mereka berdua berada di alun-alun tengah adalah , keduanya berada di sudut manapun adalah , dan di setiap edge square adalah . Jadi kemungkinan mereka berada di kotak yang sama mendekati ketika mendekati tak terhingga.(8/40)2=64/1600 (3/40)2=9/1600 (5/40)2=25/1600 64+4×9+4×251600=2001600=18 n
sumber
Anda dapat menyelesaikan dengan menggunakan matriks probabilitas transisi.
Bangun matriks probabilitas Transisi, menggunakan probabilitas satu sel ke sel lainnya. Misalnya: . P akan menjadi matriks .P[C1,C2]=P[C1,C4]=P[C1,C5]=13 9×9
Sekarang Anda dapat menghitung probabilitas stasioner (Karena semua negara berulang).
Selesaikan sedemikian rupa sehingga .πP=π ∑π=1
Ini memberikan probabilitas satu raja di bujur sangkar tertentu sebagai n besar. Gunakan properti independensi yang dapat Anda peroleh dengan probabilitas yang diperlukan.
sumber