4

Problem: Let's say you have a coin that might be (you don't know how biased, or even whether biased in the first place) biased, and you want to come up with a way to simulate an unbiased flip.

My reasoning (took me a few steps to get here but I'll spare you the struggle) is that no matter how biased the coin is, the probability of observing HT is the same as the probability of observing TH (assuming P(H) and P(T) are independent).

So we can assign for example H to HT and T to TH, and just wait for either sequence to take place.

I think that makes sense, but my intuition has been proven wrong so many times in the past that I really want to make sure my reasoning here is correct.

I'm also very interested to hear other ways to think about this and other kinds of intuition for this idea.

EDIT: Based on @Mariuslp's answer, I'd like to understand why we can't use a "sliding window", meaning why we have to toss away the first two flips if neither HT nor TH happens.

From my comment to his answer: The way I think about it, the probability of the entire sequence that happens before either HT or TH is the same for either HT or TH since P(H) and P(T) are independent, so it shouldn't matter. What's the problem with my thinking?

jeremy radcliff
  • 4,805
  • 2
    Your method works. In fact, it is generally attributed to John von Neumann...see, e.g.,this for some discussion. – lulu Jan 24 '17 at 23:32
  • 1
    It doesn't work if you toss the coin until you get either HT or TH (this is still biased since if you do it this way it really only comes down to the first throw). You need to toss the coin twice, and redo it if you get two equals. In other words, HHT should not count as HT, but rather as just a T, waiting for a H. – Arthur Jan 25 '17 at 00:05
  • @Arthur, got it, thanks. Glad I checked...I can't remember a single time my intuition was 100% correct, hah. – jeremy radcliff Jan 25 '17 at 00:32

1 Answers1

2

As mentioned in the link provided by @lulu, you can't use a sliding window when looking at your pairs: if the two first tosses give TT, you have to discard both outputs, and toss the coin twice again.

Assume that you just concatenate your results like so: HTTTHHHTHHTHHTHT..., and look at the first valid pair (this is using a sliding window).

  • HT is the first valid output if and only if the first output of the series is H.
  • TH is the first valid output if and only if the first output of the series is T.

As a result, using a sliding window will not change the bias of the coin.

However, this caveat is avoided when you discard all incorrect pairs of tosses.

Mariuslp
  • 824
  • Can you explain why that is the case? Meaning why you can't use a sliding window? The way I think about it, the probability of the entire sequence that happens before either HT or TH is the same for either sequence, so it shouldn't matter. What's the problem with my thinking? – jeremy radcliff Jan 25 '17 at 00:12
  • If your sequence starts with a T, then the next toss will either give an incorrect pair (TT), or a valid result (TH). If the result is valid, we stop, otherwise we continue. The next toss will either give an invalid result (TT), or a valid result (TH). And so on. You can see that the first valid result will be TH, as all letters before the first H are all T's. The same applies if the first letter is H. – Mariuslp Jan 25 '17 at 00:18
  • sorry, I may be misunderstanding but in your answer you make it sound like if you get TT, you should throw the coin twice again and forget completely about the TT. But in your comment, I understand (my bad if this is wrong) that if you get TT you can throw again and if you get a H for a sequence of TTH, then that would be considered a valid result of TH. – jeremy radcliff Jan 25 '17 at 00:22
  • Sorry, in my comment I talked about what happens when you use a sliding window. The result is that, with a sliding window, everything boils down to the probability of the first letter. Which is not what you want. Without sliding window, you toss every precedent result, so the probability of getting HT is the same as the one getting TH. – Mariuslp Jan 25 '17 at 00:25
  • Ah....I got it, finally. Thank you for being patient. – jeremy radcliff Jan 25 '17 at 00:31
  • No problem! Glad to help. – Mariuslp Jan 25 '17 at 00:33
  • @ Marius: I try to understand why the generated coin is fair, i.e why, by this mechanism the probability of landing HT (which means heads) is 1/2? Do I miss something? – noob-mathematician Apr 25 '19 at 14:27
  • @noob-mathematician: the probability of obtaining HT is not 1/2, but what matters is that it's equal to the probability of obtaining TH. Sure, you may also obtain TT or HH with some probability, but you'll just dismiss these results. In the end, you'll get, say, HT 10% of the time, TH 10% of the time, and garbage 80% of the time. What matters is that p(HT) = p(TH). So if we look at valid outcomes of the experience, we get that a valid outcome is HT 50% of the time, and TH 50% of the time. Hence the fair coin. – Mariuslp Apr 27 '19 at 20:27