24 ms·

Reminds me of the Von Neumann method of using a biased coin to generate unbiased random coin flips: http://web.eecs.umich.edu/~qstout/abs/AnnProb84.html http://

• eru 10y ago
  There's a nice way to extend von Neumann's basic idea naturally to the most efficient extractor: http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf
• cvwright 10y ago
  Cool. But note that this is not a problem that you're likely to run into in practice. Nolan and Gelman claim that you can't actually bias a coin. http://www.stat.berkeley.edu/~nolan/Papers/dice.pdf http://www.stat.berkeley.edu/~nolan/Papers/dice.pdf
  • paulgerhardt 10y ago
    How to create an unfair coin and prove it with math: https://izbicki.me/blog/how-to-create-an-unfair-coin-and-prove-it-with-math.html https://izbicki.me/blog/how-to-create-an-unfair-coin-and-pro...
    • babuskov 10y ago
      > Amazingly, it takes some pretty big bends to make a biased coin. It’s not until coin 3, which has an almost 90 degree bend that we can say with any confidence that the coin is biased at all. Basically, it proves that creating a biased coin really is impossible.
      • andreasvc 10y ago
        It is impossible by bending. It's probably still possible (not to say practical) by crafting a coin with a hidden compartment of a heavier metal.
        • morinted 10y ago
          From the paper linked above: one cannot, for example, weight a coin so that it is substantially more likely to land “heads” than “tails” when flipped and caught in the hand in the usual manner. Coin tosses can be biased only if the coin is allowed to bounce or be spun rather than simply flipped in the air.
        • babuskov 10y ago
          The paper states that this would only alter the center of mass. If you catch the coin or it lands on a soft surface, it has no effect, because the outcome is determined by the time when it stops. If you allow it to bounce, then yes. TL;DR: if you want unbiased coin IRL, make sure you catch it before it hits the ground.
  • j2kun 10y ago
    "Coin" is a metaphor in mathematics for any process with a binary outcome (a binary random variable, so to speak). These things exist in practice everywhere.
• bandrami 10y ago
  That was on the final of my Stochastic Processes class back in the Pleistocene. I just took the easy way and used system theory: find a system with a transfer function that is the inverse of the power spectral density of the autocorrelation function for the biased coin (Mason's rule guarantees this is possible, if sometimes impractical even in theory), and run the output through that system. Interestingly the prof emailed me the next semester because that had caught his attention and he had worked out that the two processes are ultimately identical, just using very different notations.
  • brian_cloutier 10y ago
    > find a system with a transfer function that is the inverse of the power spectral density of the autocorrelation function for the biased coin For those of us who don't know systems theory, is there a simpler explanation of this? It sounds interesting
    • bandrami 10y ago
      Sure. A "system" (which is an incredibly broad term; in practice a circuit composed of resistors, capacitors, and inductors can model any linear system so we stick with that) takes the signal x(t) and maps it to something else, f(x(t)). The autocorrelation function r(t) defines the bias of the coin (r(t) is generally given in the problem, or in real life found empirically). All of these functions are difficult to work with directly. However, their Laplace transforms are much easier: X(s) and R(s), and because of how Laplace transforms work, F(s)X(s) (convolution becomes multiplication after a Laplace transform). So if F(s) is 1 / R(s), F(s)X(s) = X(s) / R(s), which means all of the correlation in X(s) is divided out, and you're left with an uncorrelated function, or fair coin in this case.