# How to generate equiprobable numbers with a random generator?

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) ?

-
If I understand the question correctly, you are flipping a coin and you want outputs of 1 2 or 3. Why not flip the coin twice : on HH you get 1 on HT you get 2 on TH you get 3 and on TT you reflip it twice. Maybe I am grossly misunderstanding the question? –  Euler....IS_ALIVE Aug 22 '12 at 20:20
@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. –  randy Aug 22 '12 at 20:23

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<x$, 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.

-
Nice, is there an algorithm which takes always the same time to execute ? –  randy Aug 22 '12 at 20:27
@randy There can't be a bounded solution, because after $n$ random numbers from $1$ to $3$, you get $3^n$ equally likely results, and $3^n$ is odd, so there is no way to divy them up. –  Thomas Andrews Aug 22 '12 at 20:30
There isn't. This can be shown by looking at the probability of any event based on number of tosses bounded by a constant number $N$. –  André Nicolas Aug 22 '12 at 20:32
What about heads if 1, tails if 2 and alternate between heads and tails when 3 comes up. This will give the 50/50 split in the long run but maybe it loses its randomness (but not in a very obvious way). –  Michael Chernick Aug 22 '12 at 21:46

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

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.

-

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.

-