Make a Fair Coin from a Biased Coin (2018)
xarg.org
xarg.org
More interesting methods produce a stream of unbiased random bits out of a stream of flips; and you can look at the asymptotic efficiency.
A simple method to run better than von Neumann's method:
Produce 1,000 coin flips. Say you produce k heads and 1,000-k tails.
Produce a table of all possible sequences of length 1,000 with k heads and 1,000-k tails.
Look up the position of your actual realized sequence in that table. The index of that position is a uniform random integer in a range from 1 to the size of the table.
Use your favourite method to extract unbiased bits from that unbiased integer.
The only requirement to make the above method work is that coin flips are i.i.d., ie independent and identically distributed.
(In practice you probably don't want to actually construct the table, but instead compute the index directly as-if you had constructed the table.
You might also want to work with arbitrary number of flips, instead of a fixed 1,000; or even adopt the method to an arbitrary length stream of coin flips that you don't know in advance.
Also in practice, you don't need to store the whole sequence. What you do is keep a count of how many heads and tails you've seen so far, but feed the individual coin flips into an 'entropy pool'. Your head/tail count will inform your estimate of how many bits of entropy you have in your pool. (It basically feeds into the formula for how many possible orders of arrangement you have, similar to the fixed-size method suggested above.)
You generate your unbiased bits by draining the from the entropy pool.
The method of entropy pools described here is pretty much how /dev/random works on Linux.)
I don't claim originality here either; the method is pretty well known.
https://ieeexplore.ieee.org/document/1684974
Shameless plug of a paper on related topics: https://link.springer.com/article/10.1007/s00446-017-0311-5
> The index of that position is a uniform random integer in a range from 1 to the size of the table. Use your favourite method to extract unbiased bits from that unbiased integer.
Why is that position unbiased and random? If I'm using a coin that produces heads every single time, then I'm always going to land on table position 0, so therefore the table index is biased.
Von Neumann's method won't extract any randomness from this coin either.
Do keep in mind that, crucially, you only build the table _after_ you figured out how many heads or tails you got in this particular instance of 1000 flips.
The randomness we extract is not in how _many_ heads or tails we got, but how those heads and tails are shuffled in your sequence.
For the math, have a look at https://news.ycombinator.com/item?id=30697559
This does feel like a generalization of Von Neumann's method from 2 tosses to 1000
If you are sufficiently clever, you can generalize it to an indefinite stream of tosses, and produce output as you go along. See some of the papers mentioned elsewhere in the comments.
This is more efficient than Von Neumann?
log_2(sqrt(1/(2*pi*p*(1-p))) - 1000*log_2(p^p * (1-p)^(1-p))
Neumann's method generates 1000/(p(1-p)) bits of entropy from 1000 coin flips. The theoretical maximum is
-1000*log_2(p^p * (1-p)^(1-p))
One obvious drawback is that you have to flip the coin a 1000 times to produce the first unbiased random bit, while Neumann's method starts producing bits much earlier.
Definitely. Though you could fix that problem relatively easily.
I think you might even be able to run von Neumann's method first, but store the coin flips; and then once you've got enough stored, extract a few more bits from the already used flips.
Perhaps like this:
When you do two flips, you add one of three possible tokens to your list:
'double-heads', 'double-tails' or 'mixed'.
Crucially, you only store 'mixed' and not whether it was 'head-tails' or 'tails-heads' because that information was already used to produce the von-Neuman-bit.
After your list has 1000 entries, you run an algorithm a bit like what I originally described to extract bits. The complication is that the table you construct has all possibilities of shuffling a fixed number of 'double-heads', 'double-tails' or 'mixed' tokens.
An other commenter linked to some papers for asymptotically optimal entropy generation, I wonder if there is more of a streaming method there. It feels like there has to be, even maybe after a slow start. My naive intuition is that after 1000000 coin flips you have a good idea what p is, and then you can basically do arithmetic coding from there. Of course a theoretically correct method can't do exactly this, but it might asymptotically approach it.
/dev/random being unbiased relies on some assumptions about cryptography; but in practice these assumptions are at least as well-founded as our assumption that our coin flips are independent.
Look at some of the papers mentioned in other comments on this submission. There are (near) optimal streaming methods.
For example, if H=1 and T=0 then you do something like “any result above 11010 is a real heads, others are tails.”
Edit: never mind, that’s a different method than OP. (Doesn’t require exactly k heads.) Doesn’t it get the best of both worlds though?
Edit2: Double never-mind, the problem assumes you don’t know the level of bias. But I think the OP threw that out as well.
Essentially, it generates a thousand flips, and then carefully extracts the randomness only out of how those flips are shuffled, but now how many heads there are.
However, the closer to 500/500 your distribution is, the more entropy the method I describes can extract. Conversely, if you randomly hit 1000 heads and 0 tails, the method can't extract anything, and you'll have to sample again.
In contrast, a method that knows the bias and can exploit it, can extract the same number of random bits, no matter what you actually flipped. Eg in the special case of a known unbiased coin, you always get 1000 random bits for 1000 flips. Even if those flips happen to be 1000 heads.
And instead of computing the "effective index" as an abstract number and then extract bits from that, you can work out directly how to generate the unbiased bits.
Less efficient in terms of runtime (if you implement it as naively as I have described here).
I don’t see why it would be. The normal way to produce such a table is as hhh…hh, hhh…ht, hhh…th, … ttt…ht, ttt…th, ttt…tt. If heads is more likely than tails, the index is more likely to be in the lower half than the upper half.
Reading https://blog.cloudflare.com/ensuring-randomness-with-linuxs-..., I also don’t think that’s how Linux’ entropy pool works.
Where does the description in that article differ materially from what I described in the parenthetical remark?
(Of course, it does differ from what I described in the main text of the comment.)
Let’s say my experiment results in an index of 42, how do you convert that integer into information about a string of unbiased coin flips?
However, you can do much simpler and still be pretty efficient (and unbiased).
Suppose your range was numbers between 1 to 49 (inclusive).
If you get a number between 1 to 32, you interpret that as 5 bits. If you got a number between 33 to 48, you interpret that as 4 bits (because you have 16 == 2^4 possibilities between 33 to 48). If you hit 49, you just drop everything and sample again.
So if you got 42, like j7ake suggested, that would be 42 - 32 = 10 = 0b1010.
You can generalize this scheme to other numbers of possibilities.
https://izbicki.me/blog/how-to-create-an-unfair-coin-and-pro...
I get the idea as shorthand for a binary outcome, but the way you make a coin fair is to flip it.
1.96 * sqrt(p * (1-p) / n) = 0.01
0.5^2 / n = (0.01/1.96)^2
n = (1.96/0.01 * 0.5)^2
Or about 9604. So you need roughly 10k trials to determine with 95% confidence a bias of 1%.
https://epubs.siam.org/doi/abs/10.1137/S0036144504446436?jou...
But bending/weighting won't change that.
The implications on all of it are pretty big.
There very well be refs who can take advantage of coin flips over time.
See https://news.ycombinator.com/item?id=30696269 for how you can improve on von Neumann's technique and still stay provably unbiased in your output.
Instead of biasing the coin, consider unrandomizing the flip.
Here’s one of many articles on Perci Diaconis trying just this
https://www.ams.org/publicoutreach/math-history/hap7-fifty-o...
> I get the idea as shorthand for a binary outcome, but the way you make a coin fair is to flip it.
That's a case of working from false assumptions that aren't necessarily true in practice.
The way to make a coin flip fair is to control as many variables as possible during the flip and landing - because that is what is done by people who bias the flip. Only one of these variables is the coin itself.
Bias sometimes exists in the apparatus around the coin. After all some historical coins have ferrous metal in them, as the simplest example.
Bias can also be introduced by the people performing the flips. For example, there are people who can flip a coin onto its edge or with an outcome biased towards heads or tails. A flip onto the coin's edge can even be done by an amateur. [1]
After all, even without bias a coin can land on its edge. See this CBS News video from a Soccer game's ref flipping a coin. [2]
To make an extreme example, if someone can cause the sequence to contain strings of HHHT, this algorithm would absolutely bias towards returning H. So, the key to overcoming this algorithm is to inject a sequence that, regardless of which modulo 2 positition is A or B in the code, will tend to fall on such an input bias. The point is that people trust code that says it fixes these sorts of things, so it is often easier than not to break the code by controlling the input.
There are other methods used in the real world when ingesting random bit sequences.
You can just glue a weight to one side of the faces at an offset.
All because you can't imagine a way to do it doesn't mean it can't be physically done. This is a lesson kids. Randos on the internet can be wrong. Even with high conviction
edit: On second thought this is probably a bijection and you can call it "arithmetic coding" in either direction.
As far as I can tell, arithmetic coding needs both a compressor and a decompressor. Otherwise it's relatively useless in eg your fancy video file format.
In this case the algorithm says you return tails unless you flip 7 heads in a row (which happens with probability 1/128).
Though I can see an interesting problem:
You have a known unbiased coin, and a biased coin with unknown p.
Your task is to create a stream of coin flips with bias p. You want to minimize how often you have to flip the biased coin; and somehow work out a way to make use of the unbiased coin to 'stretch' your sequence of biased coin flips.
I am not sure if this is possible.
It seems to be a corollary that you cannot get random bits at a guaranteed rate that way.
If the activity is decreasing at a linear rate, then A+D and B+C should have exactly the same distribution. In reality, they will be ever so slightly different because the decay is exponential rather than linear, but over short periods of time (compared to the half-life) the linear approximation is extremely good.
So for a 6 sided dice, you roll it 6 times in a row. You discard your 6 rolls unless you get a permutation of {1,2,3,4,5,6}, and in that case pick one of the rolls consistently, eg the first or the last.
Though I suspect still quicker to convert to unbiased coin toss and use those as the bits of a number in the desired range than to wait for a permutation of 123456
For example, with P=1/3, the general method discards TT (P=1/9) and HH (P=4/9) and repeats, while keeping HT and TH (P=2/9 each). One could optimize this by only discarding TT while returning 0 for TT (P=4/9) and returning 1 for HT and TH (P=2/9 each, together also 4/9).
Generally we just want to partition the event space into three parts such that two are equally likely while the third one is used to "scratch that, just repeat". Keeping HT and TH guarantees that, but if you want to minimize retries, better solutions are possible.
0. Train your wrist, 'cause you'll be flipping this a gazillion times (say just N times)
1. Enumerate all possibilities, i.e., sample space = {H, T}^N
2. Compute the probabilities of each.
3. Partition the sample space into two such that the total probability (sum of probabilities) is equal to 0.5.
4. Call one element of the partition heads and the other tails.
5. Want a "multi-sided-coin"? Go back to step 3 and create a finer partition.
If you squint right, I described a method in https://news.ycombinator.com/item?id=30696269 for how to do just that. But I wonder whether you have a different method in mind?
Thanks for the link!
Assuming you mean a uniform distribution, we can calculate this. Been a while since I've done stats, so bear with me...
We can first argue from symmetry that we should expect as many heads as tails. But this doesn't mean that this is necessarily the same distribution as a perfectly fair coin (Bernoulli with p = 0.5).
Anyway, the distributions we have here are a Bernoulli distribution and a uniform distribution
X ~ {0, 1}; 0 with probability 1-q, 1 with probability q
q ~ [0, 1], uniformly
The expected value of X is
E[X] = 0 * p(0) + 1 * p(1) = p(1)
I think we could prove p(1) = E[q], but I'm honestly not sure, and don't know if that holds up in general. But from the above, we know it's 0.5 anyway. Now, we need higher moments:
E[X^n] = 0^n * p(0) + 1^n * p(1) = p(1) = 0.5
The moment generating function of a probability distribution is defined as M_X(t) = E[e^(tX)]. There's a theorem in probability that two distributions with the same MGF are the same. You can see from the above that this has the same moments as a Bernoulli distribution with p = 0.5. Hence, a biased coin with a random uniform bias should be identical to a Bernoulli distribution.
In fact, I believe the above argument works for not just uniform bias, but any random bias that is symmetric about p = 0.5.
In Dungeons and Dragons, a challenge is typically resolved by taking some number that's a difference between difficulty of the challenge and your character's skill, and comparing it to the roll of a twenty sided die. (Higher is better for you.)
Some dungeons and dragons game masters sometimes can't decide how hard to make a challenge. So they roll one die to set a random challenge, and then proceed as normal with a second die roll.
With the same logic as in your comment above, I think you should be able to show that this 'randomized challenged' behaves exactly the same as a challenge of difficulty 10?
(Assuming the "coin" is a complex device)
That's why proving that a hardware RNG is secure is very difficult.
Look at the following setup:
First, you pick a cleanup/filter algorithm.
Second, your adversary gets to study your algorithm and hand you a dastardly clever 'coin'. [0]
Third, your algorithm runs, but has access to a second unbiased source of randomness. [1]
Under those circumstances, your algorithm has a chance!
Basically, you use your extra source of randomness to create a secret key; then use that key to encrypt your adversary's bit-stream from their "coin". If your encryption algorithm has 'ciphertext indistinguishability under chosen-plaintext attack' https://en.wikipedia.org/wiki/Chosen-plaintext_attack this scheme should roughly work, unless your attacker has exponentially more computing power than you do.
[0] To make the challenge fair, assume that our adversary has an obligation to put at least a bit of entropy into their "coin". Eg by having an unrelated third-party pick an arbitrary bit-stream that our adversary has to transmit via their "coin". How the adversary encodes that is up to them; and they can be as wasteful as they like. They just have to be able to decode it, too.
[1] You have to use that source sparingly to make it a challenge.
1) If you expected the filter algorithm to detect and warn on bad/malicious randomness, this doesn't work
2) More importantly, if you have a CSPRNG and a source of randomness as part of your filter you can simply throw away the "coin" because just implemented your own RNG.
Basically what /dev/random does in Linux: they still use the potentially tainted 'coins' despite having a CSPRNG.
Yes, this is well known. Any reseeding of the CSPRNG is good if you steer it in with XOR.
If your adversary knows your secret state, they can tailor their to-be-XOR-ed data to steer your state wherever they want to.
The threat model where this is realistic is when your adversary built your hardware random number generator that you use to add entropy to your pool. (And that's assuming that this piece of hardware can see the other entropy sources that go into your pool, but can not directly exfiltrate that information into the outside world.)
First you find a gambler, any gambler and ask them to show you the lowest denomination coin they have, and get them to verify for you that it is a fair coin. Now demonstrate your weird coin to them, and when they are amazed by its properties, swap it with them for the fair coin. Done.
I guess I need to go out more.