C-Puzzle: Machen Sie eine faire Münze aus einer voreingenommenen Münze

Lesezeit: 9 Minuten

Benutzer-Avatar
garima

Wie kann ich die Wahrscheinlichkeit bestimmen, dass eine Funktion im folgenden Fall 0 oder 1 zurückgeben würde:

Lasst den function_A gibt 0 mit einer Wahrscheinlichkeit von 40 % und 1 mit einer Wahrscheinlichkeit von 60 % zurück. Erzeuge ein function_B mit Wahrscheinlichkeiten 50-50 nur mit function_A
nur.

Ich dachte an Folgendes:

 function_B()
 {
     int result1=function_A();
     int result2=function_A();
     //two times 40% would result in 16% and 40%+60% would be 24%... two times 60%                        would be 36%
 }

Welche Kombination könnte 50-50 ergeben?

  • Ist das eine Hausaufgabe? Ich möchte nicht einfach rausgehen und Ihnen die Antwort sagen, wenn Sie das für einen Auftrag tun sollen.

    – Vorlagentypdef

    25. März 2011 um 6:01 Uhr

  • Nein, keine Hausaufgaben … Ich kann mit zwei Funktionsaufrufen keine Antwort finden.

    – garima

    25. März 2011 um 6:06 Uhr

Dies ist ein klassisches Wahrscheinlichkeitsrätsel, und meines Wissens können Sie dies nicht mit nur zwei Aufrufen der Funktion tun. Sie können dies jedoch mit einem Tief tun erwartet Anzahl der Aufrufe der Funktion.

Die Beobachtung ist, dass, wenn Sie eine voreingenommene Münze haben, die mit Wahrscheinlichkeit p auf Kopf kommt, und wenn Sie die Münze zweimal werfen, dann:

  • Die Wahrscheinlichkeit, dass zweimal Kopf fällt, ist p2
  • Die Wahrscheinlichkeit, dass zuerst Kopf und dann Zahl kommt, ist p(1-p)
  • Die Wahrscheinlichkeit, dass zuerst Zahl und dann Kopf kommt, ist (1-p)p
  • Die Wahrscheinlichkeit, dass es zweimal Zahl gibt, ist (1-p)2

Nehmen wir nun an, Sie werfen wiederholt zwei Münzen, bis sie unterschiedliche Werte haben. Wie groß ist in diesem Fall die Wahrscheinlichkeit, dass die erste Münze Kopf zeigte? Nun, wenn wir das Gesetz von Bayes anwenden, bekommen wir das

P(erste Münze ist Kopf | beide Münzen sind unterschiedlich) = P(beide Münzen sind unterschiedlich | erste Münze ist Kopf) P(erste Münze ist Kopf) / P(beide Münzen sind unterschiedlich)

Die Wahrscheinlichkeit, dass die erste Münze Kopf ist, ist p, da jeder Münzwurf mit Wahrscheinlichkeit p Kopf ergibt. Die Wahrscheinlichkeit, dass beide Münzen unterschiedlich sind, vorausgesetzt, dass die erste Münze Kopf ist, ist die Wahrscheinlichkeit, dass die zweite Münze Zahl war, also (1 – p). Schließlich ist die Wahrscheinlichkeit, dass beide Münzen unterschiedlich sind, 2p(1-p), denn wenn Sie sich die Wahrscheinlichkeitstabelle oben ansehen, gibt es zwei Möglichkeiten, wie dies passieren kann, von denen jede die Wahrscheinlichkeit p(1-p) hat. Vereinfacht verstehen wir das

P(erste Münze ist Kopf | beide Münzen sind unterschiedlich) = p (1-p) / (2p(1-p)) = 1 / 2.

Aber das ist die Wahrscheinlichkeit, dass die erste Münze Zahl zeigt, wenn die Münzen unterschiedlich sind? Nun, das ist dasselbe wie die Wahrscheinlichkeit, dass die erste Münze nicht Kopf zeigte, wenn beide Münzen unterschiedlich sind, also 1 – 1/2 = 1/2.

