Whether only one round is performed or not is irrelevant. Every round has a success probability, even when there is only one.
My mind just refuses to accept that one single round (where a goat was revealed) can have different probabilities depending on what the host's strategy is over all rounds. It almost sounds like the gambler's fallacy (although I understand it's not, because that fallacy is related to a rather different, psychological phenomenon.)
(The exception being the excellent point you brought up, of course: If the host were always playing against you, and thus always deliberately opened the car door if you didn't select it to begin with, then switching would be detrimental because you would always lose by doing so. If you knew this strategy, then it would be effectively the host telling you outright "the door you chose is the correct one." However, this is a special case. The classical vs. random strategy affecting the probabilities of one single round still baffles me.)
Well to know what the perfect strat is for games, you'd have to know the expected values for these, IE what's the probability of him using each strategy, as well as the actual probabilities of switching during each strategy bringing an advantage.
However, in this case that's super easy, considering it's either 33/66, or just 50/50. IE in case 2, switching won't make any difference, yet in case 1 it makes all the difference, so that alone shows you that it can only help, it'll never make things worse. But if that's not satisfactory, then say he has Probability p of doing first strat, (1-p) of the second.
Exp(Switch)=(p)0.66+(1-p)0.50= 0.5+0.16p
Exp(Stay)=(p)0.33+(1-p)0.5=0.5-0.16p
Clearly for all p, we have E(Sw)>=E(St), so it's always beneficial to switch in this game, regardless of if he's trying to do it random or not. It'll either increase your chance, or equal your chance, but it can't ever decrease.
Lets play another game, there's 10 cigarettes, one of which is poisonous. I offer you one, you either smoke that one, or choose a different one. If I told you my strat was that I want to kill you, I'm sure you'd agree the best strat is 'pick another one'. If I told you I grabbed one at random, I'm sure you'd agree there'd be no real benefit to switching. Surely it's obvious that depending on what the host's intentions are, it'll affect what decision you should make? With the host having different intentions, certain combinations will or will not happen, thus by excluding them from the set it'll affect the probability of the remaining situations occurring.
Accept it.
Flip's post is assuming that you know that the host will only ever use either the random strategy or the Monty Hall strategy each round, even if you don't know which of the two is used. Without this assumption, the argument does not hold.
Let's say the player knows that the host uses the strategy of opening the goat door with probability p and the car door with probability 1-p, if the player initially selected a goat door. Expectation is player win=1, loss=0.
Exp(switch)=Prob(switch wins)/Prob(host opens goat)=[(2/3)p] / [1/3+(2/3)p]
Exp(stay)=Prob(stay wins)/Prob(host opens goat)=[1/3] / [1/3+(2/3)p]
Random strategy is p=0.5, Monty Hall is p=1, host always opens car door (mentioned in my previous post) is p=0. 0≤p<0.5 means that it is best to stay, and 0.5<p≤1 means that it is best to switch. p=0.5 is neutral.
- Player knows that host will always use strategies each round with 0.5≤p≤1 (as in Flip's post): Always switch.
- Player knows that host will always use strategies each round with 0≤p≤0.5: Always stay.
- Above two do not apply and no other information: 50% switch/stay.
Warp wrote:
My mind just refuses to accept that one single round (where a goat was revealed) can have different probabilities depending on what the host's strategy is over all rounds.
The host's strategy (even if it will be applied to all rounds), as applied to one round, is the host's one-round strategy. It can be complicated like "Play random strategy (p=0.5) with 30% probability, play Monty Hall (p=1) with 30% probability, open a goat door 10% of the time (p=0.1) with 30% probability, open a goat door 80% of the time (p=0.8) with 10% probability," but it is still a strategy used in one round.
Probability has a strange way of working that goes against intuition. In regards to the question "If you are playing one single round, and the host reveals a goat door, is it advantageous to change?", information (whether the player knows anything about what the host's strategy is or not) is very important to answer this question. It is possible for the statements:
- "It is advantageous to switch."
- "It is advantageous to stay."
both to be false (e.g. player has no clue of the host's strategy), since the advantageous strategy is to play a mixed strategy (50% switch/stay). Thinking that it is always the case that one of the two must be true is a false dilemma. Assuming that "advantageous" means "there is no better strategy", then it is also possible for both of the statements to be true (e.g. host plays random strategy p=0.5); in this case, all player strategies are equally advantageous.
I see a lot of stuff posted here and I don't know if Warp yet accepts the answer already, but may I offer a simple analysis?
All games where you pick a car, the host will pick a goat (at random). Only half the games where you pick a goat, will the host pick another goat; in the other half, those trials are discarded because he shows a car. The net effect is that you are discarding some trials when you had picked a goat, when you would benefit from switching.
Sorry if all this has been said before.
I see a lot of stuff posted here and I don't know if Warp yet accepts the answer already, but may I offer a simple analysis?
I understand now why the program prints "50%" (which was surprisingly difficult to predict and even understand after I saw the result.)
However, it still kind of puzzles me if and why the host's overall strategy would affect what you should choose in one single round. After all, if you are playing one single round, and the host opens a goat door, the situation is identical regardless of whether the host always opens a goat door or a door at random...
(Although it gives some insight into that question that if the host always opens the car door unless it was the one you selected, then, even though it appears to be an identical situation, it would nevertheless be disadvantageous to switch because you would lose by doing so. In this case the host's behavior does indeed affect the single round.)
I understand now why the program prints "50%" (which was surprisingly difficult to predict and even understand after I saw the result.)
However, it still kind of puzzles me if and why the host's overall strategy would affect what you should choose in one single round. After all, if you are playing one single round, and the host opens a goat door, the situation is identical regardless of whether the host always opens a goat door or a door at random...
(Although it gives some insight into that question that if the host always opens the car door unless it was the one you selected, then, even though it appears to be an identical situation, it would nevertheless be disadvantageous to switch because you would lose by doing so. In this case the host's behavior does indeed affect the single round.)
The probabilities are different but the decision is the same because in neither case is it a disadvantage to switch. If the issue is random goat vs. standard Monty Hall then you're decision is always to switch.
That said, there are host strategies where it's better to stay, like you said. Suppose he had the following strategy:
1) If the player picked a goat, open the player's door (2/3 chance)
2) If the player picked the car, open a different door (1/3 chance)
In the 1/3 chance that the host didn't open the player's door, you are guaranteed to get the car if you stay. In this case it looks like the standard Monty Hall problem but you're actually better off staying. Even though the individual round looks identical to Monty Hall, knowing the host's strategy greatly affected the probabilities. Likewise in the random goat vs Monty Hall strategies, knowing that the host could have picked the player's door makes the random strategy a 50/50 instead of the Monty Hall's 33/66.
However, it still kind of puzzles me if and why the host's overall strategy would affect what you should choose in one single round. After all, if you are playing one single round, and the host opens a goat door, the situation is identical regardless of whether the host always opens a goat door or a door at random...
The doors are identical, the host's strategy isn't. If you need to watch a few games to determine the host's strategy, then on the first game, you can only guess.
But if you know the host's strategy, then it doesn't matter if you play a single game or a hundred games. They're statistically independent, the expected value is the same each time.
If you think that MH boils down to "two doors on switch, one door on stay, so it's 2/3 vs 1/3", then you haven't grasped the problem yet. It's not about counting doors, but about knowing which doors to count. You need to draw the full decision tree for that, examine all paths that look like your current situation and compare the chances for "car in door 1" vs "car in door 2". Intuition really doesn't help here.
What might help your intuition is the following: without any additional knowledge, your chances are no better than 50/50. To gain any better strategy, you need more knowledge. Where does it come from?
Sure, in both cases, you gain the knowledge that one door is empty, reducing your choice to two doors. But that information merely increases your chances from 1/3 to 1/2, no more. You need knowledge about the car to get better than that.
In the original problem, that knowledge is coming from the host. The host knows where the car is hidden. He uses that knowledge to determine which door to open (never open the car door). Knowing his strategy and watching his action, you can gain some of his knowledge, and that's what improves your chances. The important information is to watch which door he chose to open, since that choice is influenced by his knowledge. "He might have picked that door randomly since the car is in door 1, but he probably opened door 3 because he isn't allowed to open door 2."
Now imagine the host not knowing where the car is hidden. He has no knowledge. You cannot gain any knowledge from him. No matter what he does, he cannot improve your chances above 1/3 for the whole game. Revealing that door improved your chance to 1/2, but by opening a door he could also have revealed the car, lowering your chance to 0 - on average, his actions neither helped nor hurt you.
You may as well just pick a door and stick with it, nothing the host does will matter, you will not gain any knowledge about the position of the car until the door with the car is opened. Needless to say, that's too late to formulate any strategy.
Btw, how does this work with more doors? Assume that instead of three doors there are four.
If the host always opens a goat door with prior knowledge of where the car is, is it advantageous to switch to one of the remaining two doors? (Obviously yes, although it's also obviously now less likely that you will win. However, the chances ought to be higher than by staying.)
However, what happens if the host opens a door at random (from the ones you didn't select) and by chance happens to open a goat door? Is it now also so that it doesn't matter if you switch?
The Numberphile youtube channel just posted a video showing the extraordinary result that the sum of all natural numbers equals -1/12.
Of course many people would instinctively rather call it an outrageous claim instead, but seemingly there's some mathematical truth to the result, and there are many ways to prove it. (Note that this is not talking about what the limit of the series is, or what it converges towards, but rather the sum of an infinite amount of terms, which is different.)
Since one of the simple proofs shown in the video deals with infinities, I instinctively get the idea that "you can prove anything with infinities" (in the same way as you can prove anything with something that equals eg. 0/0.) In other words, using some other mathematical trickery you could make the sum equal to whichever value you want, like -1/25 or 50.2. However, apparently -1/12 is the only result you get, no matter which method you use to solve it.
While the video (and its extra footage) has some talk about this, I would like to hear if someone else had some other insight into understanding the rather puzzling result.
(Also, why "12" and not something else? Where is precisely 12 coming from? I mean I can see the proof in the video, but it's still puzzling why its 12. Is there some kind of odd relation with precisely that fraction and the infinite sum of all natural numbers?)
The Numberphile youtube channel just posted a video showing the extraordinary result that the sum of all natural numbers equals -1/12.
Of course many people would instinctively rather call it an outrageous claim instead, but seemingly there's some mathematical truth to the result, and there are many ways to prove it. (Note that this is not talking about what the limit of the series is, or what it converges towards, but rather the sum of an infinite amount of terms, which is different.)
Since one of the simple proofs shown in the video deals with infinities, I instinctively get the idea that "you can prove anything with infinities" (in the same way as you can prove anything with something that equals eg. 0/0.) In other words, using some other mathematical trickery you could make the sum equal to whichever value you want, like -1/25 or 50.2. However, apparently -1/12 is the only result you get, no matter which method you use to solve it.
While the video (and its extra footage) has some talk about this, I would like to hear if someone else had some other insight into understanding the rather puzzling result.
(Also, why "12" and not something else? Where is precisely 12 coming from? I mean I can see the proof in the video, but it's still puzzling why its 12. Is there some kind of odd relation with precisely that fraction and the infinite sum of all natural numbers?)
I just finished commenting on that video. Fancy that.
Some of the assumptions I noticed:
1) 1-1+1-1... = 1/2 (wild theorycrafting about the nature of infinity)
2) The power series for 1/(1-x) being valid at x=-1 (the power series is only valid for |x|<1)
3) Using analytic continuation to say the Reimann Zeta function converges for s<=1 ("Well the definition says P, so let's assume Not P and see where that gets us"). I can use analytic continuation to find factorials for negative numbers, it doesn't mean my result has any meaning.
4) That it kind-of makes sense because you go "all the way to infinity" instead of using partial sums. If you're going to make me include infinity as a number in my calculation, then you're working in the Extended Reals and all bets are off.
You can use 1-1+1-1... and creative use of parentheses to prove that 0=1. You have to be careful when doing anything with non-convergent series, and I don't see any of that in the video.
I'm okay with non-mathematicians skimping on the mathematical rigor in favor of application, and under normal circumstances I would have been fine with a non-intuitive answer if there was real world evidence backing it up. But this is an extreme case of that and I'm going to need something a little more "real world" than string theory or quantum field theory to accept it.
And honestly, if you need a non-convergent series to have a finite value for your theory to work, maybe the proper response is to take a step back and question whether or not the universe really has 26 dimensions.
http://en.wikipedia.org/wiki/Divergent_series
I can't really say much about this subject considering it is far afield for me. All I can say is there are credible theories out there that agree on 1+2+3+4+...=-1/12, complex analysis being one (note: when I say theory, I mean theory, not a wild guess or anything like that).
You could make an argument like: Let 1+2+3+4+...=T and 1+1+1+...=U. Then T+U=2+3+4+...=T-1, so U=-1. On the other hand, T-U=0+1+2+3+...=T, so U=0. This may fit into the idea of "you can prove anything with infinities". Or rather, something in the theory should be considered wrong (since most of us believe that a theory that proves that every number is equal to every other number is a bad theory). For example, any one of "1+2+3+4+...=T", "1+1+1+...=U", "T+U=2+3+4+...", "2+3+4+...=T-1", could very well be considered a wrong statement, and that would actually improve the theory.
(Note that this is not talking about what the limit of the series is, or what it converges towards, but rather the sum of an infinite amount of terms, which is different.)
By definition the sum from a natural number i to infinity is the limit of the sequence of partial sums S_n (the sum from i to n) for n approaching infinity, which is well-defined. In this case it is easy to show than S_n diverges against infinity (for every C element R there is an index N, so that for all n>=N: S_n>C).
Edit: Whatever method they used and assumptions they made. One can surely say that the title of that video is misleading (like so many others).
All syllogisms have three parts, therefore this is not a syllogism.
Edit: Whatever method they used and assumptions they made. One can surely say that the title of that video is misleading (like so many others).
These are professors of mathematics and physics working at actual universities, so it's not like they are just making this up using pseudomathematics. (I know this is borderline argument from authority, but still...)
But as noted by others, the proof feels a bit fishy. By grouping terms in different ways you get different results. This effectively results in a contradiction, which usually means that an operation being performed is invalid.
I thought of another simple demonstration of that. Let's assume
A = 1 + 2 + 3 + 4 + ...
B = 1 + 1 + 1 + 1 + ...
Then A+B, if you group the terms in this way:
A+B = (1+1) + (2+1) + (3+1) + ... = 2 + 3 + 4 + 5 + ... = A - 1
which means that B = -1.
If you group them like this:
A+B = 1 + (1+1) + (2+1) + (3+1) + ... = 1 + 2 + 3 + 4 + ... = A
which means that B = 0.
B cannot be both -1 and 0. This sounds to me exactly like a textbook example of proof by contradiction.
You are correct! You can't manipulate divergent (and many convergent) infinite sums that way. Thus, their first proof is invalid.
Their second proof is valid, though, as distributing is usually a valid manipulation.
New video: http://www.youtube.com/watch?v=E-d9mgo8FGk
There's still some hand-waving going on (statements such as "Set x=-1" are not valid) but it touches upon analytic methods, and the Riemann zeta function of course.
A 6-sided dice is thrown N times and the results are observed to form a monotonic sequence. What is the probability that every possible number occurs at least once in the sequence?
I've come up with at least 3 formulas, none of them work >_<
What seems the most appropriate formula would be using the reverse probability. What is the opposite of having all the faces? Having at least 1 face missing: (5/6)^N. Thus 1 - (5/6)^N. Let's try that:
N=6: 66,5102023%
N=10: 83,8494417%
N=100: 99,9999988%
But to check that, one would need to count every possible dice result, and I started the wrong way to count them all. The tricky part is that any number could be the missing one, however if you just count every combo with 1,2,3,4,5 and then you count every combo with 1,2,3,5,6 so you add them up, you are likely to count the combo 1;1;1;1;1;1 twice.
Out of the curiosity, what were your two other formulas? Since I can't check if mine is correct…
This sounds like a standard balls-and-bins problem in a probability course.
Monotonic means the sequence satisfies at least one of:
(1) ai≤ai+1 for all i,
(2) ai≥ai+1 for all i.
Let's take a weakly increasing sequence (ai≤ai+1 for all i) of length N on the labels 1,2,3,4,5,6. Let ni be the number of elements with the label i. Then ni≥0 for all i, and the sum of all ni is N.
(We assume from now on that all sequences are of length N and are on the labels 1,...,6.)
This is equivalent to placing N balls in 6 bins, which in turn is equivalent to arranging a sequence of N stars and 5 bars. There are C(N+5,5) ways of doing this.
So there are C(N+5,5) weakly increasing sequences. Likewise there are C(N+5,5) weakly decreasing sequences (ai≥ai+1 for all i), and a sequence is both weakly increasing and weakly decreasing if and only if it is the same number repeated N times, of which there are 6 of them.
Therefore the number of monotone sequences is 2*C(N+5,5)-6.
Now for a weakly increasing sequence to cover all the labels 1,...,6 at least once (where we call the sequence a covering sequence), that means ni>0 for all i, and the sum of all ni is N.
This is equivalent to placing N balls in 6 bins with at least one ball in each bin, which in turn is equivalent to arranging a sequence of N stars and 5 bars where the bars cannot be at the ends or beside each other. Considering the problem as inserting the bars in-between the stars, there are C(N-1,5) ways of doing this.
So there are C(N-1,5) weakly increasing covering sequences. Likewise there are C(N-1,5) weakly decreasing covering sequences, and a sequence can't be weakly increasing, weakly decreasing, and covering all at the same time.
Therefore the number of monotone covering sequences is 2*C(N-1,5).
The probability that a sequence is a covering sequence, given that it is monotone, is [2*C(N-1,5)] / [2*C(N+5,5)-6].
A polygon has vertices with integer coordinates (in 2 dimensions) and integer length edges. Show that the perimeter is an even integer.
Define the following:
Pp: the parity of the figure's perimeter.
Px+y: the parity of the net displacement in the x coordinate plus the net displacement in the y coordinate.
Lemma:
It can be shown that all Pythagorean triples can be generated by the following equations:
a = k*(m2-n2)
b = k*2mn
c = k*(m2+n2)
where k, m, and n are all integers. Because all three are integers, b is surely even because of the factor of 2 in its expression. Therefore, either all three sides are even or one leg is even while the other leg and the hypotenuse are both odd.
Proof:
Begin with Pp even and Px+y even (i.e., start with even perimeter and even x+y displacement-- plausible for the trivial polygon consisting of a single point).
Iterate over all diagonal sides of the polygon. Because its vertices are on integer coordinates and the sides are integer length, a right triangle with integer sides can be constructed such that its hypotenuse coincides with the diagonal side of the polygon under consideration and the right angle is at integer coordinates. In other words, the right triangle's sides comprise a Pythagorean triple.
With each side, the additional perimeter contributed is c. If c is even, then Pp is unchanged and because both legs are even (by the lemma), Px+y is also unchanged. If c is odd, then Pp is changed and because one of the legs must be even while the other is odd (again, by the lemma), Px+y is changed as well.
Because both Pp and Px+y change concurrently, after all diagonals have been iterated through, both are surely either 0 or 1.
All diagonal sides have been iterated through, so all that remains are the vertical and horizontal sides. For this to be a closed polygon, the net displacement after iterating over all sides must be zero. Of course, the parity of the net displacement must be zero as well. If Px+y is odd, then we have to take an odd number of horizontal and/or vertical integer "steps" on the grid, which will add an odd number to Pp (which was odd before considering horizontal and vertical sides). If Px+y is even, then we have to take an even number of horizontal/vertical integer steps, which will add an even number to Pp (which was even before considering horizontal and vertical sides). In either case, we end with Pp being even, completing the proof.
I'm not a mathematician and although I'm confident my proof is correct, I'd like someone to clean it up for me. I imagine there's a more elegant way to put all this.
That's right Bobo the King. There is one bit of neatening I can do to the proof. For the section where you discuss Pythagorean triples, you don't even need to invoke the formula for generating them. All you need to do is reason thus:
If x^2 + y^2 = z^2, then either:
x and y are both even, z is even
x is odd, y is even, z is odd
x is even, y is odd, z is odd
And in each case x+y-z is even.
