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

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 .