To pytanie jest inspirowane minigierką Pokemon Soulsilver:

Wyobraź sobie, że na tym obszarze 5x6 jest ukrytych 15 bomb (EDYCJA: maksymalnie 1 bomba / komórka):

Jak oszacowałbyś prawdopodobieństwo znalezienia bomby na określonym polu, biorąc pod uwagę sumy wierszy / kolumn?

Jeśli spojrzysz na kolumnę 5 (suma bomb = 5), możesz pomyśleć: W tej kolumnie szansa na znalezienie bomby w rzędzie 2 jest dwukrotnie większa niż szansa na znalezienie jednej w rzędzie 1.

To (błędne) założenie o bezpośredniej proporcjonalności, które w zasadzie można opisać jako wciągnięcie standardowych operacji testu niezależności (jak w Chi-Square) w niewłaściwy kontekst, doprowadziłoby do następujących szacunków:

Jak widać, bezpośrednia proporcjonalność prowadzi do oszacowań prawdopodobieństwa ponad 100%, a nawet wcześniej byłoby to błędem.

Przeprowadziłem więc symulację obliczeniową wszystkich możliwych permutacji, co doprowadziło do 276 unikalnych możliwości umieszczenia 15 bomb. (podane sumy wierszy i kolumn)

Oto średnia z 276 rozwiązań:

To poprawne rozwiązanie, ale ze względu na wykładniczą pracę obliczeniową chciałbym znaleźć metodę szacunkową.

Moje pytanie brzmi teraz: czy istnieje ustalona statystyczna metoda oszacowania tego? Zastanawiałem się, czy to znany problem, jak się nazywa i czy są jakieś dokumenty / strony internetowe, które możesz polecić!

Przestrzeń rozwiązania (prawidłowe konfiguracje bomb) może być postrzegana jako zestaw wykresów dwustronnych o podanej kolejności stopni. (Siatka jest matrycą biadjacencji.) Do generowania równomiernego rozkładu w tej przestrzeni można podejść metodami Markova Chain Monte Carlo (MCMC): każde rozwiązanie można uzyskać z dowolnego innego przy użyciu sekwencji „przełączników”, które w twojej układance wygląda jak:

$$\begin{pmatrix} x & - \\ - & x \end{pmatrix} \to \begin{pmatrix} - & x \\ x & - \end{pmatrix}$$

Udowodniono, że ma to właściwości szybkiego mieszania. Tak więc, zaczynając od dowolnej prawidłowej konfiguracji i ustawiając MCMC działającą przez jakiś czas, powinieneś skończyć z przybliżeniem równomiernego rozkładu w rozwiązaniach, które możesz uśrednić punktowo dla prawdopodobieństw, których szukasz.

Znam tylko trochę te podejścia i ich aspekty obliczeniowe, ale przynajmniej w ten sposób unikniesz wyliczenia któregoś z nierozwiązań.

Początek literatury na ten temat:
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

Nie ma unikalnego rozwiązania

Nie sądzę, aby można było odzyskać prawdziwy dyskretny rozkład prawdopodobieństwa, chyba że poczynisz dodatkowe założenia. Twoja sytuacja to w zasadzie problem z odzyskaniem wspólnej dystrybucji z marginesów. Czasami rozwiązuje się to za pomocą kopuł w branży, na przykład zarządzania ryzykiem finansowym, ale zwykle w przypadku ciągłych dystrybucji.

Obecność, Independent, AS 205

W przypadku problemu obecności w celi nie może znajdować się więcej niż jedna bomba. Ponownie, w szczególnym przypadku niezależności, istnieje stosunkowo wydajne rozwiązanie obliczeniowe.

Jeśli znasz FORTRAN, możesz użyć tego kodu, który implementuje algorytm AS 205: Ian Saunders, Algorytm AS 205: Wyliczanie tabel R x C z powtarzającymi się sumami wierszy, Statystyka stosowana, tom 33, numer 3, 1984, strony 340-352. Jest to związane z algo Panefielda, o którym wspominał @Glen_B.

Ten algo wylicza wszystkie tabele obecności, tzn. Przechodzi przez wszystkie możliwe tabele, w których tylko jedna bomba znajduje się na polu. Oblicza również krotność, tj. Wiele tabel, które wyglądają tak samo, i oblicza pewne prawdopodobieństwa (nie te, które Cię interesują). Dzięki temu algorytmowi możesz być w stanie uruchomić pełne wyliczenie szybciej niż wcześniej.

Obecność, nie niezależna

Algorytm AS 205 można zastosować w przypadku, gdy wiersze i kolumny nie są niezależne. W takim przypadku należy zastosować różne wagi do każdej tabeli wygenerowanej przez logikę wyliczenia. Waga będzie zależeć od procesu umieszczania bomb.

Liczy się, niezależność