Mit anderen Worten, wenn Sie zwei Münzen werfen, bis sie unterschiedliche Werte haben, und dann den Wert der ersten Münze nehmen, die Sie geworfen haben, machen Sie am Ende eine faire Münze aus einer voreingenommenen Münze!

In C könnte das so aussehen:

bool FairCoinFromBiasedCoin() {
    bool coin1, coin2;

    do {
        coin1 = function_A();
        coin2 = function_A();
    } while (coin1 == coin2);

    return coin1;
}

Das mag erbärmlich ineffizient erscheinen, aber es ist eigentlich nicht so schlimm. Die Wahrscheinlichkeit, dass es bei jeder Iteration terminiert, ist 2p(1 – p). Erwartungsgemäß bedeutet dies, dass wir 1/(2p(1-p)) Iterationen benötigen, bevor diese Schleife beendet wird. Für p = 40 % ist dies 1/(2 x 0,4 x 0,6) = 1/0,48 ~= 2,083 Iterationen. Jede Iteration wirft zwei Münzen, also brauchen wir erwartungsgemäß etwa 4,16 Münzwürfe, um einen fairen Wurf zu bekommen.

Hoffe das hilft!

  • das verdient das nette Antwortabzeichen. +1

    – sehen

    22. September 2011 um 8:19 Uhr


  • Sie können es tatsächlich besser machen, aber das Codieren wird ein bisschen chaotisch. Die Idee ist, dass, wenn die Sequenzen HHTT und TTHH die gleiche Wahrscheinlichkeit des Auftretens haben (wobei H Kopf und T Zahl ist). Sie können sogar längere Sequenzen verwenden. Für Interessierte, dieses Papier ist eine großartige Lektüre.

    – FelixCQ

    23. September 2011 um 8:53 Uhr

  • @FelixCQ Ich erhalte eine Fehlermeldung You don't have permission to access /~libcs124/CS/coinflip3.pdf on this server. Gibt es einen anderen Link, den Sie teilen können?

    – Aseem Goyal

    5. Dezember 2013 um 18:10 Uhr

  • @ac_c0der, hier ist ein weiterer Link zum gleichen Papier. Dem Namen nach sollte man es jedenfalls finden: „Tossing a Biased Coin“ von Michael Mitzenmacher.

    – FelixCQ

    27. Dezember 2013 um 23:24 Uhr

  • @RafayKhan Sie können sich die Anzahl der Würfe vorstellen, bevor Sie Köpfe auf einer Münze mit der Wahrscheinlichkeit q bekommen, Köpfe als a zu bekommen geometrische Zufallsvariable mit Parameter q. Sehen Sie sich den Abschnitt über Momente an, um zu beweisen, dass der erwartete Wert dieser Variablen 1/q ist.

    – Vorlagentypdef

    29. September 2019 um 20:33 Uhr

Benutzer-Avatar
Shamim Hafiz – MSFT

Hier ist ein Ansatz, der funktioniert, aber wiederholte Versuche erfordert.

  1. die Chance das function_A gibt 1 zurück: P(1) = p (z. B. p=60%)
  2. die Chance das function_A gibt 0 zurück: P(0) = 1 – p
  3. die Chance auf eine bestimmte Folge von Rückgabewerten a,b,… bei aufeinanderfolgenden Aufrufen von to function_A ist P(a)P(b)
  4. beobachten bestimmte Kombinationen ergeben sich mit gleichen Quoten, z. B.:

          P(a)*P(b) === P(b)*P(a)
     P(a)*P(b)*P(c) === P(b)*P(c)*P(a)
    
     etc.
    
  5. Wir können diese Tatsache nutzen, wenn wir nur Folgen von (1,0) oder (0,1) auswählen, wir kennen dann die Chance von beiden ist

        P(1)*P(0)/(P(1)*P(0) + P(0)*P(1)) 
     => x / (x + x)
     => 1 / 2
    

