13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What form does the input take? If we're guaranteed that it's an IEEE-754 floating point number of a given size, then this is actually pretty easy. \$\endgroup\$ – Peter Taylor Sep 6 '12 at 19:12
4
\$\begingroup\$

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$-
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm impressed that you came back 6 years later to optimize this solution. \$\endgroup\$ – Misha Lavrov Dec 17 '18 at 22:54
3
\$\begingroup\$

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%.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Looks much better than 1% to me. I ran your program 100,000 times for probabilities of [0,1] with a step of 0.01 and compared this with random.random() < desiredProbability using this script: gist.github.com/3656877 They match up perfectly i.imgur.com/Hr8uE.png \$\endgroup\$ – Matt Sep 6 '12 at 14:36
  • \$\begingroup\$ Although, as expected, random.random() < x is considerably faster. \$\endgroup\$ – Matt Sep 6 '12 at 14:37
3
\$\begingroup\$

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

histogram

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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⌉.)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.