MitD XIII: Learning is happening

[Kashem]

That "infinite loss" implies that if they run out of unmarked doors, TE can't start over. But they can. At best, if MitD happened to randomly mark off the correct door, TE will have to eventually start over, possibly with RC's more methodical approach. It buys time, but nothing else.

Now, time is important - but just as it might cost TE time, it might gift them time, by having eliminated x incorrect doors they will no longer have to spend x days searching.

(This is, of course, ignoring that plot happens at the speed of plot and the OotS will arrive precisely at the correct time for Plot to happen, regardless of anything Xykon, RC and MitD do)



I'm not sure the implied assumption that MitD is marking unexplored doors every day is correct. For all we can tell, that was a one-off. And if it was, MitD does not have a greater chance than Xykon.

Grey Wolf

Hey guys, I'm a programmer, so I just decided to run a simulation, since I'm not confident enough in my math to be certain. So I ran the following three scenarios through 10,000 trials, to see what I got:

Control: How many doors, on average, will team Evil have to search before finding the gate

Door Marking: How many doors, on average, will team Evil have to search before finding the gate if MitD marks extra doors, and then, if it turns out all the doors are marked, they discover that MitD has been doing it, and restart, marking the doors in some other way (green paint)

Infinite Treachery: How many doors, on average, team Evil will have to search if MitD keeps marking doors, and even after he marks them all, he is not discovered, so he keeps doing it
round after round until they just get lucky and find the gate.

My results are as follows: if there are 200 doors, the control number is 100. Since there are two possibilities, and you are drawing random without replacement, it will take you on average 100 doors before you would find the gate.
If the MitD is marking doors, then the amount of doors he marks matters, with lower actually being better (because it takes longer for his treachery to be discovered). If he marks only one additional door, the average goes up to 125. If he marks 2, the average seems to hover around 121 or 122. 3 goes to 117 to 118. 4 goes to 115.
No matter how many extra doors he marks, it will never drop below 100.
The Average time Xykon and Redcloak never actually figure it out: 200, no matter how many doors he marks. Turns out it will take them approximately 2x the time.

So in the end, the math is this (checked by changing the number of doors)
for N doors, The average time if MitD wasn't marking them would be 0.5N. The average time if he only goes for one round is variable, but for 1 extra door (the optimal) it is 0.625N. If team Evil never figures it out, it becomes N.

[Grey_Wolf_c]

Would it really force them to start over, though? Imean, sure, eventually, given enough time. But if I was playing a "which door is it" game, and believed I opened all the doors without finding the prize, my first thought would be "well, maybe it's none of the doors and the answer is something else," not "time to go back through the doors again."

There are plenty of alternatives, and we can't know which one they'll go for. Thing is, they have Serini's diary, so they likely know as much as there is to know about the place. I find it more likely that if they run out of doors not having found the gate, they will be suspicious of MitD than they will be suspicious of the place. Xykon only plays stupid, he isn't actually stupid. I think he is aware that MitD is no longer (if he ever was) a reliable team member - Xykon just went along with his obvious ploy in the desert because it gave Xykon a chance to further humiliate RC, for example.

Grey Wolf

[Fyraltari]

Shown already. Nothing bad about telling after to reinforce.

But these are vastly different: in the desert he was opposing Xykon because he didn’t want him to kill Mr. Stiffly’s friends, now he is opposing him because he plain doesn’t want him to succeed.

What’s more, if he had failed in the desert, Xykon would have called him an idiot and move on, if he fails now (Edit: meaning if he is caught red-limbed) Xykon will kill him: he is putting himself at risk.


Incidentally, if TE is killing everything in its path behind each door, after running out of un-marked doors, it would be trivially easy to tell the ones they have searched from the ones they haven’t: the latter are still full of monsters.

[Grey_Wolf_c]

Incidentally, if TE is killing everything in its path behind each door, after running out of un-marked doors, it would be trivially easy to tell the ones they have searched from the ones they haven’t: the latter are still full of monsters.

Doesn't something Oona said imply that the caves re-generate, at least after a period of time?

I seem to recall she says something along those lines.

Grey Wolf

[Peelee]

But these are vastly different

You say potato, I say spoliation. Or something like that.

[Fyraltari]