Dies wird dann zum Rezept für die Implementierung einer Funktion_B:

  • Anruf function_A wiederholt, bis wir eine Folge von (0,1) oder (1,0) erhalten
  • wir geben konsequent entweder das erste oder das letzte Element der Sequenz zurück (beide haben die gleiche Wahrscheinlichkeit, 0 oder 1 zu sein)

function_B()
{
    do
    {
        int a = function_A();
        int b = function_A();
    } while( (a ^ b) == 0 ); // until a != b

    return a;
}

  • @MAK: Die Idee ist, die Wahrscheinlichkeit zu haben, dass 0 und 1 gleich sind. Wenn Sie beobachten, wenn die Funktion einen Wert zurückgibt, gibt es 50-50 auf dem Wert, um eine 0 oder 1 zu sein.

    – Shamim Hafiz – MSFT

    25. März 2011 um 6:16 Uhr

  • @Shamim: “wenn du beobachtest…” – egal ob (das ist nicht Schrödingers Katze). Ich denke, Sie meinten wahrscheinlich “Ich weiß nicht, wie ich es erklären soll, Sie finden es einfach heraus” 🙂

    – sehen

    22. September 2011 um 8:24 Uhr

  • @sehe: Gut, ich kann es erklären, aber es wäre zu voll für das Kommentarfeld :). Eigentlich ist der Satz, den ich verwendet habe, ein Klischee, einige Lehrbücher erklären Antworten in dieser Art von Sprache.

    – Shamim Hafiz – MSFT

    23. September 2011 um 6:47 Uhr

  • @Shamim: Ich habe mich halb über das Fehlen (oder die Schlamperei?) der Erklärung lustig gemacht (a) SO ist kein Lehrbuch (b) Lehrbuchgebrauch beobachten Schritte des deduktiven Denkens zu begleiten – man meist eben empfohlen dass es einige logische Schritte gibt (c) Ich habe etwas Platz in Ihrem Antwortfeld gefunden, um Dinge zu beheben. (Tipp: abgeschnittene Kommentare sind nicht der richtige Ort; idem für Kommentarfelder)

    – sehen

    23. September 2011 um 8:13 Uhr


  • @sehe: Hm. Danke für die zusätzlichen Erklärungen und Ratschläge 🙂

    – Shamim Hafiz – MSFT

    23. September 2011 um 9:38 Uhr

Benutzer-Avatar
JoelP

Gegeben:

  1. Ereignisse = {Kopf, Schwanz}
  2. die Münze ist unfair => P(head) = p und P(tail) = 1-p

