Wo ist die Bombe: Wie schätzt man die Wahrscheinlichkeit, gegebene Zeilen- und Spaltensummen?

14

Diese Frage ist von einem Minispiel von Pokemon Soulsilver inspiriert:

Stellen Sie sich vor, in diesem 5x6-Bereich sind 15 Bomben versteckt (BEARBEITEN: maximal 1 Bombe / Zelle):

Summen

Wie schätzen Sie die Wahrscheinlichkeit ein, eine Bombe auf einem bestimmten Feld zu finden, wenn man die Gesamtzahl der Zeilen / Spalten berücksichtigt?

Wenn Sie sich Spalte 5 ansehen (Gesamtzahl der Bomben = 5), könnten Sie denken: Innerhalb dieser Spalte ist die Chance, eine Bombe in Zeile 2 zu finden, doppelt so hoch wie in Zeile 1.

Diese (falsche) Annahme der direkten Proportionalität, die im Grunde genommen so beschrieben werden kann, dass standardmäßige Unabhängigkeitstestoperationen (wie im Chi-Quadrat) in den falschen Kontext gestellt werden, würde zu folgenden Schätzungen führen:

Chi-Platz

Wie Sie sehen, führt die direkte Proportionalität zu Wahrscheinlichkeitsschätzungen von über 100% und wäre sogar vorher falsch.

Also habe ich eine Computersimulation aller möglichen Permutationen durchgeführt, die zu 276 einzigartigen Möglichkeiten geführt hat, 15 Bomben zu platzieren. (gegebene Zeilen- und Spaltensummen)

Hier ist der Durchschnitt über die 276 Lösungen: Computerlösung

Dies ist die richtige Lösung, aber aufgrund der exponentiellen Rechenarbeit würde ich gerne eine Schätzmethode finden.

Meine Frage lautet nun: Gibt es eine etablierte statistische Methode, um dies abzuschätzen? Ich habe mich gefragt, ob dies ein bekanntes Problem ist, wie es heißt und ob es Artikel / Websites gibt, die Sie empfehlen können!

KaPy3141
quelle
1
Schneller und einfacher Ansatz: Für eine höhere Anzahl von Zeilen und Spalten können Sie eine Monte-Carlo-Simulation durchführen, bei der Sie das zufällige Teilmuster der möglichen Konfigurationen überprüfen, das niedriger ist als die Gesamtanzahl der Möglichkeiten. Es würde Ihnen eine ungefähre Lösung geben.
Tim
1
Ich verstehe Ihre rechnerische Lösung nicht. Was sind die Zahlen in Zellen? Sie summieren sich sicherlich nicht zu 100%, es ist kein PMF. Sie sehen auch nicht aus wie CDF, die rechte / untere Zelle ist nicht 100%
Aksakal
2
@Aksakal Dies sind die Grenzwahrscheinlichkeiten, mit denen eine bestimmte Zelle eine Bombe enthält. Die Zahlen addieren sich zu 15, der Gesamtzahl der Bomben auf dem Brett.
Dougal
2
Wenn Sie davon ausgehen, dass die beiden Ränder unabhängig sind, ist es relativ einfach, eine Stichprobe aus der Verteilung von Tabellen zu ziehen, die von den Rändern abhängig sind (über den Patefield-Algorithmus). Dies ist in der Standardverteilung von R in implementiert r2dtable(und wird auch von chisq.testund fisher.testunter bestimmten Umständen verwendet).
Glen_b -Reinstate Monica
2
@Glen_b Im Patefield-Algorithmus ist die Anzahl der Ereignisse pro Zelle jedoch nicht auf eins beschränkt.
Jarle Tufto

Antworten:

3

Der Lösungsraum (gültige Bombenkonfigurationen) kann als Satz von zweigeteilten Diagrammen mit gegebener Gradfolge angesehen werden. (Das Gitter ist die Biadjazenzmatrix.) Die Erzeugung einer gleichmäßigen Verteilung auf diesem Raum kann mit den Markov-Chain-Monte-Carlo-Methoden (MCMC) erreicht werden: Jede Lösung kann mit Hilfe einer Folge von "Schaltern", die in Ihrer Puzzleformulierung enthalten sind, aus jeder anderen Lösung erhalten werden aussehen wie:

(xx)(xx)

Es wurde nachgewiesen, dass dies eine schnelle Vermischungseigenschaft hat. Beginnen Sie also mit einer gültigen Konfiguration und setzen Sie einen MCMC, der eine Weile ausgeführt wird, um eine Annäherung an die gleichmäßige Verteilung der Lösungen zu erhalten, die Sie punktweise für die gesuchten Wahrscheinlichkeiten mitteln können.

Ich bin mit diesen Ansätzen und ihren rechnerischen Aspekten nur vage vertraut, aber zumindest vermeiden Sie auf diese Weise, eine der Nichtlösungen aufzulisten.

