Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Zufallszahlen: Fairer und unfairer Münzwurf
Autor
Universität/Hochschule Zufallszahlen: Fairer und unfairer Münzwurf
daniel23
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 16.04.2022
Mitteilungen: 13
  Themenstart: 2022-04-29

Hallo! Ich habe beim Lösen der folgenden Aufgabe Probleme. Aufgabe: ----- Gegeben sei eine Methode UNFAIREMÜNZE(), welche zu jeweils unbekannten (und damit auch potentiell ungleichen) Wahrscheinlichkeiten entweder KOPF oder ZAHL ausgibt. Nehmen Sie an, dass die Wahrscheinlichkeit, dass UNFAIREMÜNZE() KOPF zurück gibt, p ist. Schreiben Sie unter Verwendung dieser Methode eine neue Methode FAIREMÜNZE(), welche zu jeweils gleicher Wahrscheinlichkeit KOPF oder ZAHL ausgibt. Analysieren Sie die erwartete Laufzeit Ihrer Methode in O-Notation abhängig von p. ----- Ich weiß leider nicht, wie ich die Methode UNFAIREMÜNZE() einbinden soll oder wie ich p in der neuen Methode FAIREMÜNZE() verwende. VG Daniel


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2629
  Beitrag No.1, eingetragen 2022-04-29

Wenn p nicht gerade 1 oder 0 ist, funktioniert folgende Funktion. Sie kann zwar trotzdem ewig laufen, das aber nur mit WK 0. \sourceon javascript function FAIREMÜNZE() { while(true) { var w1 = UNFAIREMÜNZE(); var w2 = UNFAIREMÜNZE(); if(w1 != w2) return w1; } } \sourceoff Sie funktioniert, weil die WK, erst KOPF dann ZAHL zu werfen, dieselbe ist, wie die, erst ZAHL, dann KOPF zu werfen, und alle anderen Münzwurfpaarergebnisse verworfen werden.


   Profil
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3671
Wohnort: hier und dort (s. Beruf)
  Beitrag No.2, eingetragen 2022-04-30

Huhu zusammen, tactacs Algorithmus ist sehr nett und er ist in allen praktischen Belangen wohl auch das einzig sinnvoll verwendbare. Unter allen zustandsfreien Algorithmen ist er der beste. Wenn man auf einem realen Computer arbeitet (der also z.B. nur endliche Register besitzt und damit etwa reelle Zahlen nur mit endlicher "Genauigkeit" verarbeitet), so gibt es zustandsbehaftete Algorithmen, die "schneller" sind, in dem folgenden Sinne: Man kann nur unter Verwendung des unfairen Münzwurfs eine Folge von (zur Zahl der Münzwürfe ähnlich vielen) Zahlen erzeugen, deren Autokorrelation $0$ ist und die gleich häufig $0$ und $1$ (interpretiert als Kopf und Zahl) enthalten. Im Grunde baut man damit aber lediglich Kongruenzgeneratoren (oder andere Verfahren zur Erzeugung von Pseudo-Zufallszahlen) nach. Ausserdem kann man noch ein (natürlich ebenfalls zustandsbehaftetes) Ding basteln, dass eine unkorrelierte Folge von Bits erzeugt, die nur asymptotisch (also bei hinreichend häufiger Wiederholung) gleichverteilt sind. Dies entspricht aber vermutlich nicht unserer Idee einer "Fairen Münze". Auch sollte man vermutlich keine Lösungen in Betracht ziehen, die sich einfach eine Zufallszahl von "random.org" abholen und die dann geeignet als Kopf/Zahl interpretieren... Es gibt darüberhinaus aber einen Algorithmus, der sogar ohne Verwendung der Funktion UNFAIREMÜNZE einen fairen Münzwurf simuliert (man kann dies auch als kleines Rätsel sehen*) und - in einem gewissen Sinne - konstante Laufzeit hat: \hideon \sourceon Q# namespace QRNG { open Microsoft.Quantum.Convert; open Microsoft.Quantum.Math; open Microsoft.Quantum.Measurement; open Microsoft.Quantum.Canon; open Microsoft.Quantum.Intrinsic; operation QRNG() : Result { use q = Qubit(); // prepare QBit (=|0>) H(q); // Hadamard transformation return M(q); // PauliZ measurement, i.e. in standard basis } } \sourceoff \hideoff lg, AK *) das nicht zu ernst genommen werden sollte


   Profil
daniel23 hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]