Dada una moneda justa como entrada, generar cualquier resultado injusto en particular

13

Es fácil generar una moneda justa usando una moneda injusta, pero lo contrario es más difícil de lograr.

Su programa recibirá un número X (entre 0 y 1, inclusive) como entrada. La entrada no debe estar simplemente codificada como un número en el medio del código fuente. Luego debe devolver un solo dígito: a 1con una probabilidad de X y a lo 0contrario.

Su programa solo puede usar una forma de generador de números aleatorios en el código fuente: int(rand(2))(o un equivalente), que devuelve un cero o uno con la misma probabilidad. Puede incluir o acceder a esta función tantas veces como desee en su código. También debe proporcionar la función usted mismo como parte del código.

Su programa no puede usar ninguna otra función generadora de números aleatorios o fuentes externas (como las funciones de fecha y hora) que puedan funcionar como una función generadora de números aleatorios. Tampoco puede acceder a ningún archivo externo ni pasar el trabajo a programas externos.

Este es el código de golf, gana la respuesta más corta.

PhiNotPi
fuente
¿Qué forma toma la entrada? Si se nos garantiza que es un número de coma flotante IEEE-754 de un tamaño determinado, entonces esto es realmente bastante fácil.
Peter Taylor

Respuestas:

4

Perl, 37 42 char

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

Toma probabilidad arbitraria como argumento de línea de comando. Construye un número aleatorio uniforme $dy lo compara con la entrada.

Anterior, solución de 52 char

$p=<>;do{$p*=2;$p-=($-=$p)}while$--(.5<rand);print$-
multitud
fuente
1
Estoy impresionado de que haya regresado 6 años después para optimizar esta solución.
Misha Lavrov
3

Python, 81 caracteres

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

Puede estar apagado un poco, pero nunca más del 1%.

Keith Randall
fuente
Se ve mucho mejor que el 1% para mí. Ejecuté su programa 100,000 veces para probabilidades de [0,1] con un paso de 0.01 y comparé esto con el random.random() < desiredProbabilityuso de este script: gist.github.com/3656877 Coinciden
Matt
Aunque, como se esperaba, random.random() < xes considerablemente más rápido.
Matt
3

Mathematica 165

No simplificado, pero algunos pueden encontrar el algoritmo de interés:

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]]]

Uso

f[.53]

1

Cheque

Veamos si f[.53]realmente produce el valor 1alrededor del 53% del tiempo. Cada prueba calcula el% para muestras de 10 ^ 4.

50 de estas pruebas se ejecutan y promedian.

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.5303 , 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.5266, 0.5296, 0.2966 }

0.529798

Histograma de resultados

histograma

Explicación (¡alerta de spoiler!)

La representación de base 2 de .53 es

.10000111101011100001010001111010111000010100011110110

Continuando de izquierda a derecha, un dígito a la vez:

Si RandomInteger [] devuelve 1, entonces respuesta = 1,

De lo contrario, si el segundo RandomInteger [] devuelve 0, entonces answer = 0,

De lo contrario, si el tercer RandomInteger [] devuelve 0, la respuesta = 0,

Más....

Si, cuando se han probado todos los dígitos, todavía no hay respuesta, entonces answer = RandomInteger [].

DavidC
fuente
1

Haskell, 107 caracteres:

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
fuente
0

Wolfram Language (Mathematica) , 42 bytes

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

Pruébalo en línea!

Este es un enfoque recursivo. Ungolfed, el algoritmo es:

  • Si la probabilidad de entrada pes inferior a 1/2, cuando el coinflip aparezca 0, devuelva 0. De lo contrario, vuelva a aparecer 2p; suponiendo que sea correcto, la probabilidad general de obtener 1 es la mitad de 2po p.
  • Si la probabilidad de entrada pes mayor que 1/2, cuando el coinflip aparezca 1, regrese 1. De lo contrario, vuelva a comenzar 2p-1; asumiendo la corrección, la probabilidad general de obtener 0 es la mitad de 1-(2p-1)o 1-p.

Para acortarlo, comenzamos con el monedero aleatorio, que, en cualquier rama, se devuelve la mitad del tiempo. Si el monedero no coincide con el caso cuando se supone que debemos devolverlo, reemplácelo por el resultado de recurrir en el 2pmódulo 1. (Es decir, cuando pes menor que 1/2, reemplace 1; cuando pes mayor que 1/2 , reemplace 0. Esto es equivalente a reemplazar ⌈1-2p⌉.)

Misha Lavrov
fuente