Given a fair coin as input, generate any particular unfair outcome

Question

It is easy to generate a fair coin using a unfair coin, but the reverse is harder to accomplish.

Your program will receive one number X (between 0 and 1, inclusive) as input. The input must not simply be hard-coded as a number in the middle of the source code. It must then return a single digit: a 1 with a probability of X and a 0 otherwise.

Your program is only allowed to use one form of random number generator in the source code: int(rand(2)) (or an equivalent), which returns either a zero or a one with equal probability. You can include or access this function as many times as you wish in your code. You also have to provide the function yourself as part of the code.

Your program is not allowed to use any other random number generating functions or external sources (such as time and date functions) that could function as a random number generating function. It also cannot access any external files or pass the job along to external programs.

This is code golf, the shortest answer wins.

Answer 1

Perl, 37 42 char

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

Takes arbitrary probability as a command line argument. Builds a uniform random number in $d and compares it to the input.

Earlier, 52 char solution

$p=<>;do{$p*=2;$p-=($-=$p)}while$--(.5<rand);print$-

Answer 2

Python, 81 chars

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

Can be off by a bit, but never more than 1%.

Answer 3

Mathematica 165

Not streamlined, but some may find the algorithm of interest:

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

Usage

f[.53]

1

Check

Let's see if f[.53] really produces the value 1 around 53% of the time. Each test calculates the % for samples of 10^4.

50 such tests are run and averaged.

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.5293}

0.529798

Histogram of results

Explanation (spoiler alert!)

The base 2 representation of .53 is

.10000111101011100001010001111010111000010100011110110

Proceeding from left to right, one digit at a time:

If RandomInteger[] returns 1, then answer = 1,

Else If second RandomInteger[] returns 0, then answer = 0,

Else If third RandomInteger[] returns 0, the answer = 0,

Else....

If, when all digits have been tested, there is still no answer, then answer = RandomInteger[].

Answer 4

Haskell, 107 chars:

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

Answer 5

Wolfram Language (Mathematica), 42 bytes

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

Try it online!

This is a recursive approach. Ungolfed, the algorithm is:

• If the input probability p is less than 1/2, then when the coinflip comes up 0, return 0. Otherwise, recurse on 2p; assuming correctness, the overall probability of getting 1 is half of 2p or p.
• If the input probability p is greater than 1/2, then when the coinflip comes up 1, return 1. Otherwise, recurse on 2p-1; assuming correctness, the overall probability of getting 0 is half of 1-(2p-1) or 1-p.

To make it shorter, we start with the random coinflip, which, in either branch, gets returned half the time. If the coinflip does not match the case when we're supposed to return it, replace it by the result of recursing on 2p modulo 1. (That is, when p is less than 1/2, replace 1; when p is greater than 1/2, replace 0. This is equivalent to replacing ⌈1-2p⌉.)