Fair Coin Toss

Suppose you are the referee of a football game (whether it is the NFL or the EPL) and you are asked to toss a coin to determine which team chooses which side etc. Most coins are slightly biased so how do you use a flawed coin to generate a perfectly fair event, i.e., an event with probability 1/2? Here is a procedure that will work. In theory it is not finite and could go on forever, but probability theory tells us that the chance is very high that the procedure will terminate in a few steps.

So what is the method? Suppose your coin is biased towards Heads with probability α\alpha. So the probability of Tails is 1−α1 - \alpha. Here α\alpha is any real number between 0 and 1. Then perform the following procedure: Toss the coin twice. Of the four outcomes, HH, HT, TH, TT, only HT and TH are considered valid outcomes. Note that by the independence of the Bernoulli trials that is tossing a coin, the probability of tossing HT is α⋅(1−α)\alpha\cdot (1 - \alpha) while the probability of tossing TH is (1−α)⋅α(1 - \alpha)\cdot \alpha which is exactly the same! So we narrow our sample space to these two equally likely events and that represents probability 1/2 each.

What if we tossed HH or TT instead? Then discard the outcome and start over i.e., toss the coin two more times. If we regard a "successful" experiment as one that yields one of HT or TH, then the probability of a successful experiment is 2α(1−α)2\alpha(1- \alpha) while the probability of failure is α2+(1−α)2\alpha^2 + (1 - \alpha)^2. So, on average, how many tries before we conclude our experiment successfully? This is given by the expected value of the geometric distribution where we keep keep tossing the coin twice until we succeed. The expected value is 12α(1−α)\frac{1}{2 \alpha (1 - \alpha)}. This could be large is α\alpha is small; for example, if α=0.1\alpha = 0.1, then this expected value is around 5.55 i.e., closer to 6 double tosses. But for most reasonable coins, this will be close to 2 or 3.

So next time you need to decide something fair, you know what to do!

Note by Krishnan Shankar
6 years, 1 month ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...