Doesn't something Oona said imply that the caves re-generate, at least after a period of time?

I seem to recall she says something along those lines.

Grey Wolf

Yes but all that means is that monsters are born sometimes, it might be natural reproduction. She was explictly worried about them killing too many monsters. The bugbears’ expeditions were motivated by a need for food and raw materials, TE’s systemic exploration is leagues beyond that.


If I was in Redclaok’s and Xykon’s shoes I would suspect Oona and her tribe of being the perpetrators before the MitD: MitD has been a member of TE for years without ever causing problems while the bugbears are new, they don’t have the hobgoblins’ respect for Redcloak’s authority they have ample opportunity to mark the doors while TE is otherwise occupied inside the tomb and they have a mobile: by marking some doors (the most plentiful?) they protect their ressources.

[Throknor]

...So in the end, the math is this (checked by changing the number of doors)
for N doors, The average time if MitD wasn't marking them would be 0.5N. The average time if he only goes for one round is variable, but for 1 extra door (the optimal) it is 0.625N. If team Evil never figures it out, it becomes N.

This saves me from making a crazy analogy. Well, I worked it out so here it is: If there are 30 sealed cases and one has a prize with contestants A & B taking alternate picks but B getting two picks to A's one, clearly A has a lower chance of finding the prize. It may speed up the game for A but I doubt they'd appreciate it. (I apologize for the run-on, but I need to get back to work and it should get my point across.)

Back to the doors: (I believe, not assert, that) The scene is meant to show MITD's mental progression. The Order will get there before they run out of doors. But aside from that, Redcloak is a very methodical individual. Even if Xykon isn't letting him search in order he can count. If MITD does this at all frequently then RC is bound to notice more doors are marked than days have passed. I'd imagine he would notice even after 30 days if 50 out of 100 doors have been marked. I don't know it's a hundred doors, but my point remains: he has likely counted the doors and will realize the count discrepancy before the last door.

[Darth Paul]

.... Redcloak is a very methodical individual. Even if Xykon isn't letting him search in order he can count. If MITD does this at all frequently then RC is bound to notice more doors are marked than days have passed. I'd imagine he would notice even after 30 days if 50 out of 100 doors have been marked. I don't know it's a hundred doors, but my point remains: he has likely counted the doors and will realize the count discrepancy before the last door.

This is an excellent point. The question then becomes how they proceed. They would have no idea which doors have been searched already, so my guess would be, search the remaining doors first, mark them in a different way, and find some way to keep track of them, while working out who the treacherous agent is? Then, re-search the doors that are already marked...

[Wizard_Lizard]

Yes but all that means is that monsters are born sometimes, it might be natural reproduction. She was explictly worried about them killing too many monsters. The bugbears’ expeditions were motivated by a need for food and raw materials, TE’s systemic exploration is leagues beyond that.


If I was in Redclaok’s and Xykon’s shoes I would suspect Oona and her tribe of being the perpetrators before the MitD: MitD has been a member of TE for years without ever causing problems while the bugbears are new, they don’t have the hobgoblins’ respect for Redcloak’s authority they have ample opportunity to mark the doors while TE is otherwise occupied inside the tomb and they have a mobile: by marking some doors (the most plentiful?) they protect their ressources.

bugvears do tend to be chaotic after all.

[Squire Doodad]

Yes but all that means is that monsters are born sometimes, it might be natural reproduction. She was explictly worried about them killing too many monsters. The bugbears’ expeditions were motivated by a need for food and raw materials, TE’s systemic exploration is leagues beyond that.


If I was in Redclaok’s and Xykon’s shoes I would suspect Oona and her tribe of being the perpetrators before the MitD: MitD has been a member of TE for years without ever causing problems while the bugbears are new, they don’t have the hobgoblins’ respect for Redcloak’s authority they have ample opportunity to mark the doors while TE is otherwise occupied inside the tomb and they have a mobile: by marking some doors (the most plentiful?) they protect their ressources.

While it'll never actually come up, I'm pretty sure that a couple of the caves have been already marked by the Bugbears to help make sure they have some monsters left in a worst case scenario.

[Wizard_Lizard]

While it'll never actually come up, I'm pretty sure that a couple of the caves have been already marked by the Bugbears to help make sure they have some monsters left in a worst case scenario.

