Hacker News Reader

Comment by ms_menardi | Hacker News Reader

> There is the Von Neumann method of generating an unbiased coin from a biased coin. Of throwing it twice, and checking if you got HT or TH. And completely discarding all HH or TT results. It doesn't matter if the coin you are using is 20% or 80%, the result will be a true 50/50.

This blew my mind. Thank you!

I had to think about it a bit, so for anyone scratching their head right now trying to figure it out, consider it this way:

what matters is the ordering, of heads-then-tails, or tails-then-heads.

It doesn't matter that it's biased one way or the other, if you keep flipping pairs until you get a result with two different values, it's a 50/50 chance whether the less-likely result comes first, or second.

You might only have a 20% chance of any particular pair having a tails (for example), but in the cases where you do have a tails, it's a 50/50 chance that it comes first or second.

View on HN

And for people who like equations, here is my attempt at explaining it.

Assume each flip is independent and the bias remains same in each flip.

Let

  P(H) = p,
  P(T) = 1 - p.

Then

  P(HH) = p^2,
  P(HT) = p(1 - p),
  P(TH) = (1 - p)p,
  P(TT) = (1 - p)^2.

Therefore

  P(HT or TH) = 2p(1 - p).

Now calculate

  P(HT | HT or TH) = p(1 - p) / (2p(1 - p)) = 1/2,
  P(TH | HT or TH) = (1 - p)p / (2p(1 - p)) = 1/2.

You don't need conditional probability here, as the flips are independent.

It's just p(H)p(T).

And p(H)p(T) = p(T)p(H), thus 2*p(H)p(T) = 2p(1-p).

Thats how i noodled thru it internally

That wasn’t what he was trying to prove, but the proof could be done without conditionals like this:

If: p(H)p(T) = p(T)p(H)

And: p(H)p(T) + p(T)p(H) = 1

Then: p(H)p(T) = p(T)p(H) = 0.5

Independence tells us how to compute the probability of a sequence like HT or TH:

  P(HT) = P(H)P(T) = p(1 - p)

But the question I am addressing is not just "what is the probability of HT?" It is "given that the two flips are different, what is the probability that the order was HT rather than TH?"

That is a conditional probability:

  P(HT | HT or TH)

Afaics it's just basic commutativity – p(H)p(T) = p(T)p(H) – since instances are independent.

Same, of course, holds for flipping it multiple times. But there you get more than Head or Tail (binomnk(n, k)).

Thanks for your explanation. I did not get it in the first read, and was too lazy to think, until saw your comment.

Just want to point out, that one is actually doing the experiment with a biased coin, then one must ignore all pairs.

e.g in case a coin which is heavily biased, say .9 H and .1 T. One should start with ignoring all the HH pairs, and start only at odd index. Lest, one picks a value like HHHHT (in the case the 2nd HH pair was not skipped, instead they greedily picked up the first HT, which will make the experiment HT biased).

I was doubting this for a minute as I wondered with a significantly biased coin towards the head side would you be more likely to get HT. With probability problems like Monty Hall I like to think about extreme cases like say it's 99 heads to every 1 tails. You'd expect HT 0.99% of the time. Ditto TH.

You can’t flip coins until you get the first different outcome… You have to flip twice each time, until you get a pair with different outcomes.

Oh wow that’s really amazing. What’s the source - I love Von Neumann.

Not very random if it's only TH or HT. Trivial to brute force with no more than two tries!

Reply on news.ycombinator.com