5 ms·

Creating fair dice from random objects

40 points by epipolar 1y ago

gametorch 1y ago
the title is a classic quant interview problem the basic idea is that, because multiplication commutes, probability of A then B is the same as probability of B then A, so long as they are independent events (rolling objects typically meets this criteria) so instead of using just A or just B, which might neither have 0.5 probability, you only count "A then B" and "B then A" as rolls and this trivially extends to constructing a fair N-sided die out of any arbitrarily biased die for any N
- ted_dunning 1y ago
  That isn't what the article is about at all. It's not even what the first paragraph is about. What they are doing is designing physical shapes that will have a specified probability of falling in different positions. What you are talking about is post processing a biased random signal to get a less biased signal.
  - gametorch 1y ago
    just providing a comment I thought was interesting and kind of relevant wasn't trying to hurt anyone or anything
  - stevage 1y ago
    And yet the person you replied to was quite clear that they are responding to the title.
    - svat 1y ago
      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.
      - ncruces 1y ago
        > 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).
- ethan_smith 1y ago
  This technique is formally known as the Von Neumann extractor (1951), a foundational concept in randomness extraction.
  - deleted 1y ago
    [deleted]
deleted 1y ago
[deleted]
pixelpoet 1y ago
Hey hey, it's Keenan Crane again :)
- godelski 1y ago
  For those that don't know, he is a HIGHLY respected researcher and well known for effectively communicating complex topics. He really makes it fun. Often as visually entertaining as 3B1B while diving into more depth. I'd highly recommend people poke through his site and YouTube channel https://www.cs.cmu.edu/~kmcrane/ https://www.cs.cmu.edu/~kmcrane/ https://www.youtube.com/user/keenancrane https://www.youtube.com/user/keenancrane https://x.com/keenanisalive?lang=en https://x.com/keenanisalive?lang=en
orlp 1y ago
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 (rejected) Needless to say, p * (1 - p) and (1 - p) * p have an equal probability, so if we don't reject our two tosses, we have a fair outcome.
- stevage 1y ago
  That's cute. intuitively, if two flips give different outcomes, it's fifty/fifty which would be first.
  - gametorch 1y ago
    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).
    - IAmBroom 1y ago
      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.
  - IAmBroom 1y ago
    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.
    - stevage 1y ago
      I understood perfectly already.
- 1y ago
derbOac 1y ago
The question I have is how stable are the probabilities over time? My guess is traditional dice are more physically robust to wear and degrade more gracefully.
zzo38computer 1y ago
It does not seem to be so useful and practical to use strange shapes for dice; the common shapes, with numbers (or other symbols that are applicable for the game you are playing) on each side, will probably be more useful, anyways. However, it might be interesting. Another reason to use dice for tabletop games is so that the game can be played without the use of a computer. When I play GURPS, I generally use different dice with each dice roll in order to try to mitigate some of the bias. (I don't know quite how much effective this really is, though.)
archimedis 1y ago
The Roman rock crystal icosahedron die in the Louvre would be nice: https://archimedes-lab.org/2021/07/15/amazing-roman-rock-crystal-icosahedron-die/ https://archimedes-lab.org/2021/07/15/amazing-roman-rock-cry...
- IncreasePosts 1y ago
  The linked oracle site has a 6mb of marble for a background. Yowza!
blurbleblurble 1y ago
Keenan Crane is legendary

40 points by epipolar 1y ago

the title is a classic quant interview problem the basic idea is that, because multiplication commutes, probability of A then B is the same as probability of B then A, so long as they are independent events (rolling objects typically meets this criteria) so instead of using just A or just B, which might neither have 0.5 probability, you only count "A then B" and "B then A" as rolls and this trivially extends to constructing a fair N-sided die out of any arbitrarily biased die for any N

ted_dunning 1y ago
That isn't what the article is about at all. It's not even what the first paragraph is about. What they are doing is designing physical shapes that will have a specified probability of falling in different positions. What you are talking about is post processing a biased random signal to get a less biased signal.
- gametorch 1y ago
  just providing a comment I thought was interesting and kind of relevant wasn't trying to hurt anyone or anything
- stevage 1y ago
  And yet the person you replied to was quite clear that they are responding to the title.
  - svat 1y ago
    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.
    - ncruces 1y ago
      > 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).
ethan_smith 1y ago
This technique is formally known as the Von Neumann extractor (1951), a foundational concept in randomness extraction.
- deleted 1y ago
  [deleted]

deleted 1y ago

[deleted]

pixelpoet 1y ago

Hey hey, it's Keenan Crane again :)

godelski 1y ago
For those that don't know, he is a HIGHLY respected researcher and well known for effectively communicating complex topics. He really makes it fun. Often as visually entertaining as 3B1B while diving into more depth. I'd highly recommend people poke through his site and YouTube channel https://www.cs.cmu.edu/~kmcrane/ https://www.cs.cmu.edu/~kmcrane/ https://www.youtube.com/user/keenancrane https://www.youtube.com/user/keenancrane https://x.com/keenanisalive?lang=en https://x.com/keenanisalive?lang=en

orlp 1y ago

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 (rejected) Needless to say, p * (1 - p) and (1 - p) * p have an equal probability, so if we don't reject our two tosses, we have a fair outcome.

stevage 1y ago
That's cute. intuitively, if two flips give different outcomes, it's fifty/fifty which would be first.
- gametorch 1y ago
  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).
  - IAmBroom 1y ago
    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.
- IAmBroom 1y ago
  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.
  - stevage 1y ago
    I understood perfectly already.
1y ago

derbOac 1y ago

The question I have is how stable are the probabilities over time? My guess is traditional dice are more physically robust to wear and degrade more gracefully.

zzo38computer 1y ago

It does not seem to be so useful and practical to use strange shapes for dice; the common shapes, with numbers (or other symbols that are applicable for the game you are playing) on each side, will probably be more useful, anyways. However, it might be interesting. Another reason to use dice for tabletop games is so that the game can be played without the use of a computer. When I play GURPS, I generally use different dice with each dice roll in order to try to mitigate some of the bias. (I don't know quite how much effective this really is, though.)

archimedis 1y ago

The Roman rock crystal icosahedron die in the Louvre would be nice: https://archimedes-lab.org/2021/07/15/amazing-roman-rock-crystal-icosahedron-die/ https://archimedes-lab.org/2021/07/15/amazing-roman-rock-cry...

IncreasePosts 1y ago
The linked oracle site has a 6mb of marble for a background. Yowza!

blurbleblurble 1y ago

Keenan Crane is legendary