Gdzie jest bomba: Jak oszacować prawdopodobieństwo, biorąc pod uwagę sumy wierszy i kolumn?


14

To pytanie jest inspirowane minigierką Pokemon Soulsilver:

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

Sumy

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:

Chi-Square

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ń: Rozwiązanie obliczeniowe

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ć!


1
Szybkie i łatwe podejście: w przypadku większej liczby wierszy i kolumn można przeprowadzić symulację Monte Carlo, w której można sprawdzić losową podpróbkę możliwych konfiguracji, która jest mniejsza niż całkowita liczba możliwości. To dałoby przybliżone rozwiązanie.
Tim

1
Nie rozumiem twojego rozwiązania obliczeniowego. Jakie są liczby w komórkach? Z pewnością nie sumują się do 100%, to nie jest PMF. Nie wyglądają też jak CDF, prawa / dolna komórka nie jest w 100%
Aksakal 23.0919

2
@Aksakal Są to marginalne prawdopodobieństwa, że ​​dana komórka zawiera bombę. Liczby sumują się do 15, całkowitej liczby bomb na planszy.
Dougal

2
Jeśli zakładasz, że dwa marginesy są niezależne, stosunkowo łatwo jest pobrać próbkę z rozkładu tabel zależnego od marginesów (za pomocą algorytmu Patefielda). Jest to zaimplementowane w standardowym rozkładzie R w r2dtable(a także wykorzystywane przez chisq.testiw fisher.testniektórych okolicznościach).
Glen_b -Reinstate Monica

2
@Glen_b Ale w algorytmie Patefield liczba zdarzeń na komórkę nie jest ograniczona do jednego.
Jarle Tufto

Odpowiedzi:


4

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:

(xx)(xx)

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


To niesamowity pomysł! Myślę, że rozumiem! Mieszam każde znane rozwiązanie dla określonej liczby iteracji (których spodziewam się znaleźć w artykułach), a następnie uśredniam w stosunku do unikalnych rozwiązań, mając nadzieję, że większość z nich zostanie znaleziona. Dzięki wielkie!
KaPy3141,

2
MCMC jest dokładnie taka droga i ja również tego: arxiv.org/pdf/1904.03836.pdf
KaPy3141

@ KaPy3141 W przypadku powyższych sum wierszy i kolumn moja implementacja algorytmu pętli prostokątnej (w prefiksie arxiv) odwiedza tylko 276 unikalnych stanów, nawet jeśli uruchomię algorytm dla aż iteracji. 106
Jarle Tufto,

Co sugeruje, że wyliczenie sugerowane przez @Aksakal może być bardziej wydajne.
Jarle Tufto,

@JarleTufto, ale OP twierdzi, że istnieje tylko 276 unikalnych (ważnych) stanów; znalazłeś je wszystkie!
Ben Reiniger,

5

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.Pij=Pi×PjPiPjP6=3/15=0.2P3=3/15=0.2P63=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.θ

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

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:θ=0.000001

wprowadź opis zdjęcia tutaj

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:θ=10

wprowadź opis zdjęcia tutaj

Ujemna korelacja

To samo dotyczy silniejszej, ale ujemnej korelacji (zależności) :θ=0.2

wprowadź opis zdjęcia tutaj

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


Bardzo dziękuję za odpowiedź i interesujące linki do kopuł! Niestety, nigdy nie korzystałem z kopuł, więc trudno będzie mi znaleźć rozwiązanie, które wymusza tylko 1 bombę na komórkę, ale na pewno spróbuję, gdy będę miał lepsze zrozumienie!
KaPy3141

@ KaPy3141, dodałem odwołanie do kodu, którego można użyć do rozwiązania problemu. Jest w F90, ale stosunkowo łatwo przekonwertować na Python za pomocą numpy
Aksakal

W jaki sposób kopuły z jakimś parametrem są rozwiązaniem problemu? W jaki sposób i skąd będziesz wiedzieć, że jest to odpowiedź (na przykład dziwny efekt w twojej odpowiedzi polega na tym, że wiersze o tym samym prawdopodobieństwie krańcowym dają różne prawdopodobieństwo komórki). Problem wydaje mi się problemem kombinatorycznym. θθ
Sextus Empiricus

Musisz dopasować parametry do procesu. Problem jest czysto kombinatoryczny, jeśli proces generowania jest z nim zgodny.
Aksakal

4

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×mb

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.x=(x1,...,xnm)s=(r1,...,rn,c1,...,cm)S:xs

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: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),

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:Xs{x{0,1}nm|S(x)=s}sx|sU(Xs)

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

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 ,Xij{x{0,1}nm|xij=1}ijXs|Xs|=276Xsnmlub 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ć.Xs

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

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

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


Dziękuję bardzo za wyczerpującą odpowiedź! Właściwie na moim zielonym wykresie są już wartości do 133%. Dobrze wiedzieć, że nie ma popularnej metody rozwiązywania tego problemu i można eksperymentować samodzielnie! Mój najdokładniejszy estymator jest podobny do podejścia „zielonego”, ale zamiast alokować bomby proporcjonalnie do P (wiersz) / suma (P (rzędy)) * P (c) / suma (P (cols)), używam urojone P (r) / (1-P (r)) / suma (wiersze), a następnie przywróć produkt: P (rzeczywisty) = P (imag) / (1 + P (imag). To wymusza P <1. Teraz chyba tylko muszę
wyliczyć

@ KaPy3141 możesz użyć wartości, że konkretna bomba znajduje się w celi (która nie ma problemu z byciem powyżej 1), a następnie opisać problem jako wyciągnięcie 15 bomb z tego rozkładu, pod warunkiem, że każda komórka ma tylko wartości 0 lub 1 (rysunek bez zamiany). Zapewni to prawdopodobieństwo, które nie przekracza 1.
Sextus Empiricus
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.