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.

Run Code on Go Playground

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