10

You are given an unbiased fair coin, ie., a coin that produces heads with probability 0.5. Can you use this coin to simulate a biased coin that produces heads with some given probability $p$ ?

This is a reversal of my previous puzzle. Thanks to happystar for the idea. Simulating an unbiased coin with a biased one

bobble
  • 10,245
  • 4
  • 32
  • 80
Dmitry Kamenetsky
  • 35,897
  • 5
  • 66
  • 276
  • 1
    For the sake of completeness: How about Simulating a biased coin with another, differently biased coin? – loopy walt May 20 '21 at 07:58
  • 1
    That sounds like a great idea! Would you like to post that puzzle? I am sure people are getting sick of my posts. – Dmitry Kamenetsky May 20 '21 at 08:07
  • Some of the exact same answers as on the other question work for this. For my second answer, for example, simply change the initial of 0.5 to the probability you want to simulate - also for the proposed further question from @loopywalt. There are MANY other answers as noted in the comments to the original. – Steve May 20 '21 at 08:07
  • Steve can you elaborate? I don't quite see it at this stage. – Dmitry Kamenetsky May 20 '21 at 08:09
  • In your implementation, change double t=0.5; to the probability you want to simulate. Input a fair or biased coin as you prefer. – Steve May 20 '21 at 08:12
  • I'd also note that the comment from @jll on the original question remains valid: "This is a very well studied problem in the literature" – Steve May 20 '21 at 08:36
  • @Steve I finally implemented you suggestion. It worked with double t=1-p; – Dmitry Kamenetsky May 24 '21 at 05:38

4 Answers4

20

Yes, you can do it like this:

Start with the pair (0,1).
Then, repeat this process:
- Flip the coin.
- If it's heads, replace the pair $(x,y)$ with $(\frac{x+y}2,y)$.
- If it's tails, replace the pair $(x,y)$ with $(x,\frac{x+y}2)$.
Once both numbers in your pair are on the same side of $p$, stop. If they're both below $p$, your result is heads, and if they're both above $p$, your result is tails.

Why does this work?

Consider the interval [0,1], with $[0,p]$ labelled 'heads' and the remainder labelled 'tails'. The process is effectively selecting a point in this interval, using a uniform distribution.

If you have the pair $(x,y)$, that means your randomly-selected point is in the interval $[x,y]$. Each time you flip the coin, you cut this interval in half, to determine your point more precisely. And once you've determined that one of the two sides is impossible to get as a result, you can stop flipping.

Deusovi
  • 146,248
  • 16
  • 519
  • 609
  • 3
    This is very clever! Much better than my solution. I think this is doing a form of binary search. – Dmitry Kamenetsky May 20 '21 at 04:50
  • 1
    Wow, I didn't think this was possible. Nice one! I thought maybe only rational points will be able to be simulated. – justhalf May 20 '21 at 05:23
  • 1
    I thought you'd say that you are essentially generating rot13(ovgf va gur ovanel rkcnafvba bs n ahzore orgjrra 0 naq 1, jvgu urnqf nf 0 naq gnvyf nf 1. Vs lbh qvq guvf gb vasvavgl lbh'q unir havsbezyl pubfra n erny va gur vagreiny, ohg bs pbhefr lbh fgbc nf fbba nf lbh xabj gung erny ahzore jvgu rabhtu cerpvfvba gb qrgrezvar juvpu fvqr bs c vg snyyf ba). – Jaap Scherphuis May 20 '21 at 06:00
  • 1
    In addition, if one needs to simulate multiple events, any extra entropy consumed from the coin can be recycled for the next simulated event. Instead of starting with $(0,1)$ next time, start with either $(\frac{x}p,\frac{y}p)$ or $(\frac{x-p}{1-p},\frac{y-p}{1-p})$ depending on which are within the interval $[0,1]$. This may allow further results to be output without any more coin tosses. – Steve May 20 '21 at 08:28
  • 2
    @Steve for my taste this useful and insightful enough to warrant a separate answer. Here more than at the other question where it is for better or worse upstaged by a certain much simpler method. (I only looked at it after reading your comment here.) – loopy walt May 20 '21 at 08:45
  • @loopywalt the question is broad enough that vast essays and research papers can (and indeed have) been written on the topic. It warrants far more than a "separate answer". Better-researched and more targetted questions would help! – Steve May 20 '21 at 09:35
  • 1
    @loopywalt ... or put another way, this answer (and my comment) pretty much amount to "the standard way to solve this problem, being a step involved in arithmetic coding" – Steve May 20 '21 at 09:44
  • @Deusovi I have implemented this method. It works, but I had to change ordering of the outcome - below p should be tails and above p should be heads. – Dmitry Kamenetsky May 24 '21 at 05:41
  • +1 as this can be used even if $p$ is not rational. This would not be the case if $p$ is stored in a computer memory, but it is an interesting problem in theory, or you could have an iterative procedure to compute the digits of $p$ one after the other (like the one used to compute the digits of $\pi$) – melfnt Jul 17 '22 at 12:54
