Mein lokales ACM-Kapitel verteilt Türpreise an Leute, die zu den Meetings kommen. Sie haben jedoch eine erhöhte Gewinnchance, wenn Sie das Programmierpuzzle lösen (aber ich löse das Puzzle immer). So haben einige Leute 1 Eintrag, während andere 2 haben. Aber warte! Die Art und Weise, wie das Gewinnspiel funktioniert, besteht nicht darin, einen anderen Eintrag hinzuzufügen, wenn jemand das Rätsel löst. Stattdessen wird die Anzahl der "Leben" einer Person protokolliert, wobei dekrementiert wird, ob diese Person in jedem Durchgang ihres Zufallsstichprobenalgorithmus ausgewählt wird. So funktioniert es also:

Doorknob: 1.  xnor: 2.  Justin: 2.  Alex: 1.  Dennis: 2.

Dann wählt das Programm nach dem Zufallsprinzip eine der folgenden [Doorknob, xnor, Justin, Alex, Dennis]Optionen, dekrementiert die Zahl (sagt, es wählt Justin):

Doorknob: 1.  xnor: 2.  Justin: 1.  Alex: 1. Dennis: 2.

Und wiederholt. Wenn die Anzahl der "Leben" von jemandem auf "geht" 0( Justinerneut auswählen ), werden sie aus der Liste entfernt:

Doorknob: 1.  xnor: 2.  Alex: 1.  Dennis: 2.

Dies geht so lange weiter, bis eine Person übrig ist. Diese Person ist der Gewinner.

Die eigentliche Frage ist nun, mit welcher Wahrscheinlichkeit ich gewonnen hätte.

Sie erhalten zwei Eingaben:

• n. Dies ist die Anzahl der Personen, die an der Herausforderung teilgenommen haben
• k. Dies ist die Anzahl der Personen (von denen n), die 2 Leben haben. Diese Nummer enthält immer Sie.

Wenn ich also eine Funktion hätte pund anrufe p(10, 5), wäre das die Wahrscheinlichkeit, den Preis zu gewinnen, wenn insgesamt 10 Personen anwesend sind, von denen 5 nur 1 Leben haben, während 5 (einschließlich Sie) 2 Leben haben.

Es wird erwartet, dass Sie die Gewinnwahrscheinlichkeit entweder genau oder als Dezimalzahl ausgeben. Auf jeden Fall Antworten müssen genau bis zu und einschließlich der 4 - ^te Dezimalstelle hinter dem Komma. Es liegt an Ihnen, ob Sie auf diese Ziffer runden oder nicht.

Ihre Lösung kann eine randomisierte Lösung sein , die gibt die Antwort auf die 4 - ^te Dezimalstelle mit hohen Wahrscheinlichkeit . Sie können davon ausgehen, dass das von Ihnen verwendete integrierte RNG wirklich zufällig ist und die richtige Antwort mit einer Wahrscheinlichkeit von mindestens 90% ausgegeben werden muss.

Außerdem muss Ihr Code nur für funktionieren n, k <= 1000, obwohl ich Testfälle bereitgestellt habe, die für Neugierige größer sind.

Testfälle

Hinweis: Einige davon sind allgemeine Formeln.

n,    k   |  output
----------+---------
1,    1   |  1
2,    2   |  0.5
2,    1   |  0.75
3,    1   |  11/18 = 0.611111111
1000, 1   |  0.007485470860550352
4,    3   |  0.3052662037037037
k,    k   |  1/k
n,    1   |  (EulerGamma + PolyGamma[1 + n])/n    (* Mathematica code *)
          |  (γ + ψ(1 + n))/n
10,   6   |  0.14424629234373537
300,  100 |  0.007871966408910648
500,  200 |  0.004218184180294532
1000, 500 |  0.0018008560286627948
---------------------------------- Extra (not needed to be a valid answer)
5000, 601 |  0.0009518052922680399
5000, 901 |  0.0007632938197806958

Für weitere Überprüfungen p(n, 1) * nwie folgt vorgehen:

n     |  output
------+---------
1     | 1
2     | 1.5 
3     | 1.8333333333333335
10    | 2.928968253968254
100   | 5.1873775176396215
-------------------------- Extra (not needed to be a valid answer)
100000| 12.090146129863305

MATL , 42 Bytes

:<~QXJx`J`tf1Zry0*1b(-tzq]f1=vts3e8<]6L)Ym

Hierbei wird ein probabilistischer Ansatz (Monte Carlo) verwendet. Das Experiment wird eine große Anzahl von Malen ausgeführt, aus denen die Wahrscheinlichkeit geschätzt wird. Die Anzahl der Realisierungen wird bis ausgewählt sicherzustellen , dass das Ergebnis auf die vierte Dezimalstelle mit einer Wahrscheinlichkeit von mindestens 90% richtig abgelaufen ist. Dies benötigt jedoch sehr viel Zeit und Speicher. Im folgenden Link wurde die Anzahl der Realisierungen um den Faktor 10 ⁶ verringert , damit das Programm in angemessener Zeit endet. und nur der erste Dezimalstelle ist mit einer Wahrscheinlichkeit von mindestens 90% garantiert genau.

