Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Creating fair dice from random objects

arstechnica.com

Post reply on HN
Print view View original

21–28 of 28 posts

Re: Creating fair dice from random objects

#21

Post by gametorch »

stevage wrote: post #7
orlp wrote: post #6

How to create a fair coin from an arbitrarily biased coin: 1. Toss the coin and remember the answer. 2. Toss the coin again, if it is different from your previous toss then your result from #1 is fair. Otherwise, go back to step 1. If p is the probability of getting heads, there are four possible outcomes with their associated probabilities: TT -> (1 - p)^2 (rejected) HT -> p * (1 - p) TH -> (1 - p) * p TT -> p^2 (re…

That's cute. intuitively, if two flips give different outcomes, it's fifty/fifty which would be first.

But also, you might have to flip the coin an arbitrarily large number of times before you get a "heads tails" or "tails heads" roll (if I can arbitrarily pick how biased the coin is).

Re: Creating fair dice from random objects

#22

Post by minikomi »

orlp wrote: post #6

How to create a fair coin from an arbitrarily biased coin: 1. Toss the coin and remember the answer. 2. Toss the coin again, if it is different from your previous toss then your result from #1 is fair. Otherwise, go back to step 1. If p is the probability of getting heads, there are four possible outcomes with their associated probabilities: TT -> (1 - p)^2 (rejected) HT -> p * (1 - p) TH -> (1 - p) * p TT -> p^2 (re…

1. flip the coin until it lands on its edge.

2. the person who achieves this is the winner.

Re: Creating fair dice from random objects

#23

Post by ncruces »

svat wrote: post #11
stevage wrote: post #8

Earlier quoted context omitted.

And yet the person you replied to was quite clear that they are responding to the title.

That isn't the title either: the title is “Creating fair dice from random objects”, while what they are responding to may be something like “Creating fair coins from biased coins”. So they're only responding to the “Creating fair _ from _” part of the title. Responding to three out of six words in the title isn't bad I guess.

> and this trivially extends to constructing a fair N-sided die out of any arbitrarily biased die for any N

They wrote something interesting, even if it only tangentially matches the topic.

Pointing out that it doesn't exactly match the topic also adds to the conversation, I guess, but I think we've now exhausted any interest (so I won't be arguing further).

Re: Creating fair dice from random objects

#24

Post by nullc »

orlp wrote: post #6

How to create a fair coin from an arbitrarily biased coin: 1. Toss the coin and remember the answer. 2. Toss the coin again, if it is different from your previous toss then your result from #1 is fair. Otherwise, go back to step 1. If p is the probability of getting heads, there are four possible outcomes with their associated probabilities: TT -> (1 - p)^2 (rejected) HT -> p * (1 - p) TH -> (1 - p) * p TT -> p^2 (re…

VN extrator is a specific case of a more general idea: When you independently (hard assumption of VN extractor) draw M times with N possibilities then you can extract entropy from their permutation.

Assign some scheme for converting permutations to an index.

Then get uniform bits out, maintain two variables: one is the product of the number of permutations, the other gets multiplied by the number of permutations and the index added. Whenever the number of possibilities is divisible by two, output the LSB of the index accumulator and halve the number of possibilities.

Size up your groups and accumulators and you can get arbitrarily high extraction rates.

Doing it efficiently and in constant time (e.g. without divisions) is the more exciting trick. A colleague and I managed an extractor for the binary case that packs takes 10+3N multiplies and N CTZs to pack N bits (giving an exact invertible encoding when bits choose ones is < 2^64).

Re: Creating fair dice from random objects

#25

Post by IAmBroom »

gerdesj wrote: post #13
orlp wrote: post #6

How to create a fair coin from an arbitrarily biased coin: 1. Toss the coin and remember the answer. 2. Toss the coin again, if it is different from your previous toss then your result from #1 is fair. Otherwise, go back to step 1. If p is the probability of getting heads, there are four possible outcomes with their associated probabilities: TT -> (1 - p)^2 (rejected) HT -> p * (1 - p) TH -> (1 - p) * p TT -> p^2 (re…

"arbitrarily" is doing some heavy lifting! I'm not sure that two concurrent harmonious answers constitutes a "fixed" coin or a diagnosis of a fixed coin. This scheme will be rubbish with a one sided coin ie the limit for "arbitrary fixed coin".

How is that "heavy lifting"? It's perfectly reasonable for any real-world "coin".

Re: Creating fair dice from random objects

#26

Post by IAmBroom »

stevage wrote: post #7
orlp wrote: post #6

How to create a fair coin from an arbitrarily biased coin: 1. Toss the coin and remember the answer. 2. Toss the coin again, if it is different from your previous toss then your result from #1 is fair. Otherwise, go back to step 1. If p is the probability of getting heads, there are four possible outcomes with their associated probabilities: TT -> (1 - p)^2 (rejected) HT -> p * (1 - p) TH -> (1 - p) * p TT -> p^2 (re…

That's cute. intuitively, if two flips give different outcomes, it's fifty/fifty which would be first.

You are assuming an unbiased coin.

Imagine I glue a poker chip to a washer. There's a clear bias in the outcome of this "coin".

This method resolves that bias.

Re: Creating fair dice from random objects

#27

Post by IAmBroom »

gametorch wrote: post #21
stevage wrote: post #7

Earlier quoted context omitted.

That's cute. intuitively, if two flips give different outcomes, it's fifty/fifty which would be first.

But also, you might have to flip the coin an arbitrarily large number of times before you get a "heads tails" or "tails heads" roll (if I can arbitrarily pick how biased the coin is).

The opening scene of "Rosencrantz and Guildenstern Are Dead" springs to mind.

And that coin wasn't even biased... although Tom Stoppard was a confounding factor.

Re: Creating fair dice from random objects

#28

Post by stevage »

IAmBroom wrote: post #26
stevage wrote: post #7

Earlier quoted context omitted.

That's cute. intuitively, if two flips give different outcomes, it's fifty/fifty which would be first.

You are assuming an unbiased coin. Imagine I glue a poker chip to a washer. There's a clear bias in the outcome of this "coin". This method resolves that bias.

I understood perfectly already.
Post reply on HN