# 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:

1. Toss the coin twice.
2. If the results match, start over, forgetting both results.
3. 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.

Run Code on Go Playground

```package main

import (
"math/rand"
"time"
)

var r *rand.Rand // Rand for this package.

type RESULT int

const (
TAIL
)

func BiasedCoin() RESULT {
p := 30 // p = 0.3 to be HEAD on each toss
if r.Intn(100) < p {
} 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[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: