Ich versuche eine Funktion zu schreiben, die bei jedem Aufruf Wahr oder Falsch zurückgibt, aber mit einer bekannten Häufigkeit, sagen wir 60% der Zeit ist es wahr, die anderen 40% sind falsch. Mit dieser Funktion soll ich eine andere Funktion erstellen, die 50% der Zeit zurückgibt.
Mein erster Ansatz bestand darin, die Zufallsfunktion zu verwenden und wahr zurückzugeben, wenn sie unter 0,6 ist, falsch, wenn sie vorbei ist. Nicht sicher, wie man den zweiten Teil damit anspricht.
Nehmen wir den allgemeinen Fall: Sie haben eine Funktion F1 () erstellt, die Wahr mit Wahrscheinlichkeit P (in Ihrem Fall P = 60%) zurückgibt. Jetzt bauen Sie die zweite Funktion auf diese Weise:
%Vor%In diesem Fall ist die Wahrscheinlichkeit, dass F1 zweimal ausgeführt wird und (True, False) erhalten wird, dasselbe wie das Erhalten von (False, True) und es ist P * (1-P). Wenn Sie entweder (True, True) oder (False, False) erhalten, rufen Sie F2 rekursiv auf. Das bedeutet, dass Sie nach dem Ausführen von F2 immer Wahr oder Falsch mit der Wahrscheinlichkeit 1/2 erhalten, da die ersten beiden Zweige die gleichen Wahrscheinlichkeiten haben, und das dritte ergibt immer das Ergebnis einer Funktion mit der Wahrscheinlichkeit 1/2.
Ich mache dies zu einem Community-Wiki, falls jemand meine Antwort deutlicher machen möchte. Mir ist klar, dass es etwas schwierig sein könnte, das Konzept zu erklären.
Die durchschnittliche Anzahl der Anrufe
Die Wahrscheinlichkeit, dass die Funktion F2 () unmittelbar nach n rekursiven Aufrufen endet, lautet:
{(1-P) ^ 2 + P ^ 2} ^ n * 2P (1-P)
Daher ist die durchschnittliche Anzahl der erforderlichen rekursiven Aufrufe:
\ Summe_ {i = 0} ^ \ infty i * {(1-P) ^ 2 + P ^ 2} ^ i * 2P (1-P)
Okay, wir haben also eine Funktion, die einen Wahr-Wert mit p = 0.60 und einen Falschen Wert mit p = 0.40 erzeugt. Angenommen, wir führen diese Funktion eine Sekunde lang aus. Wie groß ist die Wahrscheinlichkeit, dass die Ergebnisse übereinstimmen?
also F_1 == wahr und F_2 == wahr passiert mit p (0.60 * 0.60) = 0.36
und F_1 == false und F_2 == false passiert mit p (0.40 * 0.40) = 0.16
und F_1! = F_2 passiert mit p (0.6 * 0.4 + 0.6 * 0.4) = 0.48
das gibt Ihnen eine Funktion mit Renditen, die 0,52 Prozent der Zeit ausmachen, was nicht ganz das ist, wonach wir suchen, aber interessant ist.
Eine sehr einfache Lösung wäre zu sagen: Wenn ich 60% der Zeit wahr habe, dann wie viel Prozent der Zeit (welche Wahrscheinlichkeit) sollte ich diesen Wert auf falsch ändern, um 50% der Zeit wahr zu sein .
Das ist alles, was ich sagen werde, weil das Hausaufgaben sind.
Ansatz:
Sie führen Ihre 40/60-Funktion aus, bis Sie das Ergebnis mit 40% Wahrscheinlichkeit erhalten. Sobald dies passiert, berechnen Sie das Ergebnis.
0,5 wird auf diese Weise berechnet.
0,5 = 0,6 - 0,6 ^ 2 + 0,6 ^ 3 + 0,6 ^ 4 - 0,6 ^ 5 - 0,6 ^ 6 + 0,6 ^ 7 + 0,6 ^ 8 - 0,6 ^ 9 + ....
(Wenn das aktuelle Ergebnis mehr als 0,5 ist, addieren Sie andernfalls subtrahieren)
Sobald Sie 0.4 erreicht haben, berechnen Sie das Ergebnis dieser Funktion. Wenn es & gt; 0.5 Sie geben wahr zurück, sonst geben Sie false zurück.
hey wie wäre es mit diesem Ansatz: Wir wissen, dass F1 () 10 mal aufgerufen wird: 6 mal wird es wahr und 4 mal falsch zurückgegeben
Also können wir in F2 () einen Zähler haben, der zu 5 zählt. Mit jedem Aufruf von F1 () erhöhen wir den Zähler. F2 () gibt zurück, was F1 () zurückgibt. Wenn der Zähler 5 erreicht, gibt F2 () "false" zurück und initialisiert den Zähler neu. Was sagst du?
Tags und Links algorithm