Di mana bomnya: Bagaimana memperkirakan probabilitas, diberikan total baris dan kolom?

14

Pertanyaan ini terinspirasi oleh game-mini dari Pokemon Soulsilver:

Bayangkan ada 15 bom tersembunyi di area 5x6 ini (EDIT: maksimum 1 bom / sel):

Jumlah

Sekarang, bagaimana Anda memperkirakan probabilitas untuk menemukan bom di bidang tertentu, mengingat total baris / kolom?

Jika Anda melihat kolom 5 (total bom = 5), maka Anda mungkin berpikir: Di dalam kolom ini peluang untuk menemukan bom di baris 2 adalah dua kali lipat peluang untuk menemukan satu di baris 1.

Asumsi proporsionalitas langsung (yang salah) ini, yang pada dasarnya dapat digambarkan sebagai menggambar operasi uji independensi standar (seperti dalam Chi-Square) ke dalam konteks yang salah, akan mengarah pada estimasi berikut:

Chi-Square

Seperti yang Anda lihat, proporsionalitas langsung mengarah pada perkiraan probabilitas lebih dari 100%, dan bahkan sebelum itu, akan salah.

Jadi saya melakukan simulasi komputasi dari semua kemungkinan permutasi yang menghasilkan 276 kemungkinan unik untuk menempatkan 15 bom. (total baris dan kolom yang diberikan)

Berikut adalah rata-rata dari 276 solusi: Solusi komputasi

Ini adalah solusi yang tepat, tetapi karena pekerjaan komputasi eksponensial, saya ingin menemukan metode estimasi.

Pertanyaan saya sekarang: Apakah ada metode statistik yang mapan untuk memperkirakan ini? Saya bertanya-tanya apakah ini masalah yang diketahui, bagaimana namanya dan apakah ada makalah / situs web yang bisa Anda rekomendasikan!

KaPy3141
sumber
1
Pendekatan cepat dan mudah: Untuk jumlah baris & kolom yang lebih tinggi, Anda dapat melakukan simulasi Monte Carlo, di mana Anda akan memeriksa subsampel acak dari kemungkinan konfigurasi yang lebih rendah daripada jumlah total kemungkinan. Itu akan memberi Anda solusi perkiraan.
Tim
1
Saya tidak mengerti solusi komputasi Anda. Berapa angka dalam sel? Mereka tentu saja tidak menambahkan hingga 100%, itu bukan PMF. Mereka juga tidak terlihat seperti CDF, sel kanan / bawah tidak 100%
Aksakal
2
@Aksakal Ini adalah probabilitas marginal yang diberikan oleh setiap sel yang berisi bom. Jumlahnya bertambah menjadi 15, jumlah total bom di papan tulis.
Dougal
2
Jika Anda mengasumsikan dua margin independen itu relatif mudah untuk sampel dari distribusi tabel bersyarat pada margin (melalui algoritma Patefield). Ini diimplementasikan dalam distribusi standar R in r2dtable(dan juga digunakan oleh chisq.testdan fisher.testdalam beberapa keadaan).
Glen_b -Reinstate Monica
2
@ Glen_b Tetapi dalam algoritma Patefield jumlah acara per sel tidak terbatas pada satu.
Jarle Tufto

Jawaban:

3

Ruang solusi (konfigurasi bom yang valid) dapat dilihat sebagai set grafik bipartit dengan urutan derajat yang diberikan. (Grid adalah matriks biadjacency.) Menghasilkan distribusi seragam pada ruang itu dapat didekati menggunakan metode Markov Chain Monte Carlo (MCMC): setiap solusi dapat diperoleh dari yang lain menggunakan urutan "switch," yang dalam formulasi puzzle Anda terlihat seperti:

(xx)(xx)

Sudah terbukti bahwa ini memiliki sifat pencampuran cepat. Jadi, dimulai dengan konfigurasi yang valid dan pengaturan MCMC berjalan untuk sementara waktu, Anda harus berakhir dengan perkiraan distribusi seragam pada solusi, yang dapat Anda rata-rata secara langsung untuk probabilitas yang Anda cari.

Saya hanya samar-samar akrab dengan pendekatan ini dan aspek komputasi mereka, tetapi setidaknya dengan cara ini Anda menghindari menyebutkan salah satu dari non-solusi.

Sebuah permulaan untuk literatur tentang topik:
https://faculty.math.illinois.edu/~mlavrov/seminar/2018-erdos.pdf
https://arxiv.org/pdf/1701.07101.pdf
https: // www. tandfonline.com/doi/abs/10.1198/016214504000001303

