Frage:
Gibt es eine überprüfbare Möglichkeit, diskrete Zufallsvariablen auf der Grundlage eines externen Ereignisses zu generieren?
user28
2010-09-21 05:47:16 UTC
view on stackexchange narkive permalink

Angenommen, wir möchten aus der folgenden Verteilung ein Unentschieden generieren:

$ P (X = 0) = 0,5 $

$ P (X = 1) = 0,5 $

Es gibt jedoch zwei Einschränkungen:

(a) Die Auslosung muss auf der Grundlage eines externen Ereignisses erfolgen.

(b) Bezogen auf (a ) muss die Auslosung durch einen Dritten überprüfbar sein. Mit anderen Worten, ein Dritter sollte in der Lage sein zu überprüfen, ob meine Ziehung tatsächlich $ X = 0 $ war (sagen wir).

Fn 1: Kann ein solches System entwickelt werden und wenn ja, wie?

Qn 2: Kann das System auf diskrete Variablen mit mehr als 2 möglichen Ergebnissen erweitert werden (wie das Würfeln)?

Qn 3: Kann es auch auf kontinuierliche Variablen erweitert werden (zB das normale)?

Was meinst du mit "verifizieren"? Bedeutet dies, dass der Dritte das externe Ereignis kontrolliert? dies würde der pmf hier widersprechen.
Offensichtlich sollte der Dritte das externe Ereignis nicht kontrollieren, damit die Frage sinnvoll ist. Nehmen wir als Beispiel an, wir meinen, wir stimmen darin überein, dass das Protokoll wie folgt lautet: Wenn es morgen in New York regnet, ist X = 0, sonst X = 1. Die Auslosung basiert auf einem externen Ereignis und ist in dem Sinne überprüfbar, dass jemand überprüfen kann, ob es nachträglich wirklich geregnet hat.
Wie wäre es mit weißem Rauschen, das Sie in einem unbenutzten Radioband aufnehmen könnten?
Fünf antworten:
#1
+7
Matt Parker
2010-09-22 10:25:08 UTC
view on stackexchange narkive permalink

Genau wie eine weitere Quelle überprüfbarer Zufälligkeit: random.org generiert Zufallszahlen aus atmosphärischem Rauschen. Sie veröffentlichen eine tägliche Datei (die meisten Tage) mit zufälligen Bits; Die erste Ziffer der Datei eines jeden Tages kann sich für Ihre Parteien als angemessen überprüfbar erweisen.


Update 2013-11-12 : Der Zugriff auf diese Dateien ist jetzt eingeschränkt, sieht aber so aus So können Sie den Betreibern von random.org eine E-Mail senden, um Zugriff zu erhalten:

Hinweis: Der Zugriff auf die vorgenerierten Dateien ist derzeit aus Bandbreitengründen eingeschränkt. Lassen Sie uns wissen ([email protected]), ob Sie Zugriff benötigen.