7

Construct a decimal number 0.abcdef... in base 2 by flipping the coin and writing a 1 whenever it is heads, and 0 whenever it is tails. If the number you have written down agrees with p's binary decimal representation so far, keep going. If not, return Heads if your number has a 0 where p has a 1, and Tails if your number has a 1 where p has a 0.

This works because

The construction is equally likely to generate any number between 0 and 1. Thus, the number it generates is between 0 and p with probability p. You don't need to generate the entire number, since at some point you can be assured it will be less or greater than p (with probability 1 - there's the effectively zero chance that it will be a repeating decimal at some point but we can ignore that).

hdsdv
  • 5,180
  • 18
  • 29
4

If $p$ is $\frac{n}{m}$ for some $n,m$:

find the minimum k such that $2^k \geq m$. When the coin is flipped $k$ times there are $2^k$ possible results: write all the possible results in lexicographical order and map the first $n$ results to Head and the next $m-n$ results to Tails.

Then just

Flip the coin $k$ times. If the rank of the result (in lexicographical order) is one of the first $n$, the output is Head. If the rank of the result is from $n+1$ to $m$, the output is Tails. If the rank of the result is from $m$ to $2^k$, flip the coin $2^k$ times again and repeat

Example with $p=\frac{1}{7}$:

$k$ is $3$ because $2^k = 8 \geq 7$. The possible results in lexicographical order are:
HHH
HHT
HTH
HTT
THH
THT
TTH
TTT

Flip the coin 3 times: if the resul is HHH, set the output to the biased coin to be H. If the result is one of HHT...TTH set the output to the biased coin to be T. If the result is TTT, flip the coin 3 times again and repeat.

Some optimization (thanks to @steve in the comments).

  1. Thanks to the lexicographical order, sometimes we can stop the process before finishing all the $k$ flips. In the example above, if the first results are HT or TH we are going to output T.

  2. Sometimes a value for $k$ greater than the minimum required will allow to discard less flips on average. For example, if $m=5$ using $k=3$

the first five outcomes will be mapped either to H or T, while the last three will result in "wasting" the three flips and repeating the process. So, every time we want a random outcome with $p=n/5$ if we use $k=3$ the expected number of coin tosses $E_3$ is equal to $3$ in $5/8$ cases, and it is equal to $3+E_3$ in the other $3/8$ cases, that is $E_3 = 3 \times 5/8 + (E_3+3) \times 3/8$. Solving for $E_3$ gives us $E_3 = 24/5 = 4.8$

However, if we use $k=4$

the first fifteen outcomes will be mapped either to H or T, and we are "wasting" the flips in just one case out of sixteen. So, every time we want a random outcome with $p=n/5$ if we use $k=4$ the expected number of coin tosses $E_4$ is equal to $4$ in $15/16$ cases, and it is equal to $4+E_4$ in the last case, that is $E_4 = 4 \times 15/16 + (E_4+4) \times 1/16$. Solving for $E_4$ gives us $E_4 = 64/15 \approx 4.267 $

