Are two heads better than one?

Summary

You’re playing a game with your lying friends Alice and Bob. Bob flips a coin and shows it to Alice. Alice tells you what she saw - but she lies 20% of the time. Then you take your best guess on whether the coin is heads or tails. Your best strategy is to trust whatever Alice says. You’re right 80% of the time. Now Bob joins in. He makes up his mind independent of Alice, and he also lies 20% of the time 1. 1Your friends are all liars! You were right 80% of the time by trusting Alice. How much better can you do with Bob’s help? Here’s some empty space for you to think I’m going to give you the answer below. So here’s some empty space for you to think in case you want to do the math yourself. Alright, let’s do some math The answer is 0% - you don’t do any better! You’re still exactly 80% to get the right answer. To establish this, let’s write a simple simulation. We’ll flip a coin a million times, ask our friends what they saw, and observe the results. For our strategy, we’ll look at a fact pattern (like “Alice says heads”), figure out what’s most likely (“the coin is heads”), and say “we guess the coin flip correctly whenever the most likely outcome occurs for this fact pattern” 2. 2“Guess the most likely outcome” is optimal here, but it is very much not optimal if this game was adversarial. It’s important that Alice and Bob aren’t trying to trick us and that they’re deciding independently. Here’s the code for that simulation. We’ll start with the easy case (just Alice): The simulation code from random import random from collections import defaultdict table = defaultdict(lambda: [0, 0]) LYING_PROB = 0.2 LYING_FRIENDS = ["Alice"] ITERATIONS = 1_000_000 for _ in range(ITERATIONS): is_heads = random() > 0.5 keys = [] for lying_friend in LYING_FRIENDS: lied = random() < LYING_PROB answer = None if is_heads: answer = "T" if lied else "H" else: answer = "H" if lied else "T" keys.append(f"{lying_friend[0]}:{answer}") key = ", ".join(keys) table_idx = 0 if is_heads else 1 ta...