Getting a fair result with an unfair coin

How can you get a fair coin toss if someone hands you a coin that is weighted to come up heads more often than tails?

💡Strategies for Solving This Problem

The Classic Probability Puzzle

This came up in my Google interview. It's not about coding - it's about thinking probabilistically. But you can implement it, which is what they asked me to do.

The Problem

You have a biased coin (unknown probability p of heads). How do you generate a fair 50/50 result?

The Insight (von Neumann's Trick)

Flip the coin twice:

HT → return "heads" (probability: p × (1-p))
TH → return "tails" (probability: (1-p) × p)
HH or TT → try again

Since p × (1-p) = (1-p) × p, the outcomes HT and TH are equally likely!

Why It Works

Even though the coin is biased, the probability of HT equals the probability of TH. By mapping HT to "heads" and TH to "tails", we get a fair result.

Expected flips: 1/(2p(1-p)). For p=0.5 (fair coin), this is 2 flips. For extreme bias (p near 0 or 1), it could be many flips.

What My Interviewer Asked

"Explain why it works" (probability argument)
"What if the coin lands the same both times?" (retry)
"What's the expected number of flips?" (depends on p)
"Implement it" (code below)

✅Solution

Solution: von Neumann Extractor

// Simulated biased coin (you'd have actual coin in real scenario)
function biasedCoin(p = 0.7) {
    return Math.random() < p ? "H" : "T";
}

function fairResult(coinFlip = biasedCoin) {
    while (true) {
        const flip1 = coinFlip();
        const flip2 = coinFlip();

        if (flip1 === "H" && flip2 === "T") {
            return "Heads";
        }

        if (flip1 === "T" && flip2 === "H") {
            return "Tails";
        }

        // HH or TT - try again
    }
}

// Test with biased coin (p=0.7)
function testFairness(trials = 10000) {
    let heads = 0;

    for (let i = 0; i < trials; i++) {
        if (fairResult(() => biasedCoin(0.7)) === "Heads") {
            heads++;
        }
    }

    console.log(`Heads: ${heads}/${trials} (${(heads/trials * 100).toFixed(2)}%)`);
    // Should be close to 50%, even with biased coin!
}

testFairness();
// Output: Heads: 5012/10000 (50.12%)

Why This Works: Math Proof

Let p = probability of heads on biased coin.

For two flips:

P(HT) = p × (1-p)
P(TH) = (1-p) × p
P(HH) = p × p = p²
P(TT) = (1-p) × (1-p) = (1-p)²

Given we get different outcomes (HT or TH):

P(HT | different) = p(1-p) / [p(1-p) + (1-p)p] = 1/2
P(TH | different) = (1-p)p / [p(1-p) + (1-p)p] = 1/2

Perfect 50/50 split!

Expected Number of Flips

function expectedFlips(p) {
    // Probability we get different results in 2 flips
    const pDifferent = 2 * p * (1 - p);

    // Expected pairs of flips until success
    const expectedPairs = 1 / pDifferent;

    // Total flips = pairs × 2
    return expectedPairs * 2;
}

console.log(expectedFlips(0.5));   // 2.0 (fair coin)
console.log(expectedFlips(0.7));   // 4.76
console.log(expectedFlips(0.9));   // 11.11 (very biased!)

Optimized Version (Fewer Flips)

You can extract more than one fair bit per round:

function fairResultOptimized(coinFlip = biasedCoin) {
    // Can extract multiple fair bits from one round
    // This is more complex but uses fewer flips on average

    while (true) {
        const flip1 = coinFlip();
        const flip2 = coinFlip();

        if (flip1 !== flip2) {
            return flip1 === "H" ? "Heads" : "Tails";
        }

        // Could continue extracting more bits here
        // Advanced: Peres extraction method
    }
}

Real-World Applications

This isn't just theoretical:

Cryptographic random number generation
Removing bias from physical random sources
Fair leader election with biased channel

Follow-Up: Generate 0.25 Probability

My interviewer asked: "What if you want 25% probability?"

function generateQuarter(coinFlip = biasedCoin) {
    // Use fairResult twice to get 4 equally likely outcomes
    const bit1 = fairResult(coinFlip) === "Heads" ? 0 : 1;
    const bit2 = fairResult(coinFlip) === "Heads" ? 0 : 1;

    // 00 = 25%, return true
    // 01, 10, 11 = 75%, return false
    return bit1 === 0 && bit2 === 0;
}

Interview tip: This problem tests probability thinking more than coding. Make sure you can explain the math clearly.