Simulating Unbalanced Coin Tossing by Balanced Coin

Photo Credit: WeGraphics

Simulating Unbalanced Coin Tossing by Balanced Coin

In the previous post type II problem, we discussed a type of questions saying that we have a flawed coin (probability 0.3 to be front and 0.7 probability to be back) and we simulate a perfect coin tossing. This time we do the reversed one, with a perfect coin (0.5 back and 0.5 front) and the objective of simulating a imperfect coin tossing (0.3 back and 0.7 front).

Problem

You are given a machine which could generate random integer numbers 0 and 1 with even probability, how can you generate uneven random events with probability 0.3 and 0.7?

Let us be straight to the point. The solution is to transform the target probabilities to binary form, and simulate it digit by digit.

To explain it in an example. We want to simulate an event I of probability 0.7 (also expressed as 0.10110011001100110…) and even II of probability of 0.3. Start with the perfect coin to simulate a series of 0s and 1s. For example, if the simulated series is 0011000, after comparing it with the target 0.10110011001100110… from the first digit after the decimal, we find it to be smaller than the target (0.0011000<0.1011001100…), hence this series produces event I. If the simulated series is 11, we immediately judge it to be larger than 0.1011 (0.11>0.1011…), producing event II.

The underlying logic here is to decompose the target number to digits that we can simulate using our machine. The drawback is theoretically the series might be countlessly long so we have to exercise a cut off sometimes, and it might take many tossing to produce one event.

Get any good solutions? Let me know.