4
$\begingroup$

Is it possible to emulate a 2 sided coin flip (50/50) with a random number generator which outputs equiprobably the numbers 1, 2 and 3 ? If yes, how ?

If not why ?

Is there a theorem?

Can it be expanded to any numbers x ("sides" of the coin) and y (random generator output) ?

  • 0
    @Euler....IS_ALIVE : it's quite the opposite : emulate a coin, have outputs with probability 50%/50%, with a random number genrator which has probability 1/3 , 1/3 , 1/3.2012-08-22

3 Answers 3

8

Yes, of course. The simplest way to do this is to treat $1$ as heads, $2$ as tails, and try again if you get a $3$.

The same approach works whenever $y>x$. If $y, choose $n$ large enough that $y^n>x$, then generate $n$ numbers at a time and use the above approach with the resulting $n$-tuples.

  • 0
    @MichaelChernick: It will deviate in a very obvious way: With probability $2/3$ it will give the other value in the next round.2016-07-28
7

In general you should need to query the $3$-valued generator fewer times than the number of bits you want to produce, since the amount of entropy per query is $\log(3)/\log(2)=1.58496...$ bits. However, since $\log(3)/\log(2)$ is irrational, there's no finite number of queries that can be converted into a fixed number of bits. The best you can do is keep the rounded-off randomness and save it for later use, as follows:

  1. Start with $(x,w)=(0,1/3)$.

  2. Let $(x,w)=(x+aw,w/3)$, where $a=0,1,2$ with equal probability (using the $3$-valued generator).

  3. Repeat these checks as long as one passes: (a) If $x\ge 1/2$, output "$1$", then let $(x,w)=(2x-1,2w)$; or (b) if $x+3w<1/2$, output "$0$", then let $(x,w)=(2x,2w)$.

  4. Return to step 2.

What this does is generate the successive ternary digits of a real number in $[0,1)$, and outputs each binary digit of the same real number as soon as it is known for certain. This is essentially arithmetic coding, and of course it can be used for any two bases.

1

Here is the solution to the general problem: how to sample with probability p given a die with b faces. Illustrated here with p = 1/pi and b = 6.

Write p in base b: p = 0.152431022133341414... (Of course, if p is rational this is a recurring sequence.)

Throw the die to generate a set of random digits in [0, b) = 1 3 5 2 ... and write as a real number q in base b = 0.1352...

Return q < p. Typically only 1-2 random digits need to be generated.

Interestingly sampling with probability 1/pi can be done without knowing the value of pi by using a theorem of Ramanujan. See

http://randomlib.sf.net/1.6/classRandomLib_1_1InversePiProb.html

and references therein.