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.

> 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

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.

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

How to create an unfair coin and prove it with math: https://izbicki.me/blog/how-to-create-an-unfair-coin-and-pro...

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

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.

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.

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.

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

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