Qm
Brainteasers

A one-in-three choice from a fair coin

probabilityrandomnessrejection-sampling

Three friends want to choose one of themselves uniformly at random, each with probability exactly 1/3. All they have is a fair coin.

  1. How do they do it?
  2. On average, how many flips does your method use?
  3. Can it be done with a method that is guaranteed to finish in a fixed number of flips?
Show a hint

Two flips give four equally likely outcomes. Use three of them and throw the fourth away.

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Making a Fair Coin From a Biased OneThe Lost Boarding Pass ProblemThe Arcsine Law: Who Leads a Coin-Flip RaceBalls and Bins and the Birthday ProblemBertrand's Chord Paradox

Related questions

A fair decision from a biased coinFrom an hour to half an hourAnts on a triangleWhy so many numbers start with 1A random chord longer than the side of the triangle
All questions →