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.
Alice writes on a piece of paper whether to use the result from the first or the second coin, Bob flips the coins however he likes, then once there are two different sides of the coins up, Alice turns over the paper and reveals to Bob which coin contains the result.
Though I guess that unnecessarily complicates the procedure – maybe Alice can just write "heads" or "tails" on a note and then Bob flips without having seen the note. It essentially replaces the second coin with Alice's mind which hopefully doesn't suffer from the same known bias.
° Shake the cup vigorously and dump coins on the table
° If coins match, go back to step one
° If coins are opposed take the result of the southernmost coin
I was still lucky with the numbers as for example with 80% vs 20% it would've been 4x4=16 and so 1 to 16 comes to 100 / 17.
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%.
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
Theory is useful but so is experiment.
p(th) = p(t) p(h)
p(ht) = p(h) p(t)
Hence p(th) = p(ht) regardless of coin imbalance as long as both events actually will happen. QED.
Is this a wrong way to get a right answer?
I recall conversations on Usenet decades ago about the Monty Hall problem[1] in which people gave elementary proofs that probabilities don't change by opening a door. Even from mathematicians and statisticians. People were very insistent that the analytical solution was simple and obvious and that switching doors didn't change anything.
The only thing that changed some people's minds was a program that simulated the Monty Hall problem. This was needed to get people to reconsider their proof when the claim was highly counterintuitive.
I suppose this is an interesting corollary with discoveries made by deep theoretical mathematics. While something may seem possible because "the math checks out" it could be only theoretically possible as it relies on some unnatural value to "be" possible in the first place.
Testing is where hopeful theories are smashed by reality until all that remains is the verifiable truth. Truly, why wouldn't we test?
[0] https://en.wikipedia.org/wiki/Deferent_and_epicycle#Bad_scie...
It's not any harder to do the "correct" analysis than to write up a simulation. It's mostly just easier to convince yourself that the simulation matches the problem description when it reaches the unintuitive result.
Could you provide an example? It seems obvious that a switcher wins exactly when a non switcher looses, which is 2 / 3 ?
Say you are playing the Monty Hall game with this host. You choose your door, he opens another door, and it happens (purely by chance) that there is no prize there. Do you still believe that you have a 2/3 chance of winning if you switch to the other unopened door?
Aren't you modeling an entirely different problem as opposed to modeling the same problem with a different model, since the problem states the parameters and you are changing those?
Not really, but read on:
You correctly state that in the Monty Hall problem, the host reveals a door without the prize. That's the same situation which I described in my previous comment.
Try thinking about it this way: Say you are the contestant on that show. You have never played the game before, and you will never play it again. So you don't know how the host behaves. You pick your door, he reveals another door, there is no prize behind it. You would have to ask yourself: did he deliberately open that door because it had no prize? Or did he just happen to open a door that had no prize?
Your best estimation of your odds of winning changes completely depending on how you model the behavior of the host.
However, with any type of host, the situation whereby "contestant opens door with no prize, host reveals another door with no prize" can still occur, and regardless of whether you deem that the 'original' Monty Hall problem or not, it is the most interesting way to define the Monty Hall problem. Call it the extended Monty Hall problem if you want: the situation described above has occurred, and you have to both define a model for the behavior of the host (and game) and calculate your odds under that model.
Here's a challenge for you: Can you find a model under which the contestant has 100% chance of winning by not switching to the unopened door?
I think seeing the results of a simulation also elucidates the set up of the math problem vs reading a proof.
"Hall will always open one of the two non-chosen doors and will never reveal the prize"
I think most people who don't understand the problem miss that critical detail.
After Monty eliminates one of the three doors, then the prize is behind one of the two. If someone were to come in this point, with no prior knowledge whatsoever, their chance of picking the correct door at random is 1/2. And that is still true even if they pick the door which our contestant is being asked whether or not to switch from! This is a real mind fuck to try to accept, that the same state of what's behind each door leads to different odds of making a correct random choice, depending on when you make the choice.
I honestly don't think I'll ever be able to "get" the Monty Hall strategy. I think I get why it works (choosing to switch means you're going from a 1/3 probability to 1/2), but it makes no sense at all. It seems like even if you choose to stay on the same door, your probability is 1/2 (the same as if Joe came in off the street and chose the same door as you). Like I said, I just have to take it on faith.
Your last paragraph isn't correct though, By switching you go from a 1/3 probability to a 2/3 probability. Based on the information the original contestant has, switching gets the car 2/3 of the time.
If the game had different rules, it would work like you are imagining. Specifically, if Monty randomly eliminated one of the two doors, meaning there was a chance for Monty to reveal the prize instead of a goat. If Monty has the chance to eliminate the prize before giving the contestant a chance to switch, then switching does not give you an advantage.
So lets say you have just picked a door in the beginning. You know you have a 1/3 chance of being right.
If I then tell you, "I will give you two options... you can either bet you are right, or bet that you are wrong"
You would obviously choose to bet you are wrong, correct? Because you know you only have a 1/3 chance of being right with your guess, which means you have a 2/3 chance of being wrong. The smart bet is that your original guess was wrong.
This is actually what is happening in the game if you think about it. You pick a door and it has 1/3 chance of being the right one; since we know Monty is only going to ever reveal a goat and never the prize, we don't even NEED Monty to reveal the door at this point - we know he is going to reveal a goat, no matter what. We don't even have to wait to see which door he reveals, since that isn't going to give us more information (it is going to be a goat, no matter what). So when he asks you if you want to switch doors, he isn't asking you to switch to ONE of the other two doors, he is asking if you want to switch to having BOTH other doors as your choice. Whether he reveals the goat before or after you choose to switch doesn't matter, because you know it will always be a goat.
If that is still not clear, lets just write out all the options:
There are three doors, A B C. One has a prize, the other two have goats. Let see what happens with your two options (switch or dont switch).
In our first example, you pick door A and you are going to switch.
1/3 of the time the prize is behind door A. If the prize is behind door A, and you switch, you lose. This is 1/3 of the time, and you lose for switching.
1/3 of the time the prize is behind door B. You picked door A, so Monty reveals door C. You switch to the remaining door (B) and you win.
1/3 of the time the prize is behind door C. You picked door A, so Monty reveals door B. You switch to the remaining door (C) and you win.
Add up all those choices, and 2 out of the 3 times you win.
Now lets imagine that we DON'T switch.
1/3 of the time the prize is behind door A. Monty reveals one of the other doors, but you don't switch. You win.
1/3 of the time the prize is behind door B. Monty reveals door C, but you don't switch from A. You lose.
1/3 of the time the prize is behind door C. Monty reveals door B, but you don't switch. You lose.
So in this not switching world, you win 1/3 of the time.
In summary, switching wins 2/3rds, not switching wins 1/3.
Does that help at all?
Monty opens door 3, showing a zonk. You knew there was a 2/3 chance of the car being in door 2 or 3, but now you know there's a 2/3 chance of the car being in door 2 (since you know it is not in door 3).
All this didn't change anything you know about door 1. It has the same 1/3 chance it started with. Probability is all about what you know in the moment.
The math involves understanding the rules, that Monty will never open the door you picked and will never open the door with the car behind it. This is why one can't look above and say "well, there is a 1/2 chance of the car being behind door 1 after door 3 was opened and there wasn't a car there". This would only be true mathematically if the door Monty opened was random, but we know the door Monty picks isn't random. In fact, the pool of doors that could be opened depends on your initial pick. Monty was never going to open door 1 (the door that you picked), even if it was a zonk & Monty was never going to open the door with the car, therefore one can't make that assertion.
Doors: Goat Goat Car
You pick a door. Monty shows you a Goat. You switch or stay.
Monty will never show you the Car before offering a switch. He always shows you a Goat. It doesn't matter which Goat he shows you - it's just "not the Car".
If your first choice is a Goat, switching will win you the Car. If your first choice is a Car, switching will win you a Goat. You have a 2/3 chance of picking a Goat, so, effectively, you want to pick a Goat so that you switch to the Car.
The best way I’ve heard it explained to help people get it through intuition is by changing the number of doors and goats. Say there are 100 doors, and they all have goats except one, which has a car. You pick door 1. Monty then proceeds to open doors 2 through 48, skips door 49, and then opens the remaining doors. After all that, he stops and asks you, would you like to switch?
Is it, though? It seems apparent that, after the first guess, the host opens all but the last two doors, which just so happens to be 1 door.
To check the math:
Start with the $NUM_DOORS open doors. Now open all but the last two. So that’s $NUM_DOORS-2, which is 3-2, which equals 1 open door.
1. You pick a door.
2. You get the offer "Do you want to keep that door, or choose both [all] of the other doors? In either case, you'll keep anything that isn't a goat."
3. Nobody opens any doors.
Should you keep your one door, or switch to the two doors?
Let's demonstrate with a slightly different construction: You're no longer playing with monty, but with a demon. This demon wants you to lose, but also picked a very bad game for themselves. You pick a door, then the demon opens all-but-one of the remaining doors. Then, you can pick any door, open or closed, and you get what's in it.
If the demon opens doors at random, nearly all the time (with 100 doors) you'll see the car and be able to pick it directly. In this situation, switching between the closed doors doesn't really matter, but you'll usually know exactly which door to pick, because you can see the car.
So instead, the demon only opens doors that don't have a vehicle behind them. You only ever see goats. At this point, he's not opening doors at random. If he were, you'd see the car 98% of the time, but you never do. At this point, since he's using additional information, it is in your best interest to switch.
The fact that Monty Hall opens the doors deterministically (not randomly) is KEY.
In the original problem, Monty ALWAYS opens a door with a goat. In using 50 doors, Monty would ALWAYS open doors containing goats, and not the car. It's not random.
Knowing it's not random, it should be very intuitive.
I think it has to do with the difference between "probable outcome in reality" and "probably outcome based on personally known information".
Lets say when you get down to door #1s and #49, Monty brings in someone new, with no information and says pick a door. For that new person, standing right next to you, doors #1 and #49 have a 50-50% chance, while for you they are a 2% vs 98% chance.
How can door #1 simultaneously have a 2% chance for you and a 50% chance for Bob? The answer is that the chance is not a single fixed property of the door itself- which is hard to wrap ones head around.
And for that matter, Monty Hall himself knows one of the doors is 100% and the other is 0%.
This ambiguity is resolved by something called do calculus - https://arxiv.org/pdf/1305.5506.pdf
Your personal, information limited calculation of the chance a car is behind door #1 has no impact on if there is a car behind door #1. Reality is binary and constant. There was always a car there, or there always wasn't.
Most people correctly intuit that of course the real probability that the car is behind door #1 cant change with reveled information. It isn't a quantum car. They just get caught up on the fact that predictive chance is a attribute of the model, not the real door.
The car isn't moving, as you say, but that intervention by the host lets us trade one door for both of the other doors.
You pick a door, then Monty let's you switch to the two remaining doors and if the car is behind either of them you win.
Obviously choosing the two remaining doors is better.
The trick is to realize that Monty showing you the contents of one door and letting you choose the other one is identical to Monty letting you choose both the remaining doors.
If you're wrong, Monty points to toward the right door.
So you should switch.
I coded it up in F# https://github.com/jackfoxy/LetsMakeADeal to convince one of the founders of a start-up I worked for. He just grunted and walked away. Pretty sure he still doesn't want to hear about Bayes' Theorem.
As a young teenager, I encountered the Monty Hall problem for the first time, and I didn't believe that the "analytical" answer was correct. I decided to simulate it by programming. In the 20 minutes it took me to write a simulation, I went from complete incomprehension to a full understanding of why I got the results I got. Programming a simulation of the problem forces you to write out the algorithmic significance of "Monty reveals one of the goats".
Years ago, when the Monty Hall problem was not well known, I've seen with my own eyes that it was hard to convince some very smart people of the correct answer. Indeed, after being convinced through simulation or exhaustive enumeration of the decision tree or some other way, they would go back and see what went wrong with their initial analysis.
Very nice way to illustrate why throwing out the duplicate sequences gets back to a 50/50 distribution.
Look I found the mathematician
A colleague told him about the Two Trains Problem (https://mathworld.wolfram.com/TwoTrainsPuzzle.html), and Von Neumann replied with the correct answer. When his colleague said, "Ah! You figured out he trick!", Von Neumann replied, "What trick? I just summed up the distances in my head!"
Why not?
The fact that you can show something with a mathematical equation doesn’t make other demonstrations any less cool.
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.
So the probability is the same. Whereas p doesn't equal (1-p) unless p=0.5
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.
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.
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.
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.
In both cases it has to do with shaping multiple rolls using some knowledge of outcome-symmetries and overlaps.
[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.
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
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.
(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...)
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.
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.
https://www.newton.ac.uk/files/seminar/20100623134014301-152...
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.
Otherwise it never halts.
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_...