Ben Reiniger
sumber
Itu ide yang luar biasa! Saya rasa saya mengerti! Saya mencampur melalui solusi yang dikenal untuk jumlah iterasi yang ditentukan (yang saya harapkan akan ditemukan di koran) dan kemudian rata-rata atas solusi unik, berharap sebagian besar dari mereka ditemukan. Terima kasih banyak!
KaPy3141
2
MCMC adalah cara yang tepat untuk pergi dan saya juga menemukan ini: arxiv.org/pdf/1904.03836.pdf
KaPy3141
106
Yang menunjukkan bahwa pencacahan seperti yang disarankan oleh @Aksakal mungkin lebih efisien.
Jarle Tufto
@ JarleTufto, tetapi OP mengatakan hanya ada 276 negara unik (valid); Anda telah menemukan semuanya!
Ben Reiniger
5

Tidak ada solusi unik

Saya tidak berpikir bahwa distribusi probabilitas diskrit yang sebenarnya dapat dipulihkan, kecuali jika Anda membuat beberapa asumsi tambahan. Situasi Anda pada dasarnya adalah masalah memulihkan distribusi bersama dari marginal. Kadang-kadang diselesaikan dengan menggunakan kopula di industri, misalnya manajemen risiko keuangan, tetapi biasanya untuk distribusi berkelanjutan.

Kehadiran, Independen, AS 205

Di hadapan masalah tidak lebih dari satu bom diperbolehkan di dalam sel. Sekali lagi, untuk kasus khusus independensi, ada solusi komputasi yang relatif efisien.

Jika Anda mengenal FORTRAN, Anda dapat menggunakan kode ini yang mengimplementasikan AS 205 Algoritma: Ian Saunders, Algorithm AS 205: Pencacahan Tabel R x C dengan Total Baris Berulang, Statistik Terapan, Volume 33, Nomor 3, 1984, halaman 340-352. Ini terkait dengan algo Panefield yang disebut @Glen_B.

Algo ini menghitung semua tabel keberadaan, yaitu menelusuri semua tabel yang mungkin ada di mana hanya satu bom berada di lapangan. Ini juga menghitung multiplisitas, yaitu beberapa tabel yang terlihat sama, dan menghitung beberapa probabilitas (bukan yang Anda minati). Dengan algoritme ini, Anda mungkin dapat menjalankan enumerasi lengkap lebih cepat dari yang Anda lakukan sebelumnya.

Kehadiran, tidak mandiri

Algoritma AS 205 dapat diterapkan pada kasus di mana baris dan kolom tidak independen. Dalam hal ini Anda harus menerapkan bobot yang berbeda untuk setiap tabel yang dihasilkan oleh logika enumerasi. Bobot akan tergantung pada proses penempatan bom.

Hitungan, independensi

Pij=Pi×PjPiPjP6=3/15=0.2P3=3/15=0.2P63=0.04

Hitungan, Tidak independen, Copula Terpisah

Untuk mengatasi masalah jumlah di mana baris dan kolom tidak independen, kita bisa menerapkan kopula diskrit. Mereka memiliki masalah: mereka tidak unik. Itu tidak membuat mereka sia-sia. Jadi, saya akan mencoba menerapkan kopula diskrit. Anda dapat menemukan ikhtisar yang baik tentang mereka di Genest, C. dan J. Nešlehová (2007). Primer pada copulas untuk menghitung data. Astin Bull. 37 (2), 475–515.

Kopula bisa sangat berguna, karena biasanya memungkinkan untuk secara eksplisit menginduksi ketergantungan, atau memperkirakannya dari data ketika data tersedia. Maksud saya ketergantungan baris dan kolom ketika menempatkan bom. Sebagai contoh, bisa jadi itu kasus ketika jika bom adalah salah satu baris pertama, maka kemungkinan besar itu akan menjadi salah satu kolom pertama juga.

Contoh

θ

C(u,v)=(uθ+uθ1)1/θ
θ

Independen

θ=0.000001

masukkan deskripsi gambar di sini

Anda dapat melihat bagaimana pada kolom 5 probabilitas baris kedua memiliki probabilitas dua kali lebih tinggi daripada baris pertama. Ini tidak salah, bertentangan dengan apa yang tampaknya Anda nyatakan dalam pertanyaan Anda. Semua probabilitas menambahkan hingga 100%, tentu saja, seperti halnya margin pada panel cocok dengan frekuensi. Misalnya, kolom 5 di panel bawah menunjukkan 1/3 yang sesuai dengan 5 bom yang disebutkan dari total 15 bom seperti yang diharapkan.

