undefined | Better HN

0 pointsms_menardi1d ago0 comments

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

0 comments

susam1d ago

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.

taegee1d ago

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

susam8h ago

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)

clickety_clack16h ago

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

cdaringe18h ago

Thats how i noodled thru it internally

aws_ls1d ago

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

taegee1d ago

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

sporkland20h ago

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.

dash220h ago

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.

pyuser58318h ago

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

throwaway898651d ago

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

j / k navigate · click thread line to collapse

0 comments

susam1d ago

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.

taegee1d ago

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

susam8h ago

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)

clickety_clack16h ago

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

cdaringe18h ago

Thats how i noodled thru it internally

aws_ls1d ago

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.

taegee1d ago

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

sporkland20h ago

dash220h ago

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.

pyuser58318h ago

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

throwaway898651d ago

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

j / k navigate · click thread line to collapse