but what if one of them has the gate (what gate?) in it?

[lio45]

I remember the thread, and I believe the conclusion is that it was a statistical equivalence, but a "maybe worth it" risk: there is a chance he would eventually force them to start over, and a chance he will speed them up, and they cancel each other out statistically, but might be worth it as a gamble. More importantly, like O-Chul points out, MitD is now clearly trying to hinder Team Evil, which is an advantage in and of itself.

Kish is 100% correct; the above is incorrect.

Removing random* unchecked doors from the pool does not affect the progress of the search at all. Team Evil continues to pick among what's left with the same probability as before.

Either TE happens to find the Gate before MitD happened to mark it treasonously, in which case MitD didn't hinder nor help, or else TE runs out of doors because MitD happened to mark the right one among the unexplored ones he was treasonously picking at random, in which case TE has to start over (greatly hindered).



*(keyword being random: it's not the Monty Hall problem, it's the Monty Hall problem but with the difference being that the host now randomly opens any of the two doors that you didn't pick, revealing the item 1/3 of the time in which case you just lose, and offering to switch - which is now a wash)

[lio45]

With three doors in all cases:


1) Monty Hall version:
Xykon picks one door at random;
The Oracle puts a red 'X' on one of the two remaining doors certifying that it's an empty cave;
We ask Xykon whether he wants to switch his original choice of door to the one remaining other door.

Xykon has a 2/3 chance of finding the Gate in the other door, and a 1/3 chance of finding the Gate in the original door.



2) Version that is actually happening in the comic:
Xykon picks one door at random;
MitD puts a red 'X' on one of the two remaining doors at random;
We ask Xykon whether he wants to switch his original choice of door to the one remaining other door.

Xykon has a 1/3 chance of finding the Gate in the other door, a 1/3 chance of finding the Gate in the original door. There's a 1/3 chance the Gate is in the door marked by MitD. Xykon's odds are unaffected by the random reduction in the number of doors available.

[Aspheric]

2) Version that is actually happening in the comic:
Xykon picks one door at random;
MitD puts a red 'X' on one of the two remaining doors at random;
We ask Xykon whether he wants to switch his original choice of door to the one remaining other door.

Xykon has a 1/3 chance of finding the Gate in the other door, a 1/3 chance of finding the Gate in the original door. There's a 1/3 chance the Gate is in the door marked by MitD. Xykon's odds are unaffected by the random reduction in the number of doors available.

The Monty Hall problem only really works with the scenario of the game show. None of this really works here because there are: a) more than three doors; b) no reveals for doors that don't contain the Gate; c) no Host who knows where the actual gate is located; and most importantly, d) no reason to suspect that the random chance will have greater impact on the plot than what the narrative demands. This also assumes that MitD removes only as many choices as Xykon/the rest of TE makes, which clearly isn't the case. Xykon's odds are reduced by MitD doing this, since he's actively removing potential answers from the board. If we're both drawing straws blindly for a special rainbow straw, and I take 5 straws every time you take one, you definitely have a worse chance of getting the rainbow straw. And if my only goal, like MitD's, is only to make sure you don't get the rainbow straw, it's even worse since you have no idea whether or not I might have picked it long ago.

It's also worth noting, though, that statistics only measure probability. It's absolutely possible to flip a coin four times and only get tails, even though it's more likely to get tails and heads twice. And, since we're guaging probability in a scenario where Rich holds all the dice the actual chance doesn't really matter. I mean, this is a comic where a one-in-a-million chance to summon a demon succeeds purely by virtue of its relative improbability. Whatever happens will happen to serve the story Rich wrote, not because of a statistical chance that MitD hindered/helped to find the gate.

[Ruck]

You're right, it's not actually a Monty Hall Problem here.

The short version of what's happening is: The chances of Team Evil finding the correct door by the time all the doors are marked, using their original method, is 100%*. The chances of Team Evil finding the correct door by the time all the doors are marked, with MitD's interference, is < 100%.

(* - assuming, of course, the gate is in fact behind one of the doors.)

[Peelee]

The Monty Hall problem only really works with the scenario of the game show. None of this really works here because there are: a) more than three doors;