Ilość problemu pozwala więcej niż jedną bombę umieszczoną w komórce, oczywiście. Szczególny przypadek niezależnych wierszy i kolumn zliczania jest prosty: gdzie i są marginesami wierszy i kolumn. Na przykład wiersz a kolumna , stąd prawdopodobieństwo, że bomba jest w rzędzie 6, a kolumna 3 to . Tak naprawdę stworzyłeś tę dystrybucję w swoim pierwszym stole.$P_i^j=P_i\times P^j$$P_i$$P^j$$P_6=3/15=0.2$$P^3=3/15=0.2$$P_6^3=0.04$

Liczy, nie jest niezależny, dyskretne kopuły

Aby rozwiązać problem zliczania, w którym wiersze i kolumny nie są niezależne, możemy zastosować dyskretne kopuły. Mają problemy: nie są wyjątkowe. Nie czyni ich jednak bezużytecznymi. Więc spróbuję zastosować dyskretne kopuły. Dobry ich przegląd można znaleźć w Genest, C. i J. Nešlehová (2007). Podkład na kopule dla danych zliczania. Astin Bull. 37 (2), 475–515.

Kopuły mogą być szczególnie przydatne, ponieważ zwykle pozwalają jawnie indukować zależność lub szacować ją na podstawie danych, gdy dane są dostępne. Mam na myśli zależność między rzędami i kolumnami podczas umieszczania bomb. Na przykład może się zdarzyć, że jeśli bomba znajduje się w pierwszym rzędzie, bardziej prawdopodobne jest, że będzie to również pierwsza kolumna.

Przykład

Zastosujmy kopułę Kimeldorfa i Sampsona do twoich danych, zakładając ponownie, że w komórce można umieścić więcej niż jedną bombę. Kopułę na zależność parametru jest określona jako: Można myśleć jako analog współczynnika korelacji.$\theta$

$$C(u,v)=(u^{-\theta}+u^{-\theta}-1)^{-1/\theta}$$ $\theta$

Niezależny

Zacznijmy od przypadku słabej zależności, , gdzie mamy następujące prawdopodobieństwa (PMF), a marginesowe pliki PDF są również wyświetlane na panelach po prawej i na dole:$\theta=0.000001$

Możesz zobaczyć, jak w kolumnie 5 prawdopodobieństwo drugiego rzędu ma dwa razy większe prawdopodobieństwo niż pierwszy rząd. Nie jest to sprzeczne z tym, co wydawało się sugerować w swoim pytaniu. Wszystkie prawdopodobieństwa sumują się oczywiście do 100%, podobnie jak marginesy na panelach pasują do częstotliwości. Na przykład kolumna 5 w dolnym panelu pokazuje 1/3, co odpowiada podanym 5 bombom spośród wszystkich 15 zgodnie z oczekiwaniami.

Pozytywna korelacja

Dla silniejszej zależności (korelacja dodatnia) z mamy:$\theta=10$

Ujemna korelacja

To samo dotyczy silniejszej, ale ujemnej korelacji (zależności) :$\theta=-0.2$

Widać, że wszystkie prawdopodobieństwa sumują się do 100%, oczywiście. Możesz także zobaczyć, jak zależność wpływa na kształt PMF. Dla dodatniej zależności (korelacji) otrzymujesz najwyższy PMF skoncentrowany na przekątnej, podczas gdy dla ujemnej zależności jest on nie przekątny

Twoje pytanie nie wyjaśnia tego, ale zakładam, że bomby są początkowo dystrybuowane poprzez proste losowe pobieranie próbek bez zastępowania komórek (więc komórka nie może zawierać więcej niż jednej bomby). Pytanie, które postawiłeś, zasadniczo dotyczy opracowania metody szacowania rozkładu prawdopodobieństwa, który można obliczyć dokładnie (teoretycznie), ale który staje się niemożliwy do obliczenia dla dużych wartości parametrów.

---

Dokładne rozwiązanie istnieje, ale wymaga dużej mocy obliczeniowej

Jak wskazano w pytaniu, możliwe jest przeprowadzenie obliczeniowego wyszukiwania wszystkich możliwych przydziałów w celu zidentyfikowania przydziałów pasujących do sum wierszy i kolumn. Możemy postępować formalnie w następujący sposób. Załóżmy, że mamy do czynienia z siatkę i przydziela bomby poprzez pobieranie próbek losowych bez wymiany (czyli każda komórka nie może zawierać więcej niż jedną bombę).$n \times m$$b$

Niech będzie wektorem zmiennych wskaźnikowych wskazujących, czy w każdej komórce jest bomba, i niech oznaczają odpowiedni wektor sum wierszy i kolumn. Zdefiniuj funkcję , która odwzorowuje z wektora alokacji na sumy wierszy i kolumn.$\mathbf{x} = (x_1,...,x_{nm})$$\mathbf{s} = (r_1, ..., r_n, c_1, ..., c_m)$$S: \mathbf{x} \mapsto \mathbf{s}$

Celem jest określenie prawdopodobieństwa każdego wektora alokacji pod warunkiem znajomości sum wierszy i kolumn. Pod prostym losowym próbkowaniem mamy , więc warunkowe prawdopodobieństwo zainteresowania wynosi:$\mathbb{P}(\mathbf{x}) \propto 1$

