10
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ For the sake of completeness: How about Simulating a biased coin with another, differently biased coin? $\endgroup$ – loopy walt May 20 at 7:58
  • 1
    $\begingroup$ That sounds like a great idea! Would you like to post that puzzle? I am sure people are getting sick of my posts. $\endgroup$ – Dmitry Kamenetsky May 20 at 8:07
  • $\begingroup$ 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. $\endgroup$ – Steve May 20 at 8:07
  • $\begingroup$ Steve can you elaborate? I don't quite see it at this stage. $\endgroup$ – Dmitry Kamenetsky May 20 at 8:09
  • $\begingroup$ In your implementation, change double t=0.5; to the probability you want to simulate. Input a fair or biased coin as you prefer. $\endgroup$ – Steve May 20 at 8:12
18
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ This is very clever! Much better than my solution. I think this is doing a form of binary search. $\endgroup$ – Dmitry Kamenetsky May 20 at 4:50
  • 1
    $\begingroup$ Wow, I didn't think this was possible. Nice one! I thought maybe only rational points will be able to be simulated. $\endgroup$ – justhalf May 20 at 5:23
  • 1
    $\begingroup$ 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). $\endgroup$ – Jaap Scherphuis May 20 at 6:00
  • $\begingroup$ 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. $\endgroup$ – Steve May 20 at 8:28
  • 2
    $\begingroup$ @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.) $\endgroup$ – loopy walt May 20 at 8:45
7
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Nice! I just noticed that this is effectively equivalent to Deusovi's answer! $\endgroup$ – justhalf May 20 at 17:36
4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – Steve May 20 at 10:18
  • 1
    $\begingroup$ what happens when $p$ is irrational? $\endgroup$ – Dmitry Kamenetsky May 20 at 10:19
  • 2
    $\begingroup$ @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! $\endgroup$ – Steve May 20 at 10:20
  • $\begingroup$ @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 $\endgroup$ – melfnt May 20 at 10:21
  • 1
    $\begingroup$ @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). $\endgroup$ – Steve May 20 at 10:43
1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Steve May 21 at 11:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Dmitry Kamenetsky May 21 at 11:36
  • $\begingroup$ @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}}$? $\endgroup$ – Hans-Peter Stricker May 21 at 11:55
  • $\begingroup$ @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... $\endgroup$ – Steve May 21 at 12:06

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.