In this post, we will discuss how to generate fair results from a biased coin which prefer one side of the coin over another, and returns `TAILS` with `p` probability and `HEADS` with `(1-p)` probability where `p != (1-p)`.

We can use the given biased coin for fair results by making two calls from biased coin instead of one call. Then if the results of both calls match (both are `HEADS`, or both are `TAILS`), we discard the results, and start over. If the results differ, we consider the first result.

##### How this works?

Suppose we have `biased()` function that returns `TAILS` with `p`

probability and `HEADS` with `1-p`

probability. We make two independent subsequent calls to the `biased()` and store the results. Then there are four possible possibilities:

- Probability that both calls returns
`TAILS`=`p * p`

- Probability that both calls returns
`HEADS`=`(1 - p) * (1 - p)`

- Probability that first call returns
`TAILS`, and the second call returns`HEADS`=`p * (1 - p)`

- Probability that first call returns
`HEADS`, and the second call returns`TAILS`=`(1 - p) * p`

Clearly, the biased coin has same probability of getting `TAILS` and then `HEADS` as the probability of getting `HEADS` and then `TAILS`. So if we exclude the events of two `HEADS` and two `TAILS` by repeating the procedure, we’re left with the only two remaining outcomes having equivalent probability. That’s the reason why we will get a fair result.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <stdio.h> #define HEADS 1 #define TAILS 0 // Biased function that returns TAILS with p probability and // HEADS with (1-p) probability int biased() { int p = 80; // generate random number between 0-99, both inclusive int r = rand() % 100; // return TAILS if we got number between [0-79], else return HEADS return (r <= 79)? TAILS: HEADS; } // Return HEADS and TAILS with equal probability using the specified function int generate() { while (1) { int first = biased(); int second = biased(); if (first != second) return first; // or return second } } // Program to generate fair results from a biased coin int main(void) { // initialize srand with distinctive value srand(time(NULL)); int x = 0, y = 0; for (int i = 0; i < 100000; i++) { int val = generate(); (val == 0) ? x++ : y++; } printf("0 ~ %f%\n1 ~ %f%%", x/1000.0, y/1000.0); return 0; } |

`Output (will vary): `

HEADS ~ 50.237000%

TAILS ~ 49.763000%

**References: ** https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply