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.

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:

  1. Generate pairs of outcomes: Call toss_biased() twice to get two outcomes.
  2. 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

Java
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]);
	}
}
Python
import random


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

Complexity

  • ⏰ Time complexity: O(1) , with an unknown constant dependent on the bias of the tossBiased() function.
  • 🧺 Space complexity: O(1)