# Generate Fair Results From A Biased Coin

Also saw from *Techie Delight* [1]

Given a biased coin with the probability of p to be head on each toss, where 0 < p < 1 and p ≠ 0.5, generate fair results from the biased coin.

Wikipedia [2] also explains the solution to this problem. The following texts comes from wiki:

- Toss the coin twice.
- If the results match, start over, forgetting both results.
- If the results differ, use the first result, forgetting the second.

This works because if we toss twice, the probability of HEAD-TAIL and TAIL-HEAD
are both *p(1-p)*. So we can ignore the case of HEAD-HEAD and TAIL-TAIL and use
only HEAD-TAIL and TAIL-HEAD, which are fair results coming from the biased
coin.

The following solution is implemented in Go.

```
package main
import (
"math/rand"
"time"
)
var r *rand.Rand // Rand for this package.
type RESULT int
const (
HEAD RESULT = iota
TAIL
)
func BiasedCoin() RESULT {
p := 30 // p = 0.3 to be HEAD on each toss
if r.Intn(100) < p {
return HEAD
} else {
return TAIL
}
}
func Fair() RESULT {
for {
r1 := BiasedCoin()
r2 := BiasedCoin()
if r1 != r2 {
return r1
}
}
}
func init() {
r = rand.New(rand.NewSource(time.Now().UnixNano()))
}
func main() {
m := make(map[RESULT]int)
m[HEAD] = 0
m[TAIL] = 0
for i := 0; i < 100000; i++ {
m[Fair()] += 1
}
for r, count := range m {
print(r)
print(" : ")
println(count)
}
}
```

One of the outputs run on my desktop:

```
0 : 50021
1 : 49979
```

Tested on: `Ubuntu Linux 17.10`, `Go 1.10.1`.

References:

[1] | Generate Fair Results from a Biased Coin - Techie Delight |

[2] | Fair results from a biased coin - Wikipedia |

[3] | Generate Any One of Given Numbers According to Given Probabilities |