EDIT (29. Juli 2016): muss aufgrund von Sprachänderungen 6Ldurch ersetzt werden 3L. Der unten stehende Link enthält diese Änderung.

Probieren Sie es online!

Hintergrund

Sei p die zu berechnende Wahrscheinlichkeit. Das in der Challenge beschriebene Experiment wird n- mal wiederholt. Jedes Mal gewinnen Sie entweder den Preis (" Erfolg ") oder nicht. Sei N die Anzahl der Erfolge. Die gewünschte Wahrscheinlichkeit kann aus N und n geschätzt werden . Je größer n ist, desto genauer wird die Schätzung sein. Die Schlüsselfrage ist, wie man auswählt n , um die gewünschte Genauigkeit zu erreichen, nämlich um sicherzustellen, dass mindestens 90% der Fehler kleiner als 10 ^{-4 sind} .

Monte-Carlo-Methoden können sein

• Feste Größe : ein Wert von n wird im Voraus festgelegt (und dann N zufällig);
• Variable Größe : n wird im Handumdrehen durch die Simulationsergebnisse bestimmt.

Unter der zweiten Kategorie besteht eine häufig verwendete Methode darin, N (gewünschte Anzahl von Erfolgen) festzulegen und weiter zu simulieren, bis diese Anzahl von Erfolgen erreicht ist . Somit n ist zufällig. Diese Technik wird als inverse Binomialabtastung oder negativ-binomiales Monte Carlo bezeichnet , hat den Vorteil, dass die Genauigkeit des Schätzers begrenzt werden kann. Aus diesem Grund wird es hier verwendet.

Insbesondere ist mit negativem Binom Monte Carlo x = ( N - 1) / ( n - 1) ein unverzerrter Schätzer von p ; und die Wahrscheinlichkeit, dass x um mehr als ein gegebenes Verhältnis von p abweicht, kann nach oben begrenzt werden. Gemäß Gleichung (1) in dieser Arbeit (beachten Sie auch, dass die Bedingungen (2) erfüllt sind), stellt die Annahme von N = 2,75 · 10 ⁸ oder größer sicher, dass p / x mit mindestens 90% zum Intervall [1.0001, 0.9999] gehört. Wahrscheinlichkeit. Dies impliziert insbesondere, dass x mit einer Wahrscheinlichkeit von mindestens 90% bis zur 4. Dezimalstelle korrekt ist, wie gewünscht.

Code erklärt

Der Code verwendet N = 3e8, um ein Byte zu speichern. Beachten Sie, dass dies bei vielen Simulationen sehr lange dauern würde. Der Code im Link verwendet N = 300, was in einer angemesseneren Zeitspanne ausgeführt wird (weniger als 1 Minute im Online-Compiler für die ersten Testfälle). Dies stellt jedoch nur sicher, dass die erste Dezimalstelle mit einer Wahrscheinlichkeit von mindestens 90% korrekt ist.

:        % Take k implicitly. Range [1 ... k]
<~       % Take n implicitly. Determine if each element in the previous array is
         % less than or equal than n
Q        % Add 1. This gives an array [2 ... 2 1 ... 1]
XJx      % Copy to clipboard J. Delete from stack
`        % Do...while. Each iteration is a Monte Carlo realization, until the 
         % desired nunber of successes is reached
  J      %   Push previously computed array [2 ... 2 1 ... 1]
  `      %   Do...while. Each iteration picks one door and decrements it, until
         %   there is only one
    t    %     Duplicate
    f    %     Indices of non-zero elements of array
    1Zr  %     Choose one of them randomly with uniform distribution
    y0*  %     Copy of array with all values set to 0
    1b(  %     Assign 1 to chosen index
    -    %     Subtract
    tzq  %     Duplicate. Number of nonzero elements minus 1. This is falsy if
         %     there was only one nonzero value; in this case the loop is exited
  ]      %   End do...while
  f1=    %   Index of chosen door. True if it was 1 (success), 0 otherwise
  v      %   Concatenate vertically to results from previous realizations
  ts3e8< %   Duplicate. Is the sum less than 3e8? If so, the loop is exited
]        % End do...while
6L)      % Remove last value (which is always 1)
Ym       % Compute mean. This gives (N-1)/(n-1). Implicitly display

Pyth, 34 Bytes

Mc|!*HJ-GHch*J+*tHgGtH*gtGHKh-GHKG

Testsuite

Definiert eine deterministisch gespeicherte rekursive Funktion gmit n , k als Argumente verwendet. g 1000 500kehrt 0.0018008560286627952in ungefähr 18 Sekunden zurück (nicht in der obigen Testsuite enthalten, da der Online-Interpreter abläuft).

Eine ungefähre Python 3-Übersetzung wäre

@memoized
def g(n,k):
    return (not k*(n-k) or (1+(n-k)*((k-1)*g(n,k-1)+g(n-1,k)*(n-k+1)))/(n-k+1))/n

JavaScript (ES6), 65 Byte

f=(n,k,d=n-k)=>(!d||(f(n-1,k)*++d*--d+1+(--k&&f(n,k)*k*d))/++d)/n

Versuchen Sie es nicht mit den großen Zahlen; Sogar f (30, 10) nimmt eine merkliche Zeit in Anspruch.