That's the only part I take issue with - the number of doors doesn't really matter, so long as theres a knowledgeable entity opening incorrect doors for you.

[lio45]

As I said, the one reason it's not a Monty Hall problem is because the doors that get removed from the pool of available doors get removed at random (by someone who doesn't know any better than you), instead of getting removed because they aren't the door you're looking for, by an omniscient/reliable force.

The number of doors is irrelevant. Peelee's earlier example with a billion doors is still a "Monty Hall Problem".

If there are three doors, and one contains a prize, and you pick one, and I, without any knowledge, decide that one of the two remaining ones is off the table, and you're then offered a choice of keeping your original pick or switching to the one remaining door available, there's no benefit to switching; your odds are 50%/50%.

What turns it into the Monty Hall problem is the fact that the door I'm taking off the table is a certified wrong door. If I instead take a door off the table randomly, then switching your pick won't affect your odds at all; it's one random door vs another just as random door.

To illustrate with simple round numbers: if there are 100 doors, and MitD marks one extra random door per door Team Evil actually checks, the odds are rigorously identical for the first 50 doors that Team Evil will open (they're picking doors at random among the remaining available doors). At that point, either they've found the Gate (the 50% of cases where MitD's sabotage had no effect; was neither positive nor negative), or else they haven't and their methodical search has been ruined (the other 50%), causing them great delay.

On average, MitD's actions are undeniably negative for Team Evil. Zero possible benefit, while they may cause TE to have to start over.


ETA:

Xykon's odds are reduced by MitD doing this, since he's actively removing potential answers from the board. If we're both drawing straws blindly for a special rainbow straw, and I take 5 straws every time you take one, you definitely have a worse chance of getting the rainbow straw.

If there are 100 straws, and one rainbow straw in there, and every time I randomly draw a straw, you randomly take 5 straws away, you are not affecting my odds at all for my first 17 draws. (And then I'll run out of straws to draw from.)

And if every time I draw a straw, you randomly draw five, and keep one of them (chosen randomly among the five) for yourself while putting the other four away, we have equal odds of finding the rainbow straw first.

[Jasdoif]

There's an awful lot of room for variance in this scenario. Key among them the possibility that what they're looking for isn't actually there to find, how quickly/fully Monster Hollow repopulates, and what exactly Xykon and/or Redcloak will do if/when they discover what MitD's been up to. But to the extent I can look at the scenario....

There are two important factors:

• The chance of Team Evil finding the Gate before starting over...is the number of doors they search, divided by the number of doors there are to search (each door MitD marks decreases the chance of the correct door being searched by Team Evil)
• The number of days Team Evil spend searching doors...is based on the number of doors they actually search (each door MitD marks decreases the time Team Evil spends on searching doors before starting over, and could possibly decrease the time Team Evil spent searching doors before finding the Gate)

If the question is whether MitD is making Team Evil take longer to find the Gate, then let's find out whether MitD makes Team Evil have to search more doors than they would have without MitD's subterfuge.

Spoiler: I'm Not Sure How Much We're Actually Caring About the Details at this Point

Show

So if Team Evil was searching the doors as they expect they're searching the doors, they'll find the Gate somewhere between and including the very first door they search, and the only door left after they've searched every single one of the other doors. So on average, halfway through the doors. We'll make that the goal for MitD to beat: If Team Evil conducts more searches than half the total number of doors, he's made them take longer.


If MitD marks one (extra) door for every door Team Evil searches...that means Team Evil searches at most half the doors. So half the time, MitD marked the Gate door and Team Evil searches half the number of doors before starting over and searching doors again; and the other half, Team Evil finds the Gate after searching at most half the number of doors....Okay, I like this approach because the only probability that matters is that of MitD marking the Gate door; it's irrelevant where in the run the Gate door is, so we don't have to bother accounting for that at all.

Okay, so at 1:1 it's an even chance of stalling Team Evil.

Now, if MitD marks three (extra) doors for every door Team Evil searches...that means Team Evil searches at most one quarter of the doors. So three quarters of the time, MitD marked the Gate door and Team Evil searches one quarter the number of doors before starting over and searching doors again....That means he'd need to mark the Gate door a second time, after Team Evil starts over; but determining the odds for that is pretty easy: multiply the (3/4) chance by another (3/4) chance, for (9/16).

56.25%. Better than half!

And so five (extra) doors means one sixth total get searched before starting over; and a five-sixths chance of starting over, which has to happen three times...(5/6)³ is (125/216).

Around 57.87%. A small improvement, but definitely an improvement.

---

A formula for this, where "k" is the number of extra doors for each searched door, would be

(k / (k + 1))^{((k + 1) / 2)}

, which converges around a 60.653% chance of MitD delaying Team Evil from finding the Gate.

I feel comfortable saying MitD is could reasonably delay Team Evil if/while he's marking more (extra) doors than have actually been searched.

[Aspheric]

The number of doors is irrelevant. Peelee's earlier example with a billion doors is still a "Monty Hall Problem".

The fact that it's three doors is crucial to the Monty Hall set up. So yes, it is relevant. Adding more doors changes the actual percentages that make the ideal choice to switch relevant. But that doesn't matter, because Team Evil doesn't actually get that opportunity here, because this isn't equivalent to the game show whatsoever.

Your examples don't make sense, since they don't line up with the information we've been presented with. No one is facilitating a switch for TE. There's more than three doors. MitD is not falsely marking the same number of doors as TE, nor does he know for a fact where the Gate actually is. The only thing that lines the current situation up with the Monty Hall Problem is that they want something special that's hidden behind a door. The similarities end there.

If there are 100 straws, and one rainbow straw in there, and every time I randomly draw a straw, you randomly take 5 straws away, you are not affecting my odds at all for my first 17 draws. (And then I'll run out of straws to draw from.)

And if every time I draw a straw, you randomly draw five, and keep one of them (chosen randomly among the five) for yourself while putting the other four away, we have equal odds of finding the rainbow straw first.

No. My goal here isn't to make sure I get the rainbow straw. I just want to make sure you don't get it. Every straw I take is a straw you don't get to pick. You are always better off picking for straws on your own, without my interference, if you want the best result.

It's the same principle with the Gate. There's no way that MitD helps Team Evil's chances, period. If they pick the right door despite him covering up fakes, it wasn't because he helped them, it was because TE got lucky and pick the right door before MitD did. Will MitD actually succeed in hindering TE's search for the gate? No, probably not. It raises the stakes for the Order if Xykon and Redcloak get to the Gate, which makes a more interesting story, so that's the scenario Rich will likely write. But as far as strict probability is concerned, the more doors MitD falsely marks, the fewer chances TE has of picking the right door.

[Wizard_Lizard]

I love how we are solving a fictional scenario with math.

[Fyraltari]

I love how we are solving a fictional scenario with math.

Like there actually is a guy buying seventeen watermelons at $15.46 each.

[Wizard_Lizard]

Like there actually is a guy buying seventeen watermelons at $15.46 each.

Or someone recieving 20% interest per annum froma bank.

( Had that one in economics)

[Peelee]

The fact that it's three doors is crucial to the Monty Hall set up. So yes, it is relevant. Adding more doors changes the actual percentages that make the ideal choice to switch relevant.

Witg any number of doors, if some are removed by an entity that knows they are wrong, your odds are better of you switch. Maybe not significantly better, but always better. The three doors only seem relevant because the actual show used three because it was simple and practical, but as far as the math goes, no, the number of doors doesn't matter. All that matters is that incorrect options are removed and you have a chance to change your option.

[Fyraltari]

Witg any number of doors, if some are removed by an entity that knows they are wrong, your odds are better of you switch. Maybe not significantly better, but always better. The three doors only seem relevant because the actual show used three because it was simple and practical, but as far as the math goes, no, the number of doors doesn't matter. All that matters is that incorrect options are removed and you have a chance to change your option.

Well, that depends: with four doors, you go from 1/4 chance of success to 1/3 by switching, improving your odds by 8,3%. With three your odds improve by 16,6%, that's twice as much change.

[Ruck]

Well, that depends: with four doors, you go from 1/4 chance of success to 1/3 by switching, improving your odds by 8,3%. With three your odds improve by 16,6%, that's twice as much change.

In the Monty Hall Problem, you go from 1/3 chance of succeeding to 2/3 by switching with three doors, 1/4 to 3/4 by switching with four doors, etc.

[Fyraltari]

In the Monty Hall Problem, you go from 1/3 chance of succeeding to 2/3 by switching with three doors, 1/4 to 3/4 by switching with four doors, etc.

I re-looked into this and you are half right. Yes in the classic set-up you go from 1/3 to 2/3 because as

Spoiler: this tree

Show

shows there are actually three starting points for the second choice and in two of them changing automatically means getting the right door.
Which is a 33.3333...% increase in chances to be right


However with four doors, in addition to now having four starting points, changing your answer only gives you 1/2 chance to get the right answer, as beyond the door you first chose and the door the host eliminated there remains two doors. This means that of the four starting points, one leads to a wrong anwser whatever you choose when changing (you had the right answer to begin with) and three leads to either the right or aone wrong answer when choosing (you had one of the wrong answers originally). So your chances are actually 3/8.
This is still better odds than sticking with your first answer but only by: 3/8-1/4 = 1/8 = 12.5%


With five doors, switching give you 4/15 chances of getting the right answer against 1/5 if you stick that is a 1/15 = 6.666...% increase.

The formulae are, with N the number of door:
-chance of success by sticking: 1/N
-Chance of success by switching: (N-1)/(N²-2N)
-Increase of odds by switching: (N-1)/(N²-2N) - 1/N = 1/(N²-2N)

[Peelee]

I re-looked into this and you are half right. Yes in the classic set-up you go from 1/3 to 2/3 because as

Spoiler: this tree

Show

shows there are actually three starting points for the second choice and in two of them changing automatically means getting the right door.
Which is a 33.3333...% increase in chances to be right


However with four doors, in addition to now having four starting points, changing your answer only gives you 1/2 chance to get the right answer, as beyond the door you first chose and the door the host eliminated there remains two doors. This means that of the four starting points, one leads to a wrong anwser whatever you choose when changing (you had the right answer to begin with) and three leads to either the right or aone wrong answer when choosing (you had one of the wrong answers originally). So your chances are actually 3/8.
This is still better odds than sticking with your first answer but only by: 3/8-1/4 = 1/8 = 12.5%


With five doors, switching give you 4/15 chances of getting the right answer against 1/5 if you stick that is a 1/15 = 6.666...% increase.

The formulae are, with N the number of door:
-chance of success by sticking: 1/N
-Chance of success by switching: (N-1)/(N²-2N)
-Increase of odds by switching: (N-1)/(N²-2N) - 1/N = 1/(N²-2N)

The point is, no matter how many doors there are, if any incorrect ones are removed, then switching gives you better odds. It may be practically insignificant (eg a billion doors and one removed), but it's still better odds.

[lio45]

You're both correct, but Ruck is the only one of you two who has the right interpretation of the problem.

The host opens all the wrong doors but one, not only one wrong door. (In Fyraltari's defense, with only three doors, those scenarios are indistinguishable.)

[Fyraltari]

The point is, no matter how many doors there are, if any incorrect ones are removed, then switching gives you better odds. It may be practically insignificant (eg a billion doors and one removed), but it's still better odds.

Sure, but that's only because the host will never remove the right answer.

[lio45]

Sure, but that's only because the host will never remove the right answer.

Exactly. In both your interpretation and Ruck's, your odds are still better if you switch after any number of certified wrong doors are taken off the table. The only difference is, in your version, the more doors there are, the less your odds are improved by switching; in Ruck's version, it's the opposite.

Aspheric, you're wrong about the number of doors bring "crucial", it's absolutely not. The basic problem is, there are choices, one is right, you pick blindly, then incorrect options are removed by an omniscient entity, then you're asked if you want to change your pick, and the right answer statistically is yes.

The fact that it's doors, that the prize is a car, that there are three doors, etc. are all irrelevant.

Also, if you wish to disagree with anything I said on probabilities, please point it out more precisely so I can show you it's correct.

I recall this forum had this exact discussion when that comic showed up, and I had the same position then, even posted it in that thread. (Some participants were wrong.) There's only one correct answer: MitD doesn't change the odds of picking the right door as long as there are doors to pick from, but as soon as TE runs out of doors or even just realizes the sabotage, they're hindered (their methodical search is ruined).