Simulating an Unbiased Coin Toss Using a Biased Coin

Problem

Assume you have access to a function toss_biased() which returns 0 or 1 with a probability that’s not 50-50 (but also not 0-100 or 100-0). You do not know the bias of the coin.

Write a function to simulate an unbiased coin toss.

Examples

Example 1

1
2


Input: Call the function 10000 times
Output: About 5000 times 0, about 5000 times 1

Example 2

1
2


Input: Call the function once
Output: 0 (with 50% probability), 1 (with 50% probability)

Solution

Method 1 - Using Probability

To simulate an unbiased coin toss using a biased coin, we can use a clever trick that leverages pairs of results. Specifically, we can use the pair (0, 1) and (1, 0) to generate unbiased results. The idea is that these pairs are equally likely to occur, regardless of the bias of the original coin.

Here’s a step-by-step explanation and implementation:

Steps:

Generate pairs of outcomes: Call toss_biased() twice to get two outcomes.
Check pairs: If the outcomes are (0, 1), return 0. If the outcomes are (1, 0), return 1. Any other combination (i.e., (0, 0) or (1, 1)) is discarded and the process is repeated.

Explanation:

The probability of getting (0, 1) is ( P(0) \times P(1) ).
The probability of getting (1, 0) is ( P(1) \times P(0) ).

Since ( P(0) \times P(1) = P(1) \times P(0) ), these two events are equally likely, thus simulating an unbiased coin toss.

Code

1
2
3
4
5
6
7
8


int biasedCoin(); // returns 0 or 1 with unknown probability
int fairCoin() {
  while (true) {
    int a = biasedCoin();
    int b = biasedCoin();
    if (a != b) return a;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func biasedCoin() int { /* returns 0 or 1 with unknown probability */ }
func fairCoin() int {
  for {
    a := biasedCoin()
    b := biasedCoin()
    if a != b {
      return a
    }
  }
}

 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


import java.util.Random;


public class UnbiasedCoinToss {

	private Random rand = new Random();

	// Mocking the biased coin toss function for demonstration purposes
	public int tossBiased() {
		// For example, let's assume the coin has a 30% chance of returning 0 and 70% for 1
		return rand.nextDouble()<0.3 ? 0 : 1;
	}

	public int tossUnbiased() {
		while (true) {
			int firstToss = tossBiased();
			int secondToss = tossBiased();

			if (firstToss == 0 && secondToss == 1) {
				return 0;
			} else if (firstToss == 1 && secondToss == 0) {
				return 1;
			}
			// If we get (0,0) or (1,1), we ignore both results and toss again
		}
	}

	public static void main(String[] args) {
		// Testing the unbiased coin toss function
		int[] results = { 0, 0 };

		for (int i = 0; i < 10000; i++) {
			int result = tossUnbiased();
			results[result]++;
		}

		System.out.println("Unbiased toss results:");
		System.out.println("0: " + results[0]);
		System.out.println("1: " + results[1]);
	}
}

1
2
3
4
5
6
7
8


fun biasedCoin(): Int = /* returns 0 or 1 with unknown probability */
fun fairCoin(): Int {
  while (true) {
    val a = biasedCoin()
    val b = biasedCoin()
    if (a != b) return a
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


# Mocking the biased coin toss function for demonstration purposes
def toss_biased():
    # For example, let's assume the coin has a 30% chance of returning 0 and 70% for 1
    return 0 if random.random() < 0.3 else 1


def toss_unbiased():
    while True:
        first_toss = toss_biased()
        second_toss = toss_biased()

        if first_toss == 0 and second_toss == 1:
            return 0
        elif first_toss == 1 and second_toss == 0:
            return 1
        # If we get (0,0) or (1,1), we ignore both results and toss again


# Testing the unbiased coin toss function
results = {"0": 0, "1": 0}
for _ in range(10000):
    results[str(toss_unbiased())] += 1

print("Unbiased toss results:", results)

1
2
3
4
5
6
7
8


fn biased_coin() -> u8 { /* returns 0 or 1 with unknown probability */ }
fn fair_coin() -> u8 {
  loop {
    let a = biased_coin();
    let b = biased_coin();
    if a != b { return a; }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


function biasedCoin(): number {
  // returns 0 or 1 with unknown probability
  return Math.random() < 0.7 ? 0 : 1; // Example bias
}
function fairCoin(): number {
  while (true) {
    const a = biasedCoin();
    const b = biasedCoin();
    if (a !== b) return a;
  }
}

Complexity

⏰ Time complexity: O(1) , with an unknown constant dependent on the bias of the tossBiased() function. Each iteration has a 2p(1-p) chance of success, so expected number of iterations is constant.
🧺 Space complexity: O(1) — No extra space used.

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 - Using Probability#

Steps:#

Explanation:#

Code#

Complexity#