Frage:
Wahrscheinlichkeit, dass die Anzahl der Köpfe die Summe der Würfelwürfe überschreitet
user239903
2020-08-26 04:08:59 UTC
view on stackexchange narkive permalink

Lassen Sie $ X $ span> die Summe der Punkte bezeichnen, die wir in $ 100 $ span> Würfelwürfeln sehen, und lassen Sie $ Y $ span> bezeichnet die Anzahl der Köpfe in $ 600 $ span> Münzwürfen.Wie kann ich $ P (X > Y) berechnen? $ Span>

Intuitiv glaube ich nicht, dass es eine gute Möglichkeit gibt, die Wahrscheinlichkeit zu berechnen.Ich denke jedoch, dass wir $ P (X > Y) \ ca. 1 $ span> sagen können, da $ E (X) =350 $ span>, $ E (Y) = 300 $ span>, $ \ text {Var} (X) \ca. 292 $ span>, $ \ text {Var} (Y) = 150 $ span>, was bedeutet, dass die Standardabweichungen ziemlich klein sind.

Gibt es einen besseren Weg, um dieses Problem anzugehen?Meine Erklärung scheint ziemlich wellig zu sein, und ich würde gerne einen besseren Ansatz verstehen.

Eine Möglichkeit wäre, normale Annäherungen an $ X $ und $ Y zu verwenden, dann unabhängig von $ X-Y $
Ich würde nur eine normale Annäherung verwenden, wenn ich keine genaue Antwort benötige.
Ihre Erklärung * ist * handgewellt, und das ist ein großartiger Ansatz.Mit solchen schnellen und einfachen Berechnungen auf der Rückseite des Umschlags können Sie überprüfen, ob eine andere komplizierte Berechnung oder Modellanpassung überhaupt Sinn macht.Sie sind im Wesentlichen das Wahrscheinlichkeitsäquivalent von [Fermi-Problemen] (https://en.wikipedia.org/wiki/Fermi_problem).Wenn ich Sie interviewen würde, würde ich mich sehr über Ihre Ideen freuen.(Noch glücklicher, wenn Sie sich auch andere Ansätze ausgedacht haben, wie eine Simulation in einem Softwarepaket.)
Könnten Sie Ihren Inquisitor bitten, realistischer zu sein? "Jeder kennt" die Summe der Punkte, die wir in 100 Würfeln sehen sollten, und das wird nicht passieren.Der halbe Grund, warum Würfelspiele existieren. Als ich ungefähr 12 Jahre alt war, brachte ein Lehrer die Klasse dazu, Hunderte von Würfeln zu werfen, und das Ergebnis war sehr klar. Die Nummern zwei und fünf waren doppelt so wahrscheinlich wie die Statistiken es vorgaben.Bevor Sie das leugnen, versuchen Sie es! Warten Sie aber ... Nr. Zwei und fünf?Kennst du nicht mehrere Würfelspiele, die von sieben abhängen?Ist das nicht zu zweit oder zu fünft zu sagen?
Fünf antworten:
#1
+17
Henry
2020-08-26 14:34:35 UTC
view on stackexchange narkive permalink

Es ist möglich, genaue Berechnungen durchzuführen.Zum Beispiel in R

  rollt <-100
dreht <-600 um
ddice <-rep (1/6, 6)
für (n in 2: Rollen) {
  Würfel <- (c (0, Würfel, 0,0,0,0,0) + c (0,0, Würfel, 0,0,0,0) + c (0,0,0, Würfel, 0,0,0) +
            c (0,0,0,0, Würfel, 0,0) + c (0,0,0,0,0, Würfel, 0) + c (0,0,0,0,0,0, Würfel)) / 6}
sum (ddice * (1-pbinom (1: flips, flips, 1/2)) # Wahrscheinlichkeitsmünzen mehr
# 0.00809003
sum (ddice * dbinom (1: flips, flips, 1/2)) # Wahrscheinlichkeitsgleichheit
# 0.00111972
sum (ddice * pbinom (0: (flips-1), flips, 1/2)) # Wahrscheinlichkeitswürfel mehr
# 0.99079025
 

mit dieser letzten Zahl, die der BruceET-Simulation entspricht

Die interessanten Teile der Wahrscheinlichkeitsmassenfunktionen sehen so aus (Münzwürfe in Rot, Würfelsummen in Blau)

enter image description here

Ich liebe das (und nicht nur, weil ich ein R-Evangelist bin).Schade, dass die Simulationsantworten so viele weitere positive Stimmen erhalten haben.
@CarlWitthoft: Ein Grund, warum die Simulationsantwort mehr positive Stimmen erhält, kann sein, dass sie leichter zu verstehen und zu codieren ist und weniger fehleranfällig.Ich glaube, ich spreche einigermaßen fließend R, aber ich verstehe nicht, was hier passiert.Ich habe immer noch gestimmt.Warum?Da die Ergebnisse mit der Simulation übereinstimmen, bin ich zuversichtlich, dass sie in Ordnung sind.
#2
+15
BruceET
2020-08-26 05:38:02 UTC
view on stackexchange narkive permalink

Eine andere Möglichkeit besteht darin, eine Million Übereinstimmungen zwischen $ X $ span> und $ Y $ span> zu simulieren um $ P (X > Y) = 0,9907 \ pm 0,0002 zu approximieren. $ span> [Simulation in R.]

  set.seed (825)
d = replizieren (10 ^ 6, Summe (Probe (1: 6.100, rep = T)) - rbinom (1.600, .5))
Mittelwert (d > 0)
[1] 0,990736
2 * sd (d > 0) / 1000
[1] 0,0001916057 # aprx 95% Marge des Simulationsfehlers
 

enter image description here

Notizen per @ AntoniParelladas Kommentar:

In R simuliert die Funktion sample (1: 6, 100, rep = T) 100 Würfe eines fairen Würfels; Die Summe davon simuliert $ X $ span>. Auch rbinom ist R-Code zum Simulieren eine binomiale Zufallsvariable; hier ist es $ Y. $ span> Der Unterschied ist $ D = X - Y. $ span> Die Prozedur replizieren erzeugt einen Vektor mit einer Million Differenzen d . Dann ist (d > 0) ein logischer Vektor von einer Million TRUE s und FALSE s, dem Mittelwert von Das ist sein Anteil an TRUE s - unsere Antwort. Zum Schluss die letzte Aussage gibt die Fehlerquote eines 95% -Konfidenzintervalls des Anteils an von TRUE s (unter Verwendung von 2 anstelle von 1,96) als Realitätsprüfung der Genauigkeit der simulierten Antwort. [Mit einer Million Iterationen erwartet man normalerweise 2 oder 3 Dezimalstufen Genauigkeit für Wahrscheinlichkeiten - manchmal mehr für Wahrscheinlichkeiten bisher von 1/2.]

Können Sie den Code erklären?Ich benutze R, daher ist es mir klar, aber ich denke, Ihr Beitrag wäre nützlicher, wenn der Code erklärt würde, sowie die Verwendung des Binomials und die Berechnung des Standardfehlers.
Die normale Annäherung hat runde Zahlen, kann also während eines Interviews möglich sein.Schließlich ist es wahrscheinlich Ihre Methode, die sie sehen möchten.Und Sie haben bereits einen guten Start in Ihre Frage.
An höflich konstruktiven Vorschlägen ist nichts auszusetzen.// Normalerweise bekomme ich die grundlegende Antwort so schnell wie möglich und mache mir dann Sorgen oder mache Ergänzungen als Antwort auf Fragen von OP.(Ganz zu schweigen von Tippfehlern.)
Simulation ist kein Beweis.Dies ist, um alte Rivalitäten auszugraben, eine technische Lösung, keine mathematische Lösung
Eine Frage zum Vorstellungsgespräch versucht normalerweise herauszufinden, wie potenzielle Mitarbeiter Probleme angehen.Der anfängliche Ansatz von OP scheint in Ordnung zu sein.Könnte auch normal ca. erwähnen, wenn Sie nach einer genaueren Lösung gefragt werden.(Auch kein Beweis.) Für einige Arten von Jobs kann es Punkte geben, um zu erwähnen, dass eine Simulation verwendet werden kann, um möglicherweise eine genauere Antwort zu erhalten als bei normalen ca.Das Herumflattern nach einer exakten Ableitung von dist'n von D macht möglicherweise keinen guten Eindruck.// @CarlWitthoft's Kommentar vielleicht besser geeignet auf der 'Mathe'-Seite.Zweifel, dass viele Benutzer hier sim für einen formalen Beweis halten - oder dessen Nützlichkeit in Frage stellen.
@BruceET das OP fragte, wie man * berechnet *, nicht * schätzt *
Wenn das Interview nicht für eine Tenure-Track-Position in der Statistik gedacht war, würde ich sagen, dass eine Simulation, deren Codierung fünf Minuten dauert, nützlicher ist als eine Berechnung, deren Durchführung und Überprüfung drei Stunden dauert.(Und Leute wie ich würden die Berechnung mit genau dieser Art von Simulation immer noch überprüfen.) +1 von mir.
@StephanKolassa Hier ist eine Geschichte (wahr), die mir von einem Tufts-Professor erzählt wurde, als ich in prähistorischen Zeiten einen Codierungs- / Modellierungskurs belegte.Zwei Kollegen versuchten, etwas abzuschätzen, einer durch Berechnung der Ausdehnung und Summierung der analytischen Reihen;die andere mit einem Finite-Elemente-Gittermodell.Riesige Abweichungen bei den Ergebnissen, bis sie feststellten, dass die Serienerweiterung so langsam konvergierte, dass Tausende von Begriffen erforderlich waren.Sie müssen also nachweisen, dass Ihre "Fünf-Minuten-Simulation" eine gültige Annäherung an das reale System ist.
@CarlWitthoft Natürlich müssen Sie nachweisen können, dass die Annäherung gültig ist.Normale Annäherungen an einen Binomialprozess [sind jedoch kein Neuland] (https://en.wikipedia.org/wiki/Binomial_distribution#Normal_approximation).
#3
+14
Robby the Belgian
2020-08-26 05:50:45 UTC
view on stackexchange narkive permalink

Etwas genauer:

Die Varianz einer Summe oder Differenz zweier unabhängiger Zufallsvariablen ist die Summe ihrer Varianzen. Sie haben also eine Verteilung mit einem Mittelwert von $ 50 $ span> und einer Standardabweichung $ \ sqrt {292 + 150} \ ca. 21 $ span>. Wenn wir wissen möchten, wie oft wir erwarten, dass diese Variable unter 0 liegt, können wir versuchen, unsere Differenz durch eine Normalverteilung zu approximieren, und wir müssen den $ z $ nachschlagen span> -score für $ z = \ frac {50} {21} \ ca. 2,38 $ span>. Natürlich wird unsere tatsächliche Verteilung etwas breiter sein (da wir ein Binomial-PDF mit einem PDF mit gleichmäßiger Verteilung falten), aber hoffentlich ist dies nicht zu ungenau. Die Wahrscheinlichkeit, dass unsere Summe positiv ist, liegt gemäß einer $ z $ span> -Ergebnis-Tabelle bei $ 0,992 $ span >.

Ich habe ein schnelles Experiment in Python durchgeführt, bei dem 10000 Iterationen ausgeführt wurden, und ich habe $ \ frac {9923} {10000} $ span> Positive erhalten. Nicht zu weit weg.

Mein Code:

  importiere numpy als np
c = np.random.randint (0, 2, Größe = (10000, 100, 6)). Summe (Achse = -1)
d = np.random.randint (1, 7, Größe = (10000, 100))
(d.sum (Achse = -1) > c.sum (Achse = -1)). sum ()
--> 9923
 
Gut.Sie haben sowohl Simulation als auch normale ca.(+1)
Es könnte eine [Kontinuitätskorrektur] wert sein (https://en.wikipedia.org/wiki/Continuity_correction), also $ \ Phi ^ {- 1} \ left (\ frac {50-0.5} {\ sqrt {292 + 150}} \ right) \ ca. 0.9907256 $, was besser mit der genauen Antwort von $ 0.99079025 $ vergleichbar ist
#4
+2
Ilmari Karonen
2020-08-27 15:05:43 UTC
view on stackexchange narkive permalink

Die genaue Antwort lässt sich leicht numerisch berechnen - keine Simulation erforderlich. Zu Bildungszwecken finden Sie hier ein elementares Python 3-Skript, das keine vorgefertigten statistischen Bibliotheken verwendet.

  aus Sammlungen importieren defaultdict

# Definieren Sie die Verteilungen einer einzelnen Münze und sterben Sie
Münze = Tupel ((i, 1/2) für i in (0, 1))
die = Tupel ((i, 1/6) für i in (1, 2, 3, 4, 5, 6))

# eine einfache Funktion zum Berechnen der Summe zweier Zufallsvariablen
def add_rv (a, b):
  sum = defaultdict (float)
  für i, p in a:
    für j, q in b:
      Summe [i + j] + = p * q
  Rückgabetupel (sum.items ())

# Berechnen Sie die Summe von 600 Münzen und 100 Würfeln
coin_sum = dice_sum = ((0, 1),)
für _ im Bereich (600): coin_sum = add_rv (coin_sum, coin)
für _ im Bereich (100): dice_sum = add_rv (dice_sum, die)

# Berechnen Sie die Wahrscheinlichkeit, dass die Würfelsumme höher ist
prob = 0
für i, p in dice_sum:
  für j, q in coin_sum:
    wenn i > j: prob + = p * q

print ("Wahrscheinlichkeit, dass 100 Würfel zu mehr als 600 Münzen summieren =% .10f"% prob)
 

Probieren Sie es online aus!

Das obige Skript stellt eine diskrete Wahrscheinlichkeitsverteilung als Liste von (Wert-, Wahrscheinlichkeits-) Paaren dar und verwendet ein einfaches Paar verschachtelter Schleifen, um die Verteilung der Summe zweier Zufallsvariablen zu berechnen (Iteration über alle möglichen Werte von jedem von die Summanden). Dies ist nicht unbedingt die effizienteste Darstellung, aber es ist einfach zu bearbeiten und für diesen Zweck mehr als schnell genug.

(FWIW, diese Darstellung von Wahrscheinlichkeitsverteilungen ist auch kompatibel mit der Sammlung von Dienstprogrammfunktionen zum Modellieren komplexerer Würfelwürfe, die ich für einen Beitrag auf unserer Schwesterseite geschrieben habe vor einer Weile.)

Natürlich gibt es auch domänenspezifische Bibliotheken und sogar ganze Programmiersprachen für solche Berechnungen. Mit einem solchen Online-Tool namens AnyDice kann dieselbe Berechnung viel kompakter geschrieben werden:

  X: 100d6
Y: 600d {0,1}
Ausgabe X > Y mit dem Namen "1 wenn X > Y, sonst 0"
 

Unter der Haube glaube ich, dass AnyDice das Ergebnis ziemlich genau wie mein Python-Skript berechnet, außer vielleicht mit etwas mehr Optimierungen.In jedem Fall geben beide die gleiche Wahrscheinlichkeit von 0,9907902497 an, wenn die Summe der Würfel größer als die Anzahl der Köpfe ist

Wenn Sie möchten, kann AnyDice auch die Verteilungen der beiden Summen für Sie zeichnen.Um ähnliche Diagramme aus dem Python-Code zu erhalten, müssen Sie die Listen dice_sum und coin_sum in eine Diagrammdiagrammbibliothek wie pyplot einspeisen.

#5
+2
Silverfish
2020-08-28 14:57:19 UTC
view on stackexchange narkive permalink

Die folgende Antwort ist etwas langweilig, scheint aber die einzige zu sein, die bisher die wirklich genaue Antwort enthält! Normale Approximation oder Simulation oder auch nur das numerische Knacken der genauen Antwort auf ein angemessenes Maß an Genauigkeit, was nicht lange dauert, sind wahrscheinlich der bessere Weg - aber wenn Sie den "mathematischen" Weg suchen, um die genaue Antwort zu erhalten, dann :

Lassen Sie $ X $ span> die Summe der Punkte bezeichnen, die wir in $ 100 $ span> -Würfeln mit Wahrscheinlichkeit sehen Massenfunktion $ p_X (x) $ span>.

Lassen Sie $ Y $ span> die Anzahl der Köpfe in $ 600 $ span> Münzwürfen mit Wahrscheinlichkeitsmassenfunktion bezeichnen $ p_Y (y) $ span>.

Wir suchen $ P (X > Y) = P (X - Y > 0) = P (D > 0) $ span> wobei $ D = X - Y $ span> ist die Differenz zwischen der Summe der Punkte und der Anzahl der Köpfe.

Sei $ Z = -Y $ span> mit der Wahrscheinlichkeitsmassenfunktion $ p_Z (z) = p_Y (-z) $ span>. Dann kann die Differenz $ D = X - Y $ span> als Summe $ D = X + Z $ span umgeschrieben werden > was bedeutet, dass $ X $ span> und $ Z $ span> unabhängig sind, können wir die Wahrscheinlichkeitsmassenfunktion finden von $ D $ span> durch Nehmen der diskreten Faltung der PMFs von $ X $ span > und $ Z $ span>:

$$ p_D (d) = \ Pr (X + Z = d) = \ sum_ {k = - \ infty} ^ {\ infty} \ Pr (X = k \ cap Z = d - k) = \ sum_ {k = - \ infty} ^ {\ infty} p_X (k) p_Z (dk) $$ span>

In der Praxis muss die Summe nur über Werte von $ k $ span> erfolgen, für die die Wahrscheinlichkeiten natürlich ungleich Null sind. Die Idee hier ist genau das, was @IlmariKaronen getan hat. Ich wollte nur die mathematischen Grundlagen dafür aufschreiben.

Jetzt habe ich nicht gesagt, wie man die PMF von $ X $ span> findet, die als Übung übrig bleibt, aber beachte, dass wenn $ X_1, X_2, \ dots, X_ {100} $ span> sind die Anzahl der Punkte auf jedem der 100 unabhängigen Würfelwürfe mit jeweils diskreten einheitlichen PMFs auf $ \ {1, 2, 3, 4, 5, 6 \} $ span>, dann $ X = X_1 + X_2 + \ dots + X_ {100} $ span> und so ...

  # Speichern Sie die PMFs von Variablen als Datenrahmen mit den Spalten "value" und "prob".
# Wichtig, dass die Werte fortlaufend sind und aus Gründen der Konsistenz beim Falten aufsteigen.
# also bei Bedarf Zwischenwerte mit der Wahrscheinlichkeit 0 einschließen!

# Funktion zum Überprüfen, ob der Datenrahmen der obigen Definition von PMF entspricht
# Verwenden Sie message_intro, um zu erklären, welche Prüfung fehlschlägt
is.pmf <- Funktion (x, message_intro = "") {
  if (! is.data.frame (x)) {stop (paste0 (message_intro, "Kein Datenrahmen"))}
  if (! nrow (x) > 0) {stop (paste0 (message_intro, "Dataframe hat keine Zeilen"))}
  if (! "value"% in% colnames (x)) {stop (paste0 (message_intro, "No 'value' column"))}
  if (! "prob"% in% colnames (x)) {stop (paste0 (message_intro, "No 'prob' column"))}
  if (! is.numeric (x  $ value)) {stop (paste0 (message_intro, Spalte '' value 'nicht numerisch ")})
  if (! all (is.finite (x $  span> value))) {stop (paste0 (message_intro, "Enthält 'value' NA, Inf, NaN usw.?")})
  if (! all (diff (x  $ value) == 1)) {stop (paste0 (message_intro, "'value' nicht fortlaufend und aufsteigend")}
  if (! is.numeric (x $  span> prob)) {stop (paste0 (message_intro, "'prob' Spalte nicht numerisch"))}
if (! all (is.finite (x  $ prob))) {stop (paste0 (message_intro, "Enthält 'prob' NA, Inf, NaN usw.?")})
  if (! all.equal (sum (x $  span> prob), 1)) {stop (paste0 (message_intro, Spalte '' prob 'summiert sich nicht zu 1 ")})
  return (TRUE)
}}

# Funktion zum Falten von PMFs von x und y
# Beachten Sie, dass wir den zweiten Vektor umkehren müssen, um uns in R zu falten
# name1 und name2 werden in der Fehlerberichterstattung für die beiden Eingaben verwendet
convolve.pmf <- Funktion (x, y, name1 = "x", name2 = "y") {
  is.pmf (x, message_intro = paste0 ("Prüfen", Name1, "ist gültige PMF:"))
  is.pmf (y, message_intro = paste0 ("Prüfen", Name2, "ist gültige PMF:"))
  x_plus_y <- data.frame (
    value = seq (from = min (x  $ value) + min (y $  span> value),
                to = max (x  $ value) + max (y $  span> value),
                durch = 1),
    prob = convolve (x  $ prob, rev (y $  span> prob), type = "open")
  )
  return (x_plus_y)
}}

# Sei x_i die Punktzahl beim einzelnen Würfelwurf i
# Hinweis Die PMF von x_i ist für jedes i = 1 bis i = 100 gleich.)
x_i <- data.frame (
  Wert = 1: 6,
  prob = rep (1/6, 6)
)

# Sei t_i die Summe von x_1, x_2, ..., x_i
# Wir speichern die PMFs von t_1, t_2 ... in einer Liste
t_i <- list ()
t_i [[1]] <- x_i # t_1 ist nur x_1 und hat dieselbe PMF
# PMF von t_i ist die Faltung von PMFs von t_ (i-1) und x_i
für (i in 2: 100) {
  t_i [[i]] <-convolve.pmf (t_i [[i-1]], x_i,
        name1 = paste0 ("t_i [[", i-1, "]]"), name2 = "x_i")
}}

# Sei x die Summe der Punkte aller 100 unabhängigen Würfelwürfe
x <-t_i [[100]]
is.pmf (x, message_intro = "Überprüfen, ob x gültig ist PMF:")

# Sei y die Anzahl der Köpfe in 600 Münzwürfen, ebenso die Binomialverteilung (600, 0,5):
y <- data.frame (Wert = 0: 600)
y  $ prob <-dbinom (y $  span> -Wert, Größe = 600, Prob = 0,5)
is.pmf (y, message_intro = "Überprüfen, ob y PMF gültig ist:")
# Sei z das Negativ von y (beachte, dass wir die Reihenfolge umkehren, um die Werte aufsteigend zu halten)
z <- data.frame (Wert = -rev (y  $ value), prob = rev (y $  span> prob))
is.pmf (z, message_intro = "Überprüfen, ob z eine gültige PMF ist:")

# Sei d die Differenz, d = x - y = x + z
d <-convolve.pmf (x, z, name1 = "x", name2 = "z")
is.pmf (d, message_intro = "Überprüfen, ob d eine gültige PMF ist:")

# Prob (X > Y) = Prob (D > 0)
Summe (d [d $ Wert > 0, "prob"])
# [1] 0,9907902
 

Probieren Sie es online aus!

Nicht, dass es praktisch wichtig wäre, wenn Sie nur nach angemessener Genauigkeit suchen, da der obige Code ohnehin in Sekundenbruchteilen ausgeführt wird, aber es gibt eine Verknüpfung, um die Faltungen für die Summe von 100 unabhängigen, identisch verteilten Variablen durchzuführen: seit 100 = 64 + 32 + 4, ausgedrückt als Summe der Potenzen von 2, können Sie Ihre Zwischenantworten so weit wie möglich mit sich selbst verknüpfen. Schreiben der Zwischensummen für den ersten $ i $ span> Würfelwurf als $ T_i = \ sum_ {k = 1} ^ {k = i} X_k $ span> können wir die PMFs von $ T_2 = X_1 + X_2 $ span>, $ T_4 = T_2 erhalten + T_2 '$ span> (wobei $ T_2' $ span> unabhängig von $ T_2 $ span> ist, aber hat die gleiche PMF) und in ähnlicher Weise $ T_8 = T_4 + T_4 '$ span>, $ T_ {16} = T_8 + T_8' $ span>, $ T_ {32} = T_ {16} + T_ {16} '$ span> und $ T_ {64} = T_ {32} + T_ {32} '$ span>. Wir brauchen zwei weitere Windungen, um die Gesamtpunktzahl aller 100 Würfel als Summe von drei unabhängigen Variablen zu ermitteln: $ X = T_ {100} = (T_ {64} + T_ {32} '') + T_4 '' $ span> und eine endgültige Faltung für $ D = X + Z $ span>. Ich denke, Sie brauchen insgesamt nur neun Faltungen - und für die letzte können Sie sich einfach auf die Teile der Faltung beschränken, die einen positiven Wert für $ D $ span> ergeben . Oder wenn es weniger mühsam ist, die Teile, die die nicht positiven Werte für $ D $ span> angeben, und nehmen dann das Komplement. Vorausgesetzt, Sie wählen den effizientesten Weg, bedeutet dies meiner Meinung nach, dass Ihr schlimmster Fall effektiv achteinhalb Windungen sind. EDIT: und wie @whuber vorschlägt, ist dies auch nicht unbedingt optimal!

Verwenden der von mir identifizierten Neun-Faltungs-Methode mit dem gmp-Paket, damit ich mit bigq -Objekten arbeiten und eine überhaupt nicht optimierte Schleife schreiben kann Bei den Windungen (da die integrierte Methode von R keine bigq -Eingaben verarbeitet) dauerte es nur ein paar Sekunden, um den genauen vereinfachten Bruch zu ermitteln:

1342994286789364913259466589226414913145071640552263974478047652925028002001448330257335942966819418087658458889485712017471984746983053946540181650207455490497876104509955761041797420425037042000821811370562452822223052224332163891926447848261758144860052289/1355477899826721990460331878897812400287035152117007099242967137806414779868504848322476153909567683818236244909105993544861767898849017476783551366983047536680132501682168520276732248143444078295080865383592365060506205489222306287318639217916612944423026688

was tatsächlich auf 0,9907902 rundet. Für die genaue Antwort hätte ich das nicht mit zu vielen weiteren Windungen machen wollen, ich konnte fühlen, wie die Zahnräder meines Laptops anfingen zu knarren!

Obwohl es intuitiv offensichtlich ist, dass solche binären Zerlegungen zu Effizienzgewinnen führen, kann es Sie interessieren, dass sie nicht unbedingt die effizienteste Methode erzeugen.Ein kleines Beispiel ist 15 = 1111B = 1 + 2 + 4 + 8.Nach der binären Zerlegung können wir Faltungen der Ordnung 2 = 1 + 1, 4 = 2 + 2, 8 = 4 + 4 und dann 15 = 1 + 2 + 4 + 8 berechnen, was 6 Operationen erfordert;Dies kann jedoch in nur 5 Operationen erreicht werden, indem 2, 4, 5 = 1 + 4, 10 = 5 + 5, 15 = 5 + 10 berechnet werden.Ich erinnere mich, dass Donald Knuth dieses Problem in * Art of Computer Programming * bespricht. Https://stats.stackexchange.com/questions/5347 ist eng verwandt.
Zu dem Code: Vor einigen Jahren fand ich es praktisch, denselben Ansatz zu wählen, indem ich die grundlegenden arithmetischen Operatoren überlastete: https://stats.stackexchange.com/a/116913/919.
@whuber Schön!Ich glaube, ich war von so einem Code inspiriert, den ich tatsächlich woanders gesehen hatte, entweder von Ihnen oder möglicherweise von Wölfen.Der effizienteste Weg, um die Windungen zu machen: wirklich interessant!Es war bemerkenswert, wie viel langsamer die endgültigen Windungen waren, was mich fragt, ob es einen Unterschied zwischen der Minimierung der Anzahl der Windungen und (noch besser) der Minimierung der Anzahl der Operationen gibt.Ich denke, das Falten von Vektoren der Längen $ m $ und $ n $ erfordert $ mn $ Multiplikationen und $ mn-m-n + 1 $ Additionen (Berechnungen mit gemeinsamen Nennern für die genauen Brüche werden nicht vernachlässigbar billig sein) ...
... Es sieht so aus, als ob großes $ mn $ das Problem ist. Das Ziel ist es, das Produkt klein zu halten und gleichzeitig die Summe schnell aufzubauen.(Die Summe von $ k $ Würfeln kann von $ k $ bis $ 6k $ reichen, daher muss der Vektor für seine PMF $ m = 5k + 1 $ Wahrscheinlichkeiten enthalten. Daher wird die Summe $ m + n $Seien Sie nahezu proportional zur Summe der Würfelzahlen, die Sie auf 100 aufbauen möchten.) 1 + 9 zu machen ist eine einfachere Methode, um 10 zu machen, als beispielsweise 5 + 5 - besser, um die Summe "schief" zu halten".Was darauf hindeutet, dass mein "Verdoppelungs" -Ansatz vielleicht doch keine so kluge Idee war!
(Und mehr noch als Hinweis für sich selbst: Mit den "großen Rationalen" hätte ich vermutlich viel Zeit sparen können, wenn ich nur die Zähler als "große ganze Zahlen" gespeichert und einen gemeinsamen Nenner für jeden Vektor von Wahrscheinlichkeiten verfolgt hätte ...)
Während eines Prozesses aufeinanderfolgender Windungen arbeiten Sie direkt mit den Fourier-Transformationen.Somit erfordert jede Faltung $ \ max (m, n) $ Multiplikationen und keine Additionen.Eine Lösung, die ich befürwortet habe, besteht darin, zu Beginn Näherungswerte zu verwenden, um den Bereich der Endwerte zu schätzen, die sinnvolle Wahrscheinlichkeiten ungleich Null haben, und dann alle Berechnungen auf Werte zu beschränken, die für diesen Endbereich relevant sind: Dies legt eine Obergrenze für die Größe von $ \ max (m, n) $ wird sein.Weitere Informationen finden Sie unter https://stats.stackexchange.com/a/5482/919 und unter https://stats.stackexchange.com/a/291571/919 für weitere Informationen.
@whuber Ja, im Idealfall würde ich FFT verwenden - mein Kommentar galt nur für die "Big Rationals" -Berechnung, die ich verwendet habe, um die * genaue * Antwort zu erhalten, also leider keine Annäherungen für mich, und soweit ich das R-Paket für `sagen kanngmp` unterstützt keine Convolutions / FFT für `bigq`-Objekte :-( Für" praktischere "Zwecke sind die in Ihren Posts angegebenen Annäherungen sehr praktisch!


Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 4.0-Lizenz, unter der er vertrieben wird.
Loading...