Erzeugen Sie bei einer fairen Münze als Eingabe ein bestimmtes unfaires Ergebnis

13

Es ist einfach, eine faire Münze mit einer unfairen Münze zu generieren, aber das Gegenteil ist schwieriger zu erreichen.

Ihr Programm erhält eine Ziffer X (zwischen 0 und 1) als Eingabe. Die Eingabe darf nicht einfach als Zahl in der Mitte des Quellcodes fest codiert werden. Es muss dann eine einzelne Ziffer zurückgeben: a 1mit einer Wahrscheinlichkeit von X und a 0ansonsten.

Ihr Programm darf nur eine Form des Zufallszahlengenerators im Quellcode verwenden: int(rand(2))(oder eine gleichwertige), die entweder eine Null oder eine Eins mit gleicher Wahrscheinlichkeit zurückgibt. Sie können diese Funktion beliebig oft in Ihren Code aufnehmen oder darauf zugreifen. Sie müssen die Funktion auch selbst als Teil des Codes bereitstellen.

Ihr Programm darf keine anderen Funktionen zur Generierung von Zufallszahlen oder externe Quellen (wie Uhrzeit- und Datumsfunktionen) verwenden, die als Funktion zur Generierung von Zufallszahlen fungieren könnten. Es kann auch nicht auf externe Dateien zugreifen oder den Auftrag an externe Programme weitergeben.

Dies ist Code Golf, die kürzeste Antwort gewinnt.

code-golf math PhiNotPi
quelle
Wie sieht die Eingabe aus? Wenn wir garantiert sind, dass es sich um eine IEEE-754-Gleitkommazahl einer bestimmten Größe handelt, ist dies eigentlich recht einfach.
Peter Taylor

Antworten:

4

Perl, 37 42 char

($d/=2)+=rand>.5for%!;print$d/2<pop|0

Nimmt eine beliebige Wahrscheinlichkeit als Befehlszeilenargument. Baut eine einheitliche Zufallszahl auf $dund vergleicht sie mit der Eingabe.

Früher 52 Zeichen Lösung

$p=<>;do{$p*=2;$p-=($-=$p)}while$--(.5<rand);print$-
Mob
quelle
1
Ich bin beeindruckt, dass Sie 6 Jahre später zurückkamen, um diese Lösung zu optimieren.
Mischa Lawrow
3

Python, 81 Zeichen

import random
print(sum(random.randint(0,1)*2**-i for i in range(9))<input()*2)+0

Kann etwas abweichen, aber niemals mehr als 1%.

Keith Randall
quelle
Sieht für mich viel besser aus als 1%. Ich habe Ihr Programm 100.000 Mal für Wahrscheinlichkeiten von [0,1] mit einem Schritt von 0,01 ausgeführt und dies mit der random.random() < desiredProbabilityVerwendung dieses Skripts verglichen : gist.github.com/3656877 Sie stimmen perfekt überein i.imgur.com/Hr8uE.png
Matt
Obwohl, wie erwartet, random.random() < xerheblich schneller ist.
Matt
3

Mathematica 165

Nicht optimiert, aber einige finden den Algorithmus von Interesse:

d = RealDigits; r = RandomInteger;
f@n_ := If[(c = Cases[Transpose@{a = Join[ConstantArray[0, Abs[d[n, 2][[2]]]], d[n, 2][[1]]], 
         RandomInteger[1, {Length@a}]}, {x_, x_}]) == {}, r, c[[1, 1]]]

Verwendung

f[.53]

1

Prüfen

Mal sehen, ob f[.53]der Wert tatsächlich in 153% der Fälle erreicht wird. Jeder Test berechnet die% für Proben von 10 ^ 4.

50 solcher Tests werden ausgeführt und gemittelt.

Table[Count[Table[f[.53], {10^4}], 1]/10^4 // N, {50}]
Mean[%]

{0,5292, 0,5256, 0,5307, 0,5266, 0,5245, 0,5212, 0,5316, 0,5345, 0,5297, 0,5334, 0,5306, 0,5288, 0,528, 0,5379, 0,5293, 0,5263, 0,539, 0,5322, 0,5195, 0,5208, 0,5382, 0,543, 0,5336, 0,5305 0,5297, 0,5318, 0,5243, 0,5281, 0,5361, 0,5349, 0,5308, 0,5265, 0,5309, 0,5233, 0,5345, 0,5316, 0,5376, 0,5264, 0,5269, 0,5295, 0,523, 0,5294, 0,5326, 0,5316, 0,5334, 0,5165, 0,5296, 0,5366 }

0,529798

Histogramm der Ergebnisse

Histogramm

Erklärung (Spoiler Alarm!)

Die Basis 2 Darstellung von .53 ist

.10000111101011100001010001111010111000010100011110110

Von links nach rechts fortfahren, eine Ziffer nach der anderen:

Wenn RandomInteger [] 1 zurückgibt, ist answer = 1,

Sonst Wenn zweite RandomInteger [] 0 zurückgibt, dann antworte = 0,

Sonst Wenn dritte RandomInteger [] 0 zurückgibt, ist die Antwort = 0,

Sonst....

Wenn nach dem Testen aller Ziffern immer noch keine Antwort vorliegt, ist answer = RandomInteger [].

DavidC
quelle
1

Haskell, 107 Zeichen:

import System.Random
g p|p>1=print 1|p<0=print 0|1>0=randomIO>>=g.(p*2-).f
f x|x=1|1>0=0.0
main=readLn>>=g
Rotsor
quelle
0

Wolfram Language (Mathematica) , 42 Byte

RandomInteger[]/.⌈1-2#⌉:>#0@Mod[2#,1]&

Probieren Sie es online!

Dies ist ein rekursiver Ansatz. Ungolfed, der Algorithmus ist:

  • Wenn die Eingabewahrscheinlichkeit pkleiner als 1/2 ist, geben Sie 0 zurück, wenn der Münzwurf 0 ergibt 2p. Unter der Annahme der Korrektheit beträgt die Gesamtwahrscheinlichkeit, eine 1 zu erhalten, die Hälfte von 2poder p.
  • Wenn die Eingabewahrscheinlichkeit pgrößer als 1/2 ist, geben Sie 1 zurück, wenn der Münzwurf 1 ergibt 2p-1. Unter der Annahme der Korrektheit beträgt die Gesamtwahrscheinlichkeit, 0 zu erhalten, die Hälfte von 1-(2p-1)oder 1-p.

Um es kürzer zu machen, beginnen wir mit dem zufälligen Coinflip, der in beiden Zweigen die Hälfte der Zeit zurückgegeben wird. Wenn der Münzwurf nicht mit dem Fall übereinstimmt, in dem er zurückgegeben werden soll, ersetzen Sie ihn durch das Ergebnis der Rekursion von 2pModulo 1. (Wenn palso weniger als 1/2 ist, ersetzen Sie 1; wenn pgrößer als 1/2 ist , 0 ersetzen. Dies entspricht dem Ersetzen ⌈1-2p⌉.)

Mischa Lawrow
quelle