melfnt
  • 5,132
  • 2
  • 13
  • 58
  • Some improvement to this (on average) may be possible for certain values. e.g. if $m=5$, rather than using $k=3$ and discarding 3/8 of groups of 3 flips, you can use $k=4$ and discard only 1/16 of groups of 4 flips. Also due to lexicographic order, the final result may be apparent without finishing all the flips (in your example, TH or HT from first 2 flips give certainty of the final result without flipping the coin a 3rd time). Also useful to find a good approximation of $p=\frac{n}{m}$ where $m=2^k$, so that number of flips is constant or has an upper bound. – Steve May 20 '21 at 10:18
  • 1
    what happens when $p$ is irrational? – Dmitry Kamenetsky May 20 '21 at 10:19
  • 2
    @DmitryKamenetsky this method requires $p$ (or a sufficiently good approximation) to be rational. If $p$ is being stored on a computer, it is certainly rational! – Steve May 20 '21 at 10:20
  • @Steve that's great, I didn't realize that some optimization are possible! Do you want to post your own answer? Otherwise I can add this information to my answer – melfnt May 20 '21 at 10:21
  • 1
    @melfnt with vast numbers of possible answers to this insufficiently scoped question, I already posted two of the 4 I thought of on the previous question... so to balance things out, I'll post none to this one... feel free to improve your own answer as much as you want though! Practical implementations of this would usually use k=32 or k=64 or similar (or k=256 or more in cryptographic applications). – Steve May 20 '21 at 10:43
  • well to be fair the question is sufficiently scoped. It simply asks how you can do it. It is not asking you for the most efficient way - that is more of a bonus question. Note I really appreciate all your answers and effort. I just don't think these questions are too open, like you say. – Dmitry Kamenetsky May 20 '21 at 12:51
1

What a nice coincidence when I found StackExchange's featured hot topic to be almost the same question that I asked some days ago at CrossValidate SE: Intended selection bias. Here I describe the following procedure:

Consider a bag of balls of two equally distributed colors. If I pick a ball uniformly at random it is a red or a blue ball with equal probability $p_{\textsf{red}} = p_{\textsf{blue}} = 1/2$. But then I want to get a red ball with probability $p_{\textsf{red}} = 2/3$ – for whatever reasons.

Two methods come to my mind:

  1. Create another bag with two copies of each red ball in the original set and one copy of each blue ball. Now the probability of picking a red ball uniformly at random is $p_{\textsf{red}} = 2/3$.

  2. Pick a ball uniformly at random from the original set. If it is a red one (which happens with probability $1/2$), keep it. If it is a blue one, pick a number $r$ uniformly at random from $[0,1]$. If $r > \theta$, put it back and pick another ball uniformly at random. Keep it.

To achieve $p_{\textsf{red}} = 2/3$ you have to choose $\theta$ such that $1/2 + 1/2\cdot (1-\theta)\cdot 1/2 = 2/3$, i.e. $\theta = 1/3$.

Does this qualify for an answer to your question?

Hans-Peter Stricker
  • 111
  • 3
  • This seems to amount to "use some other source of randomness, $r$, to control which result you get". That can be simplified by using $r$ to directly select the final result, rather than using the coin (or bag of balls) at all. – Steve May 21 '21 at 11:23
  • 1
    Interesting coincidence indeed and I enjoyed reading the background to your question. Here we need to use the fair coins as the only source of randomness, so we can't use your r. – Dmitry Kamenetsky May 21 '21 at 11:36
  • @Steve: Could you please be a bit more specific how to use $r$ directly? Would this also work when the prior probabilites for red and blue are unequal, i.e. $p_{\textsf{red}} \neq p_{\textsf{blue}}$? – Hans-Peter Stricker May 21 '21 at 11:55
  • @Hans-PeterStricker To use $r$ directly, if $r > \theta$ show a blue ball (or return a simulated head, or select outcome 1) otherwise show a red ball (or return a simulated tail or select outcome 2). It almost certainly won't make sense in the context of your original question though... – Steve May 21 '21 at 12:06