Tangens: Dirk Eddelbuettel hat ein R-Paket (http://cran.r-project.org/web/packages/random/index.html) geschrieben, um auf Zufallszahlen zuzugreifen. Nicht überprüfbar.
Das funktioniert perfekt.
Ich kann nicht auf diese Textdateien zugreifen. Es sind Benutzername und Passwort erforderlich.
Vielen Dank für den Hinweis, @Muhd. Sieht so aus, als könnten Sie eine E-Mail für den Zugriff senden, aber dies macht die Dateien weniger nützlich.
#2
+6
Simon Byrne
2010-09-22 16:53:02 UTC
view on stackexchange narkive permalink

In vielen Ländern gibt es eine staatliche Lotterie, die regelmäßig überprüft wird und deren Ergebnisse online bekannt gegeben werden: z. Nationale Lotterie in Großbritannien. Sie müssen nur eine geeignete Funktion erstellen, die diesen Ausgaberaum Ihrer gewünschten Ausgabe zuordnet.

Eine kontinuierliche Verteilung wäre schwieriger, aber Sie könnten eine diskrete Annäherung erhalten: Im Fall von Großbritannien gibt es $ {} ^ {49} C_6 \ times 43 $ = 601 304 088 gleich wahrscheinliche Ergebnisse, die kann je nach Kontext eine ausreichende Granularität ergeben.

#3
+3
shabbychef
2010-09-21 09:48:37 UTC
view on stackexchange narkive permalink

Dies erinnert mich an eine Frage aus der Algorithmenklasse vor langer Zeit. Das externe Ereignis sei eine (vorzugsweise kontinuierliche) Zufallsvariable $ Y $. Um einen Wert von $ X $ zu generieren, nehmen Sie zwei unabhängige Beobachtungen von $ Y $ und lassen Sie $ X $ $ 1 $ sein, wenn die erste Beobachtung von $ Y $ größer als die zweite ist, lassen Sie $ 0 $, wenn die zweite größer als ist das erste und wiederholen Sie das Experiment, wenn es ein Unentschieden gibt. Offensichtlich funktioniert dies besser, wenn $ Y $ kontinuierlich ist. Wenn nur ein Münzwurf als Generator verfügbar ist, kann die Anzahl der aufeinanderfolgenden Köpfe, bevor ein Schwanz angezeigt wird, die Zufallsvariable $ Y $ sein. (Ich glaube, die Hausaufgabenfrage war, wie man einen voreingenommenen Münzwurf in einen unvoreingenommenen Münzwurf verwandelt. Ein Teil der Hausaufgaben bewies, dass der Prozess enden würde ...)

Dies kann offensichtlich auf den erweitert werden diskreter Fall auch, obwohl man mit Krawatten auf größere Schwierigkeiten stoßen kann. Wenn Sie $ n $ mögliche Ergebnisse für $ X $ haben, nehmen Sie einige $ k $ so, dass $ n $ $ k! $ Teilt, und teilen Sie dann die $ k! $ Möglichen Ordnungen von $ k $ Beobachtungen von $ Y $ in Äquivalenzklassen auf für $ X $.

edit: per @ srikants Kommentar, ein Beispiel für einen möglichen Generator von $ Y $: (wie von @andyW erwartet) Sei $ Z_i $ die Anzahl der Aktien, mit denen gehandelt wird ein bestimmter hochliquider ETF, wie von einer bestimmten Quelle über einen festgelegten Zeitraum gemeldet, eindeutig indiziert durch $ i $. Sei $ Y_i = \ tan {(Z_i)}, $ wobei die Tangentenfunktion von einer festen Standardbibliothek berechnet wird (in einer festen Revision von R beispielsweise auf einer festen Plattform). Ein solcher Generator von $ Y $ ist pseudozufällig genug für mich. Andere Generatoren von $ Z $ sind ebenfalls für diesen Prozess zugänglich, wenn sie in Bezug auf $ 2 \ pi $ stark genug variieren.

Was wäre ein konkretes Beispiel für ein externes Ereignis, das ich für $ Y $ verwenden könnte?
Als Beispiel dachte ich zuerst an alte Zahlenspiele, bei denen ein Dezimalpunkt bestimmter Aktienberichte in der Zeitung verwendet wurde. Natürlich würden Sie sich über die wahre Zufälligkeit dieser Metrik Sorgen machen, daher stelle ich mir vor, dass es bessere Beispiele gibt.
Alles, was Sie benötigen, ist eine zugängliche Ganzzahl oder eine Sammlung von Ganzzahlen, um als Startwert für einen Pseudozufallsgenerator und möglicherweise als Anzahl von Iterationen des Pseudozufallsgenerators zu fungieren.Daraus können Sie jede diskrete oder kontinuierliche Verteilung generieren.
#4
+1
Keith Winstein
2010-09-22 23:26:27 UTC
view on stackexchange narkive permalink

Ich habe nicht ganz verstanden, was Sie unter "aufgrund eines externen Ereignisses" verstanden haben. Aber Sie können eine faire Münze auf eine Weise werfen, die ein entfernter Benutzer kryptografisch überprüfen kann.

Betrachten Sie diesen Algorithmus:

  1. Bob wählt einen einheitlich zufälligen booleschen Wert, TRUE oder FALSCH. Er wählt auch eine große Zufallszahl. Er sendet Alice den SHA-256-Hash des mit der Nummer verketteten Booleschen Werts. (ZB sendet er den Hash von "TRUE | 12345678".) Da Alice die Zufallszahl nicht kennt und der Hash einseitig ist, kennt Alice den Booleschen Wert nicht.
  2. Alice dreht a um Münze und sendet Bob den Wert - WAHR oder FALSCH.
  3. Bob zeigt die Zufallszahl und damit seinen eigenen Booleschen Wert an. Alice überprüft, ob der Boolesche Wert und die Zufallszahl tatsächlich mit dem Wert übereinstimmen, den sie zuvor erhalten hat.
  4. Diese endgültige Ausgabe des Münzwurfs ist das Exklusiv-Oder des Booleschen Werts von Alice und des Booleschen Werts von Bob.
  5. ol>

    Mit diesem Algorithmus kann keine Partei ohne die Mitwirkung der Gegenpartei betrügen. Wenn eine der Parteien fair spielt, ist die Ausgabe ein einheitlicher zufälliger boolescher Wert.

    (BEARBEITEN) Ich verstehe das Problem jetzt so, dass Sie überhaupt keine interne Quelle für Nichtdeterminismus haben, daher muss jede Zufälligkeit kommen eine externe Quelle und der Algorithmus muss deterministisch sein. In diesem Fall können wir weiterhin Kryptografie verwenden, um zu helfen.

    Wie wäre es, wenn Sie jeden Tag den SHA-256 der PDF-Version der New York Times oder den SHA-256 des Volumens und des Schlusskurses von nehmen Alle Aktien des Dow Jones Industrial Average in alphabetischer Reihenfolge nach Tickersymbol oder wirklich der sichere Hash von allem, was gegenseitig beobachtet werden kann und das Sie nicht beeinflussen können. Wenn Sie nur ein Bit möchten, nehmen Sie das erste Bit des SHA-256.

    Wenn Sie eine Normalverteilung wünschen, können Sie das Ganze in zwei Teilen (128 Bit, dann 128 Bit) als zwei Teile verwenden einheitliche Abweichungen und verwenden Sie die Box-Muller-Transformation, um zwei normale Abweichungen zu erhalten.

Ich dachte, die Bedeutung von "externem Ereignis" sei klar. Zur Verdeutlichung sollte das externe Ereignis aufgrund der dem Protokoll auferlegten Einschränkungen die Quelle der zufälligen Generierung sein und die Auslosung muss überprüfbar sein. Ihre Antwort bezieht sich auf die Überprüfbarkeit, nicht jedoch auf den externen Ereignisteil. Trotzdem +1 für eine interessante Antwort. Fällt der Algorithmus aus Neugier nicht zusammen, wenn sowohl Bob als auch Alice betrügen und einen Wert melden (0 oder 1, wie sie möchten) * ohne * eine Münze zu werfen?
Hallo Srikant, ja, der Algorithmus erfordert mindestens eine ehrliche Partei. Sie haben überhaupt keine interne Zufallsquelle? Dann könnten Sie jeden Tag den SHA-256 der PDF-Version der New York Times oder den SHA-256 des Volumens und des Schlusskurses aller Aktien im Dow Jones Industrial Average oder den wirklich sicheren Hash von irgendetwas nehmen das kann man sich gegenseitig beobachten und das kann man nicht beeinflussen. Wenn Sie ein Bit möchten, nehmen Sie ein Bit des SHA-256. Wenn Sie eine Normalverteilung wünschen, nehmen Sie das Ganze (256 Bit) als einheitliche Abweichung und verwenden Sie die Box-Muller-Transformation, um eine normale Abweichung zu erhalten.
Ja, Ihre Änderung unter Verwendung des Hash von NYT / Aktienkursen sollte auch funktionieren, obwohl sie die einzige Schwäche hat, mindestens 1 ehrliche Partei zu benötigen. Interessante Art, sich dem Problem zu nähern.
#5
  0
ronaf
2010-09-22 08:42:41 UTC
view on stackexchange narkive permalink

Eine einfache Möglichkeit, symmetrische Bernoulli-Versuche zu generieren, besteht darin, eine Münze zweimal zu werfen. Wenn der erste Wurf H und der zweite T ist, sagen Sie X = 1. Wenn es umgekehrt ist, sagen Sie X = 0. Wenn die beiden Würfe mit [2H oder 2T] übereinstimmen, verwerfen Sie das Ergebnis und fahren Sie fort. Unabhängig von der Vorspannung der Münze ist X symmetrisch bernoulli.

Aber die Frage ist: Wie würden Sie das jemandem auf der anderen Seite der Welt bestätigen? Siehe Punkt b) in der Frage.


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 2.0-Lizenz, unter der er vertrieben wird.
Loading...