This post is based on an answer from Paul Crowley to a question I asked on Twitter. I’m writing it up mostly for my notes and because I had a follow up question about it I wanted to answer.
You and I want to decide something by coin toss. But there’s a problem. You see, I don’t trust your coin and you don’t trust my coin.
How do we resolve this issue?
Simple: We each flip our coins. If the results come up the same, call that heads. If the results come up different, call that tails.
Theorem: If at least one of us is using a fair coin, the result is fair.
Proof:
Without loss of generality, suppose I have a fair coin.
P(Heads) = P(Heads|You flip tails) * P(you flip tails) + P(Heads|You flip heads) * P(you flip heads)
But each of these conditional probabilities is \(\frac{1}{2}\) because they’re just the probability that I flip tails and heads respectively. So
P(Heads) = \(\frac{1}{2}\)(P(you flip tails) + P(you flip heads)) = \(\frac{1}{2}\) as desired.
QED
Simple enough.
The follow up question I wanted to ask though: What happens if we both cheat?
Suppose I’m flipping heads with probability \(p\) and you’re flipping heads with probability \(q\). Then \(P(Heads) = pq + (1 – p)(1 – q)\).
Supposing I want to maximize the probability of getting a heads. Let \(f(p) = pq + (1 – p)(1 – q) = 1 – q + (2q – 1)p \). If I don’t know the value of \(q\) (or at least which side of \(\frac{1}{2}\) it’s on) there’s not much I can do here: Any choice of \(p\) I make might hurt my odds rather than help them. If I do know whether \(q > \frac{1}{2}\) or not then I can choose \(p \in \{0,1\}\) to get \(P(\mathrm{Heads}\) = \mathrm{max}(q, 1-q)\). It’s unclear to me exactly what the game theory here is, but it does suggest that if you think that I am able to predict your value of \(q\) then your best choice is to use a fair coin.