Ein Anfang der Literatur zum Thema:
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
quelle
Das ist eine tolle Idee! Ich glaube ich verstehe! Ich durchmische jede bekannte Lösung für eine definierte Anzahl von Iterationen (die ich in den Artikeln erwarten würde) und mittle anschließend über die einzigartigen Lösungen, in der Hoffnung, dass die meisten gefunden werden. Vielen Dank!
KaPy3141
2
MCMC ist genau der
richtige
@ KaPy3141 Für die obigen Zeilen- und Spaltensummen werden bei meiner Implementierung des Rechteckschleifenalgorithmus (im Vorabdruck von arxiv) nur 276 eindeutige Status angezeigt, selbst wenn der Algorithmus für bis zu Iterationen ausgeführt wird. 106
Jarle Tufto
Was darauf hindeutet, dass die von @Aksakal vorgeschlagene Aufzählung möglicherweise effizienter ist.
Jarle Tufto
@ JarleTufto, aber OP sagt, dass es nur 276 eindeutige (gültige) Zustände gibt; du hast sie alle gefunden!
Ben Reiniger
5

Es gibt keine eindeutige Lösung

Ich glaube nicht, dass eine echte diskrete Wahrscheinlichkeitsverteilung wiederhergestellt werden kann, es sei denn, Sie machen einige zusätzliche Annahmen. Ihre Situation ist im Grunde ein Problem der Wiederherstellung der gemeinsamen Verteilung von Marginals. Es wird manchmal durch die Verwendung von Copulas in der Branche gelöst , beispielsweise durch das Finanzrisikomanagement, normalerweise jedoch für kontinuierliche Verteilungen.

Präsenz, unabhängig, AS 205

Bei Anwesenheitsproblemen ist nicht mehr als eine Bombe in einer Zelle erlaubt. Auch für den Sonderfall der Unabhängigkeit gibt es eine relativ effiziente Rechenlösung.

Wenn Sie FORTRAN kennen, können Sie diesen Code verwenden , der den AS 205-Algorithmus implementiert: Ian Saunders, Algorithmus AS 205: Aufzählung von R x C-Tabellen mit wiederholten Zeilensummen, Angewandte Statistik, Band 33, Nummer 3, 1984, Seiten 340-352. Es ist verwandt mit Panefields Algo, auf das sich @Glen_B bezieht.

Dieser Algorithmus zählt alle Präsenztabellen auf, dh durchläuft alle möglichen Tabellen, in denen sich nur eine Bombe in einem Feld befindet. Es berechnet auch die Multiplizität, dh mehrere Tabellen, die gleich aussehen, und berechnet einige Wahrscheinlichkeiten (nicht die, an denen Sie interessiert sind). Mit diesem Algorithmus können Sie die vollständige Aufzählung möglicherweise schneller ausführen als zuvor.

Präsenz, nicht unabhängig

Der AS 205-Algorithmus kann auf einen Fall angewendet werden, in dem die Zeilen und Spalten nicht unabhängig sind. In diesem Fall müssten Sie für jede von der Aufzählungslogik generierte Tabelle eine andere Gewichtung anwenden. Das Gewicht hängt vom Platzierungsprozess der Bomben ab.

Grafen, Unabhängigkeit

Das Zählproblem erlaubt natürlich mehr als eine Bombe in einer Zelle. Der Sonderfall von unabhängigen Reihen und Spalten der Zählung Problem ist einfach: Pij=Pi×Pj wobei Pi und Pj sind Rn von Zeilen und Spalten. Zum Beispiel Zeile P6=3/15=0.2 und Spalte P3=3/15=0.2 , daher ist die Wahrscheinlichkeit , dass eine Bombe in Zeile 6 und Spalte 3 istP63=0.04 . Sie haben diese Distribution tatsächlich in Ihrer ersten Tabelle erstellt.

Zählt, nicht unabhängig, diskrete Copulas

Um das Zählproblem zu lösen, bei dem Zeilen und Spalten nicht unabhängig voneinander sind, können wir diskrete Copulas anwenden. Sie haben Probleme: Sie sind nicht einzigartig. Es macht sie jedoch nicht unbrauchbar. Also würde ich versuchen, diskrete Copulas anzuwenden. Einen guten Überblick finden Sie in Genest, C. und J. Nešlehová (2007). Ein Primer für Copulas für Zähldaten. Astin Bull. 37 (2), 475–515.

Copulas können besonders nützlich sein, da sie es normalerweise ermöglichen, eine Abhängigkeit explizit zu induzieren oder sie anhand von Daten zu schätzen, wenn die Daten verfügbar sind. Ich meine die Abhängigkeit von Zeilen und Spalten beim Platzieren von Bomben. Zum Beispiel könnte es der Fall sein, wenn die Bombe eine der ersten Reihen ist, dann ist es wahrscheinlicher, dass es auch eine der ersten Spalten ist.

Beispiel

θ

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

Unabhängig

θ=0.000001

Bildbeschreibung hier eingeben

