18 ms·
Von Neumann described a very elegant way to get fair results from a biased coin. 1. Flip the coin twice 2. If you get the same result both times, goto 1 3. N
by jbandela1 3y ago
Von Neumann described a very elegant way to get fair results from a biased coin.
1. Flip the coin twice
2. If you get the same result both times, goto 1
3. Now that you have different results for your pair of flips, use the first element of the pair of flips as your result.
https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_...
- extraduder_ire 3y agoI take it a double headed coin doesn't count as biased for this algorithm. (because it's too biased to still be considered a "coin", for probability's sake.) Otherwise it never halts.
- garfieldnate 3y agoCouldn't you still game that by choosing the starting side? If you want heads, and you start on heads and get a tails for the first round, you could start on tails on the second round to try to get another tails and reset to step 1.
- dentalperson 3y agoI love the math/stats history around gambling-related things, thanks for mentioning this. This method assumes the flipper can't introduce bias. ET Jaynes in his book Probability Theory also mentions that it is easy to learn to flip a fair coin in such a way that the result can be predetermined. I searched a tiny bit for this but couldn't find what he was referring to though.
- ryanar 3y agoLots of practice, use your thumb to hit the edge of the coin to give you more control, aim for a specific spot so you use the same amount of force and control the amount of times it flips. You can also use a surface that absorbs more so the coin is less likely to flip after hitting it.
- aspenmayer 3y agoI’ve heard that, with many hours of practice, dedicated amateurs and many famous magicians are able to do this kind of thing. I wouldn’t call it sleight of hand, but it is similar, although it may fall under that category broadly. I’m not a domain expert but I was taught some simple coin tricks as a child by my artist mom’s artist friend who ran the local frame shop. I never tried or thought to try to favor the coin flip or introduce bias, but it’s definitely a skill that can be acquired.
- kqr 3y agoI remember at one point in my childhood learning a trick where it looks like you're flipping the coin, but you're really only causing it to rotate and wobble, meaning it's guaranteed to land on whatever side faced up as you tossed it. I don't remember how I did it though, and a few minutes of trying to recreate the effect has failed.
- mewpmewp2 3y agoThat's amazing, but I guess it won't help when the person can choose the bias? Because according to the study the person can choose the bias by choosing which side start up. So if the person wants tails based on what you've said, they should always 1. Do the first throw starting tails up. 2. If the first one is tails, then they now want to start second one heads up. 3. If the first one is heads, they will want to try and get heads again to dismiss the results. So they will do heads up. So assuming for example that they have an ability to control bias 75% vs 25%. Then there would be 75% chance of getting first as tails. After that 75% chance of getting heads. So they will have 56.25% chance of getting it right the first 2 rounds. The worst case for them would be if they get heads first (25% chance), and then are unable to get heads again. Which would be another 25% chance so 6.25% odds to lose with the first round. So 56.25% chance of winning the first round of 2, or 6.25% losing and 37.5% of having to try again. And I think the odds would converge at somewhere around 90% to 10%. I didn't do full calculations here, but overall it seems this strategy would increase the bias even more.
- wesleychen 3y agoYou can solve this easily by always flipping with the same side (doesn’t matter which) facing up for all flips.
- mewpmewp2 3y agoUnless they can also introduce bias using strength/technique of the throw.
- havnagiggle 3y agoThere is skill to coin flipping. You'd need to blind the flipper, either physically blindfold or make it so they don't know which result is the positive outcome ahead of time.
- bee_rider 3y agoOr ask the competitors to flip the coin in a manner they doesn’t allow for skill, like put it in a Yahtzee cup and toss from there.
- arkitaip 3y agoI absolutely love that even with a corrupted system you can use properties of the system to ensure just outcomes.
- ChocMontePy 3y agoIf anyone wants to test it, someone wrote a short code that simulates doing that 100,000 times: https://www.techiedelight.com/generate-fair-results-biased-coin/ https://www.techiedelight.com/generate-fair-results-biased-c... The coin is biased to come up TAILS 80% of the time, but using Von Neumann's method in the program I got HEADS 50.035%, TAILS 49.965%.
- 098799 3y agoWhy would you test it? Probability of two heads: p*p Probability of two tails: (1-p)*(1-p) Probability of head followed by tails: p*(1-p) Probability of tails followed by heads: (1-p)*p It's not difficult to notice that if you remove the first two, the last two form a 50/50 distribution
- fennecfoxy 3y agoBecause that's how science is done, theory then practical? Maybe it's just a meat space thing, but even if the math gives us the answer it still only feels "final" or "true" to me when we've actually tested something out.
- sporkland 3y agoPut another way p*(1-p) = (1-p)*p So the probability is the same. Whereas p doesn't equal (1-p) unless p=0.5
- voidfunc 3y agoSome of us suck at math.
- williamstein 3y agoMath is often much more fun and compelling for some people when you both theoretically prove something works and then also convince yourself of the same thing via a numerical experiment. I’m pretty good at math proofs (pure math PhD, wrote some books and papers), but I still love to do numerical experiments. It’s fun, and you also set yourself up to be able to easily ask different questions that may be very hard to answer theoretically.
- bryanrasmussen 3y agook but if the coin tends to land as starting then 1. starting from heads 2. flip heads 3. flip heads 4. starting from heads 5. flip heads 6. flip tails take 5 = heads? heads should still be more likely to occur than tails under this scenario, although, Zeno-like, with decreasing likelihood approaching zero over time? on edit: of course Von Neumann's process has more restrictions, leading closer to fairness.
- raphael_kimmig 3y agoIf you always start with heads the method works out. The key is that the first and the second toss need to be independent so that HT and TH have the same probability. If you influence the second toss based on the first one it no longer works.
- ctenb 3y agoThat's really cool. The key insight is that "The reason this process produces a fair result is that the probability of getting heads and then tails must be the same as the probability of getting tails and then heads, as the coin is not changing its bias between flips and the two flips are independent." So you have to make sure you always start with the same side up.
- dataflow 3y agoI'm confused, how does this help? If coins are biased to land same-side up, then don't I always have an advantage by guessing whatever side is up before the first throw?
- jpeterson 3y agoThe probability of [HEADS, TAILS] is always the same as the probability of [TAILS, HEADS], no matter how the coin is weighted.
- dataflow 3y agoI get that but I don't see how it answers my question?
- arrowsmith 3y agoYou're flipping pairs of coins until you get either "HT" or "TT". So the only two possibilities are: 1. keep flipping until you get HT (and so you choose 'heads') 2. keep flipping until you get TH (and so you choose 'tails') Since HT and TH are equally likely, results 1 and 2 are equally likely, i.e. there's a 50% chance of choosing heads, 50% change of choosing tails.
- kqr 3y agoI see what you're getting at, and it's subtle! To simplify the discussion, let's assume we always start out with heads up. You're right that the first coin is more likely to end up heads. But so is the second coin, and if both occur, that would invalidate the pair of tosses. Now, imagine you guessed tails despite the coin starting on heads. If the first toss lands tails, the second coin is still more likely to land heads, which keeps the pair valid. In other words, whatever you gain by guessing the side that's up on the first coin, you lose on account of the second coin having that same higher probability of invalidating the pair. ---- Using extreme numbers, in case that makes it more clear: imagine a coin that has a 99 % probability of ending up with the same side we start with, and – for simplicity of exposition – we always start with heads facing up before the toss. If you guess heads, and the first coin lands heads, then there is a 1 % chance that you win, namely that when the second coin lands tails. If you guess tails, and the first coin lands tails, then there is a 99 % chance that you win, namely that when the second coin lands heads. The two outcomes of the first coin (99 % and 1 % respectively) perfectly balance out the two valid outcomes of the second coin.
- 1980phipsi 3y agoYou can load a dice, but you can't bias a coin: http://www.stat.columbia.edu/~gelman/research/published/diceRev2.pdf http://www.stat.columbia.edu/~gelman/research/published/dice...
- deleted 3y ago[deleted]
- m3kw9 3y agoFlip till I get the side I wanted
- wslh 3y agoWith all due respect to Von Neumann, intuitively I would change it to use the information in the two coins: one for (X, Y) and another for (Y, X). Not the first.
- Schiphol 3y agoYes, and as the second coin carries no information (because we are focusing now on sets of two different consecutive outcomes) both your and JvN's protocols are equivalent.
- vikingerik 3y agoAlso interestingly, this extends beyond a two-sided coin, to any number of possible results, like a die with N sides. To get a fair result from a biased dN: Roll it N times. If you don't get all N distinct results, restart. If you do, then the first of those is your final result.
- Terr_ 3y agoAlso-related are all the problems like "simulate an 11-sided die with a 6-sided die", where the solution involves identifying certain rolls that should trigger a retry. [0] In both cases it has to do with shaping the combination of multiple rolls using some knowledge of outcome-symmetries and overlaps. ____ [0] In this particular case, that's something like: Roll the die twice to get rolls A and B; map those a number X in the range range [1,36] using x=(((A-1)*6)+B); if X<=33 then return (x%11)+1 which will be equally likely in the range [1,11]; if X>33 then start over.
- aidenn0 3y agoThat is only guaranteed to work if subsequent tosses are independent of each other. TFA suggests that they are not. [edit] If you always start with the same side of the coin face-up, then the tosses will be independent of each other, but if you e.g. always flip it once or always keep it the same before the next toss, then they are not.
- elijaht 3y agoTFA does not suggest that. Even if a coin is biased towards the side it started on, this wouldn’t carry over from one flip to the next. It would be important to start the flip on the same side, but that’s doesn’t make the second flip dependent on the first
- aidenn0 3y agoHah, realized that after I posted and edited while you were commenting. It's a good point. My original assumption would you'd just pick it up and flip it; not attempt to put the same side face up each time.
- k7sune 3y agoHow come when the results are the same you have to go to 1 and flip twice again? Can you just toss another one and use the last two results?
- nullc 3y agoThe VN debiaser is very simple but it's not very efficient-- it loses a lot of your randomness. Under the same IID assumption you can take N flips that returned M heads and map them to the N choose M possible ways that could have happened. The result will (under IID assumption, even in the presence of bias) be a uniform number on the range [0..N choose M). The ctz(N choose M) trailing bits can be used directly (as they will be uniform) but the rest would have to be converted to binary via something like an arithmetic coder or rejection sampling. The result is muuch more efficient. Less directly, VN debiasers can also be stacked. Each debiaser outputs three streams: the normal one, one that says if the normal one output anything, and one that says if it got HH or TT. Then run VN debiasers on those. Though it takes a fairly large tree to extract most of the entropy.
- thaumasiotes 3y agoThat only works if the result of the coin is independent of whatever it showed on the prior flip. (You might say "of course it is!", but if that's your approach to the problem, you should be aware that biased coins don't exist...)
- ComputerGuru 3y agoThe same principle is used in embedded systems as the base of a prng when obtaining randomness from a possibly biased or imperfect source of noise (eg adc low bits or uninit memory values). I find it easier to understand if you say “instead of using the level/value as the source of randomness, use the transition from one level/state to the other as the bit of entropy.” (edge-based instead of level-based) I.E. instead of head is 0 and tails is 1, head to tail is 0 and tails to head is 1, and the other transitions are disregarded.
- antisthenes 3y ago> 2. If you get the same result both times, goto 1 Well, yes. The wiki description basically states that you get to throw away results of coin tosses in some particular cases. In that sense, it's not really any different from just making up the results of the coin tosses entirely. There's 10000 different ways to make your data garbage.
- lalaithion 3y agoAh, but this assumes a fixed unfairness; with this result, you could pretend to do the von neumann method but change starting sides on each flip, giving a biased result.
- esafak 3y agoBasically rejection sampling, which is about obtaining variates from one distribution using variates from another. We have samples from p-coins (where p is the probability of flipping heads) and we wish to generate samples from 0.5-coins. https://www.newton.ac.uk/files/seminar/20100623134014301-152416.pdf https://www.newton.ac.uk/files/seminar/20100623134014301-152...
- oakwhiz 3y agoPocket change is Manchester encoded by default.
- mucle6 3y agoThis is very interesting, but it assumes a coin is biased the same way every flip. If a coin is more likely to land on the side it starts on, then the bias can change between flips. To fix this, we just need to make sure the coin starts the same side up before every flip.
- stainablesteel 3y agoyou can do that all you want my coin is the same on both sides