Collaborative coin flipping

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.

This entry was posted in Numbers are hard on by .