Korelasi positif

θ=10

masukkan deskripsi gambar di sini

Korelasi Negatif

θ=0.2

masukkan deskripsi gambar di sini

Anda dapat melihat bahwa semua probabilitas menambahkan hingga 100%, tentu saja. Anda juga dapat melihat bagaimana ketergantungan memengaruhi bentuk PMF. Untuk dependensi positif (korelasi) Anda mendapatkan PMF tertinggi yang terkonsentrasi pada diagonal, sedangkan untuk dependensi negatif itu adalah off-diagonal

Aksakal
sumber
Terima kasih banyak atas jawaban Anda dan tautan menarik Anda ke copulas! Sayangnya, saya belum pernah menggunakan kopula, jadi akan sulit bagi saya untuk menemukan solusi yang hanya memberlakukan 1 bom per sel, tetapi saya pasti akan mencoba setelah saya memiliki pemahaman yang lebih baik!
KaPy3141
@ KaPy3141, saya menambahkan referensi ke kode yang dapat Anda gunakan untuk menyelesaikan masalah. Ada di F90, tetapi relatif mudah untuk mengkonversi ke Python dengan numpy
Aksakal
θθ
Anda harus menyesuaikan parameter dengan proses. Masalahnya adalah kombinasi murni jika proses menghasilkan konsisten dengannya.
Aksakal
4

Pertanyaan Anda tidak memperjelas hal ini, tetapi saya akan berasumsi bahwa bom-bom tersebut awalnya didistribusikan melalui pengambilan sampel sederhana-acak tanpa penggantian sel (sehingga sebuah sel tidak dapat mengandung lebih dari satu bom). Pertanyaan yang Anda ajukan pada dasarnya meminta pengembangan metode estimasi untuk distribusi probabilitas yang dapat dihitung secara tepat (dalam teori), tetapi yang menjadi tidak layak secara komputasi untuk menghitung nilai parameter besar.


Solusi tepat ada, tetapi intensif secara komputasi

n×mb

x=(x1,...,xnm)s=(r1,...,rn,c1,...,cm)S:xs, yang memetakan dari vektor alokasi ke jumlah baris dan kolom.

P(x)1

P(x|s)=P(x,s)P(s)=P(x)I(S(x)=s)xP(x)I(S(x)=s)=I(S(x)=s)xI(S(x)=s)=1|Xs|I(S(x)=s)=U(x|Xs),

Xs{x{0,1}nm|S(x)=s}sx|sU(Xs). Yaitu, distribusi bersyarat dari vektor alokasi untuk bom-bom itu seragam di atas himpunan semua vektor alokasi yang kompatibel dengan total baris dan kolom yang diamati. Probabilitas marginal dari bom dalam sel tertentu kemudian dapat diperoleh dengan memarginalkan distribusi bersama ini:

P(xij=1|s)=x:xij=1U(x|Xs)=|XijXs||Xs|.

Xij{x{0,1}nm|xij=1}ijXs|Xs|=276Xsnmb


Mencari metode estimasi yang baik

Xs

Estimator empiris yang naif: Estimator yang telah Anda usulkan dan gunakan dalam tabel hijau Anda adalah:

P^(xij=1|s)=ribcjbb=ricjb.

b

Ben - Pasang kembali Monica
sumber
Terima kasih banyak atas jawaban mendalam Anda! Sebenarnya, dalam bagan hijau saya, sudah ada nilai hingga 133%. Adalah baik untuk mengetahui bahwa tidak ada metode populer untuk masalah ini dan dapat diterima untuk bereksperimen sendiri! Estimator saya yang paling akurat mirip dengan pendekatan "hijau", tetapi alih-alih mengalokasikan bom sebanding dengan P (baris) / jumlah (P (baris)) * P (c) / jumlah (P (cols)), saya menggunakan imajiner P (r) / (1-P (r)) / jumlah (baris) dan setelah itu mengembalikan produk: P (real) = P (imag) / (1 + P (imag) .Ini memaksa P <1. Sekarang saya kira, saya hanya perlu melakukan komputasi jumlah / baris (sedikit dilanggar)
komputasi
@ KaPy3141 Anda dapat menggunakan nilai bahwa bom tertentu berada di dalam sel (yang tidak memiliki masalah berada di atas 1) dan kemudian menggambarkan masalahnya sebagai undian 15 bom dari distribusi itu dengan ketentuan bahwa setiap sel hanya memiliki nilai 0 atau 1 (menggambar tanpa penggantian). Ini akan memberi Anda probabilitas yang tidak melebihi 1.
Sextus Empiricus