Sie können sehen, dass in Spalte 5 die Wahrscheinlichkeit für die zweite Zeile doppelt so hoch ist wie die Wahrscheinlichkeit für die erste Zeile. Dies ist nicht falsch im Gegensatz zu dem, was Sie in Ihrer Frage zu implizieren schienen. Alle Wahrscheinlichkeiten summieren sich natürlich zu 100%, ebenso wie die Ränder auf den Panels mit den Frequenzen übereinstimmen. Zum Beispiel zeigt die Spalte 5 in der unteren Tafel 1/3, was erwartungsgemäß den angegebenen 5 von insgesamt 15 Bomben entspricht.

Positive Korrelation

θ=10

Bildbeschreibung hier eingeben

Negative Korrelation

θ=0.2

Bildbeschreibung hier eingeben

Sie sehen natürlich, dass sich alle Wahrscheinlichkeiten zu 100% summieren. Außerdem können Sie sehen, wie sich die Abhängigkeit auf die Form der PMF auswirkt. Für die positive Abhängigkeit (Korrelation) erhalten Sie die höchste PMF, die auf die Diagonale konzentriert ist, während sie für die negative Abhängigkeit außerhalb der Diagonale liegt

Aksakal
quelle
Vielen Dank für Ihre Antwort und Ihre interessanten Links zu Copulas! Leider habe ich noch nie Copulas verwendet, so dass es für mich schwierig sein wird, eine Lösung zu finden, die nur 1 Bombe pro Zelle erzwingt, aber ich werde es auf jeden Fall versuchen, sobald ich ein besseres Verständnis habe!
KaPy3141
@ KaPy3141, Ich habe einen Verweis auf den Code hinzugefügt, mit dem Sie das Problem lösen können. Es ist in F90, aber relativ einfach, mit Numpy zu Python zu konvertieren
Aksakal
θθ
Sie müssten die Parameter an den Prozess anpassen. Das Problem ist rein kombinatorisch, wenn der Erzeugungsprozess damit übereinstimmt.
Aksakal
4

Ihre Frage macht dies nicht klar, aber ich gehe davon aus, dass die Bomben zunächst durch einfaches Zufallsstichprobenverfahren ohne Austausch über die Zellen verteilt werden (eine Zelle kann also nicht mehr als eine Bombe enthalten). Die Frage, die Sie aufgeworfen haben, ist im Wesentlichen die Entwicklung einer Schätzmethode für eine Wahrscheinlichkeitsverteilung, die (theoretisch) genau berechnet werden kann, die jedoch für die Berechnung großer Parameterwerte rechnerisch nicht mehr durchführbar ist.


Die genaue Lösung existiert, ist aber rechenintensiv

n×mb

x=(x1,...,xnm)s=(r1,...,rn,c1,...,cm)S:xs, die vom Zuordnungsvektor auf die Zeilen- und Spaltensummen abbildet.

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). Das heißt, die bedingte Verteilung des Zuordnungsvektors für die Bomben ist gleichmäßig über die Menge aller Zuordnungsvektoren, die mit den beobachteten Zeilen- und Spaltensummen kompatibel sind. Die Grenzwahrscheinlichkeit einer Bombe in einer gegebenen Zelle kann dann durch Marginalisierung über diese gemeinsame Verteilung erhalten werden:

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

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


Suche nach guten Schätzmethoden

Xs

Der naive empirische Schätzer: Der Schätzer, den Sie in Ihrer grünen Tabelle vorgeschlagen und verwendet haben, ist:

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

b

Setzen Sie Monica wieder ein
quelle
Vielen Dank für Ihre ausführliche Antwort! Tatsächlich gibt es in meinem grünen Diagramm bereits Werte von bis zu 133%. Es ist gut zu wissen, dass es keine beliebte Methode für dieses Problem gibt und es akzeptabel ist, selbst zu experimentieren! Mein genauester Schätzer ähnelt dem "grünen" Ansatz, aber anstatt die Bomben proportional zu P (Reihe) / Summe (P (Reihen)) * P (c) / Summe (P (Spalten)) zuzuweisen, verwende ich ein imaginäres P (r) / (1-P (r)) / Summe (Reihen) und danach das Produkt zurückbringen: P (real) = P (imag) / (1 + P (imag). Dies erzwingt P <1. Jetzt muss ich wohl nur noch die (leicht verletzten) Zeilen- / Spaltensummen rechnerisch durchsetzen
KaPy3141
@ KaPy3141 Sie können den Wert verwenden, den eine bestimmte Bombe in einer Zelle hat (der nicht das Problem hat, über 1 zu liegen), und dann das Problem als Ziehung von 15 Bomben aus dieser Verteilung mit der Bedingung beschreiben, dass jede Zelle nur hat Werte 0 oder 1 (Zeichnung ohne Ersatz). Dies gibt Ihnen eine Wahrscheinlichkeit, die 1 nicht überschreitet.
Sextus Empiricus