$$\begin{equation} \begin{aligned} \mathbb{P}(\mathbf{x} | \mathbf{s}) = \frac{\mathbb{P}(\mathbf{x}, \mathbf{s})}{\mathbb{P}(\mathbf{s})} &= \frac{\mathbb{P}(\mathbf{x}) \cdot \mathbb{I}(S(\mathbf{x}) = \mathbf{s})}{\sum_\mathbf{x} \mathbb{P}(\mathbf{x}) \cdot \mathbb{I}(S(\mathbf{x}) = \mathbf{s})} \\[6pt] &= \frac{\mathbb{I}(S(\mathbf{x}) = \mathbf{s})}{\sum_\mathbf{x} \mathbb{I}(S(\mathbf{x}) = \mathbf{s})} \\[6pt] &= \frac{1}{|\mathscr{X}_\mathbf{s}|} \cdot \mathbb{I}(S(\mathbf{x}) = \mathbf{s}) \\[6pt] &= \text{U}(\mathbf{x} | \mathscr{X}_\mathbf{s}), \\[6pt] \end{aligned} \end{equation}$$

gdzie to zestaw wszystkich wektorów alokacji zgodnych z wektorem . To pokazuje, że (przy prostym losowym próbkowaniu bomb) mamy . Oznacza to, że warunkowy rozkład wektora alokacji dla bomb jest jednolity w zbiorze wszystkich wektorów alokacji zgodnych z obserwowanymi sumami wierszy i kolumn. Marginalne prawdopodobieństwo bomby w danej komórce można następnie uzyskać poprzez marginalizację w obrębie tego wspólnego rozkładu:$\mathscr{X}_\mathbf{s} \equiv \{ \mathbf{x} \in \{ 0, 1\}^{nm} | S(\mathbf{x}) = \mathbf{s} \}$$\mathbf{s}$$\mathbf{x} | \mathbf{s} \sim \text{U}(\mathscr{X}_\mathbf{s})$

$$\begin{equation} \begin{aligned} \mathbb{P}(x_{ij} = 1 | \mathbf{s}) = \sum_{\mathbf{x}: x_{ij} = 1} \text{U}(\mathbf{x} | \mathscr{X}_\mathbf{s}) = \frac{|\mathscr{X}_{ij} \cap \mathscr{X}_\mathbf{s}|}{|\mathscr{X}_\mathbf{s}|}. \end{aligned} \end{equation}$$

gdzie to zbiór wszystkich wektorów alokacji z bombą w komórce w tym rzędzie i tej kolumnie. Teraz w swoim konkretnym problemie obliczyłeś zestaw i że , więc prawdopodobieństwo warunkowe wektorów alokacji jest jednolite w stosunku do zestawu alokacji, który obliczyłeś (zakładając, że zrobiłeś to poprawnie). To jest dokładne rozwiązanie problemu. Jednak obliczenie zestawu wymaga intensywnych obliczeń, dlatego obliczenia tego rozwiązania mogą stać się niemożliwe, gdy ,$\mathscr{X}_{ij} \equiv \{ \mathbf{x} \in \{ 0, 1\}^{nm} | x_{ij} = 1 \}$$i$$j$$\mathscr{X}_\mathbf{s}$$|\mathscr{X}_\mathbf{s}| = 276$$\mathscr{X}_\mathbf{s}$$n$$m$lub stają się większe.$b$

---

Poszukiwanie dobrych metod szacowania

W przypadku, gdy obliczenie zestawu jest niewykonalne , chcesz być w stanie oszacować krańcowe prawdopodobieństwo, że bomba znajdzie się w określonej komórce. Nie znam żadnych istniejących badań, które podałyby metody szacowania tego problemu, więc będzie to wymagać opracowania pewnych prawdopodobnych estymatorów, a następnie przetestowania ich wydajności pod kątem dokładnego rozwiązania przy użyciu symulacji komputerowych dla wartości parametrów, które są wystarczająco niskie, aby to zrobić. dać.$\mathscr{X}_\mathbf{s}$

Naiwny estymator empiryczny: Estymator, który zaproponowałeś i użyłeś w swoim zielonym stole, to:

$$\hat{\mathbb{P}}(x_{ij} = 1 | \mathbf{s}) = \frac{r_i}{b} \cdot \frac{c_j}{b} \cdot b = \frac{r_i \cdot c_j}{b}.$$

Ta metoda szacowania traktuje rzędy i kolumny jako niezależne i szacuje prawdopodobieństwo bomby w danym rzędzie / kolumnie na podstawie względnych częstotliwości w sumach wierszy i kolumn. Łatwo jest ustalić, że estymator sumuje się do we wszystkich komórkach, jak chcesz. Niestety ma on główną wadę, że w niektórych przypadkach może dać oszacowane prawdopodobieństwo powyżej jednego. To zła właściwość dla estymatora.$b$