Algorithmus:

  1. Generieren Sie eine Stichprobe von N1-Ereignissen (Kopf oder Zahl) mit der unfairen Münze
  2. Schätzen Sie den Stichprobenmittelwert m1 = (#heads)/N1
  3. Generieren Sie eine weitere Stichprobe von N2-Ereignissen (Kopf oder Zahl) mit den unfairen Münzen
  4. Schätzen Sie den Stichprobenmittelwert m2 = (#heads)/N2
  5. Wenn (m1 > m2) Kopf zurückgeben sonst Schwanz zurückgeben

Anmerkungen:

  1. Die in Schritt 5 oben zurückgegebenen Ereignisse sind gleich wahrscheinlich (P(head) = P(tail) = 0,5)
  2. Wenn #5 viele Male wiederholt wird, dann ist sein Stichprobenmittelwert –> 0,5, unabhängig von p
  3. Wenn N1 –> unendlich, dann m1 –> true mean p
  4. Um eine faire Münzausgabe zu erzeugen, benötigen Sie viele unabhängige Stichproben (hier Würfe) der unfairen Münze. Je mehr desto besser.

Intuition: Obwohl die Münze unfair ist, ist die Abweichung des geschätzten Mittelwerts um den wahren Mittelwert zufällig und könnte mit gleicher Wahrscheinlichkeit positiv oder negativ sein. Da der wahre Mittelwert nicht angegeben ist, wird dieser aus einer anderen Stichprobe geschätzt.

Machbar. 2 Aufrufe dieser Funktionen reichen jedoch nicht aus. Stellen Sie sich vor, Sie rufen die Funktion immer und immer wieder auf und kommen immer näher an 50/50 heran

Ich fragte mich, ob etwas Rekursives funktionieren sollte, mit zunehmender Tiefe sollte die Chance für 0 oder 1 immer näher an 0,5 liegen. Auf Stufe 1 beträgt die modifizierte Chance p’=p*p+(p-1)*(p-1)

depth = 10;
int coin(depth) {
    if (depth == 0) {
        return function_A();
    }
    p1 = coin(depth-1);
    p2 = coin(depth-1);
    if (p1 == p2) {
        return 1;
    } else {
        return 0;
    }
}

h for head, t for tail and p() for probability of.

Lets suppose the following:
    p(h) = 0.6
    p

Lets define an event => Event: Flip the coin twice (flip1 , flip2) 

Flipping the coin twice could produce the following results
=> {h, h} , {t, t}, {h, t}, {t, h}

Here are the different probabilities for each event

{h, h} = 0.6 * 0.6 = 0.18
{t, t} = 0.4 * 0.4 = 0.12
{h, t} = 0.6 * 0.4 = 0.24
{t, h} = 0.4 * 0.6 = 0.24

Wie wir sehen können, die Wahrscheinlichkeiten des Habens {h, t} und {t, h} sind gleich. Wir können uns darauf stützen, um ein gleichwahrscheinliches Ergebnis zu erzielen, dafür können wir unser Ereignis so lange auslösen, bis es zurückkehrt {h, t} oder {t, h}. An diesem Punkt geben wir den ersten Versuch des Ereignisses zurück (vorausgesetzt, dass das Ereignis zwei Flips enthält).

Hier ist eine schnelle rekursive Implementierung der Lösung

def unfair_foo():
      # Some code here to produce unfair result
 
def fair_foo():
    flip_1, flip_2 = unfair_foo(), unfair_foo()
 
    if flip_1  flip_2:
      # Base case
      return flip1

     return  fair_foo()  # Recursive call

Benutzer-Avatar
Benutzer3107673

def fairCoin(biasedCoin):
coin1, coin2 = 0,0
while coin1 == coin2:
coin1, coin2 = biasedCoin(), biasedCoin()
return coin1

Das ist ursprünglich eine clevere Idee von von Neumann. Wenn wir eine voreingenommene Münze haben (dh eine Münze, die Kopf mit einer anderen Wahrscheinlichkeit als 1/2 ergibt), können wir eine faire Münze simulieren, indem wir Paare von Münzen werfen, bis die beiden Ergebnisse unterschiedlich sind. Da wir unterschiedliche Ergebnisse haben, ist die Wahrscheinlichkeit, dass das erste „Kopf“ und das zweite „Zahl“ ist, die gleiche wie die Wahrscheinlichkeit von „Zahl“ und dann „Kopf“. Wenn wir also einfach den Wert der ersten Münze zurückgeben, erhalten wir „Kopf“ oder „Zahl“ mit der gleichen Wahrscheinlichkeit, dh 1/2. Diese Antwort stammt von –
http://jeremykun.com/2014/02/08/simulating-a-fair-coin-with-a-biased-coin/
lesen Sie mehr darüber unter http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin

  • Dies ist ein Duplikat der derzeit akzeptierten Antwort.

    – Jeremy Westen

    10. Februar 2015 um 18:33 Uhr

1354380cookie-checkC-Puzzle: Machen Sie eine faire Münze aus einer voreingenommenen Münze

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy