Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 19 20 [21] 22 23 ... 47  All

Author Topic: Maths thread.  (Read 307121 times)

0 Members and 3 Guests are viewing this topic.

singletee

  • Jester
  • *****
  • Offline Offline
  • Posts: 915
  • Shuffle iT Username: singletee
  • Gold, Silver, Copper, Let's Jam!
  • Respect: +1606
    • View Profile
Re: Maths thread.
« Reply #500 on: August 07, 2015, 04:00:40 pm »
0

it's certainly not option B. The two options in my mind for step 4 are:
A. Host chooses a completely random door that isn't the contestant's current door or the car door.I'd say this is 99/103 and TrojH concurs.

B. Host chooses a door that isn't the contestant's current door or the car door but he doesn't choose equally between  the available doors, rather he chooses with a modified rate that will maximize his chances of winning. I'd say this is 50.5%

And in your option B, I'd say the odds are 99/101, not 99/100, but that's neither here nor there.

Actually, you're right, it can't be B, because there's no guarantee that a door can be opened at all, since the door with the car might be the only remaining not-chosen door.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #501 on: August 07, 2015, 04:16:14 pm »
+2

skip, it's your problem. Please give us a single, precisely formulated problem. Here's what I think you currently intend your problem to be, correct me if I am wrong:

There are 100 doors, one of which has a prize behind it, the others contain toasters. The contestant and host will play a game where the contestant wins if they open the door with the prize and the host wins if the contestant opens a door with a toaster. The steps of the game are:

1. Contestant selects a door
2. Host is forced to open 97 not-currently-chosen doors with toasters behind them of his choice
3. Contestant has the option to switch their selection to one of the other two closed doors.
4. Host is forced to open one more (closed) not-currently-chosen door with a toaster behind it of his choice.
5. Contestant opens one of the two closed doors of their choice.

Assuming the Host plays optimally, what is the Contestant's optimal strategy and what is his chance of winning?

If this is the specified problem, then the contestant can insure that he has a 99% chance of winning by not switching in step 3 and switching in step 5, and the Host is powerless to stop him. The contestant can't do better than this, clearly. TerminalCopper figured this out.

You seem to think that the contestant switched in step 3. Why did they do that? Were they playing a game which they didn't know the rules for? I hate playing games I don't know the rules for.
Logged

skip wooznum

  • Golem
  • ****
  • Offline Offline
  • Posts: 194
  • Shuffle iT Username: Skip Wooznum
  • he/him
  • Respect: +111
    • View Profile
Re: Maths thread.
« Reply #502 on: August 07, 2015, 04:17:00 pm »
0

it's certainly not option B. The two options in my mind for step 4 are:
A. Host chooses a completely random door that isn't the contestant's current door or the car door.I'd say this is 99/103 and TrojH concurs.

B. Host chooses a door that isn't the contestant's current door or the car door but he doesn't choose equally between  the available doors, rather he chooses with a modified rate that will maximize his chances of winning. I'd say this is 50.5%

And in your option B, I'd say the odds are 99/101, not 99/100, but that's neither here nor there.

Actually, you're right, it can't be B, because there's no guarantee that a door can be opened at all, since the door with the car might be the only remaining not-chosen door.
fair point.
Logged

skip wooznum

  • Golem
  • ****
  • Offline Offline
  • Posts: 194
  • Shuffle iT Username: Skip Wooznum
  • he/him
  • Respect: +111
    • View Profile
Re: Maths thread.
« Reply #503 on: August 07, 2015, 04:23:39 pm »
0

skip, it's your problem. Please give us a single, precisely formulated problem. Here's what I think you currently intend your problem to be, correct me if I am wrong:

There are 100 doors, one of which has a prize behind it, the others contain toasters. The contestant and host will play a game where the contestant wins if they open the door with the prize and the host wins if the contestant opens a door with a toaster. The steps of the game are:

1. Contestant selects a door
2. Host is forced to open 97 not-currently-chosen doors with toasters behind them of his choice
3. Contestant has the option to switch their selection to one of the other two closed doors.
4. Host is forced to open one more (closed) not-currently-chosen door with a toaster behind it of his choice.
5. Contestant opens one of the two closed doors of their choice.

Assuming the Host plays optimally, what is the Contestant's optimal strategy and what is his chance of winning?

If this is the specified problem, then the contestant can insure that he has a 99% chance of winning by not switching in step 3 and switching in step 5, and the Host is powerless to stop him. The contestant can't do better than this, clearly. TerminalCopper figured this out.

You seem to think that the contestant switched in step 3. Why did they do that? Were they playing a game which they didn't know the rules for? I hate playing games I don't know the rules for.
fine. Let's add a rule that says that once the contestant is offered the option to switch and declines, he is no longer able to switch later on. The game is over and he must keep his curtain. That should solve TC's issue.

And sorry for not keeping this restricted to a single problem, it's just I want to know what people think about the other problem as well. But the one you described is my priority.
« Last Edit: August 07, 2015, 04:29:55 pm by skip wooznum »
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: Maths thread.
« Reply #504 on: August 07, 2015, 04:23:49 pm »
0

If Monty offers you a switch a second time, switch to the Moat.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

skip wooznum

  • Golem
  • ****
  • Offline Offline
  • Posts: 194
  • Shuffle iT Username: Skip Wooznum
  • he/him
  • Respect: +111
    • View Profile
Re: Maths thread.
« Reply #505 on: August 07, 2015, 04:28:03 pm »
+2

If Monty offers you a switch a second time, switch to the Moat.
please keep solutions in spoilers. It's inconsiderate towards others.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #506 on: August 07, 2015, 04:59:20 pm »
+4

Okay. In that case it is best for the contestant to switch the first time, since surely he can do better than 1/100. Then we are playing the classical monty hall problem with the following modifications:

1. The car is not uniformly distributed between doors; it is behind the first with probability 2/200, the second 99/200, the third 99/200.
2. The contestant is forced to select door 2.
3. Then the host opens door 1 or 3, whichever has a goat behind it. If both have a goat the host chooses door 1 or 3 with a strategy which minimizes the chance that the contestant wins, instead of randomly as in the classical problem.
4. Then the contestant opens one of the two remaining closed doors of their choice

This is a fairly simple game to solve. The contestant has 4 pure strategies: Open door 1 if possible, else door 2, Open door 2, open door 3 if possible, else door 2, and open the other door. Call these strategies 1, 2, 3,  and 4, respectively. The host has two pure strategies: Open door 1, or open door 3 (since he only has a choice when both are goats). Here's a payoff table, where the payoff is that of the contestant and a win is +1, a loss -1. The payoff for the host is the negative.

                1          2          3        4
Door 1      .01       -.01     -.01     .01   

Door 3    -.98       -.01       .98     .01

Clearly it can never be better to choose strategies 1 or 2, so we just consider 3 and 4. Then it is never better for the host to choose to open door 3 if he has the choice, so then we are left with just Door 1, and strategies 3 and 4. Then of course the contestant should always switch, strategy 4.

So we got lucky and there was a pure-strategy equilibrium. The host should always open Door 1 if he has a choice*, and the contestant should always switch*. The contestant's expected payoff is than .01, or equivalently, he has a 101/200 = 50.5% chance of winning.

*Technically, the host could also open door 3 when he has a choice with probability up to and including 2/99, and then the contestant would be fine opening door 2 when the host opens door 3 if P(D3) = 2/99. The expected payoff remains the same of course.
« Last Edit: August 07, 2015, 06:33:15 pm by liopoil »
Logged

TrojH

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 169
  • Respect: +191
    • View Profile
Re: Maths thread.
« Reply #507 on: August 07, 2015, 05:17:54 pm »
0

liopoil, thanks for that detailed solution. It saved me from having to type up a solution of my own. :D

I concur with liopoil's answer.
Logged

skip wooznum

  • Golem
  • ****
  • Offline Offline
  • Posts: 194
  • Shuffle iT Username: Skip Wooznum
  • he/him
  • Respect: +111
    • View Profile
Re: Maths thread.
« Reply #508 on: August 07, 2015, 06:13:41 pm »
0

Okay. In that case it is best for the contestant to switch the first time, since surely he can do better than 1/100. Then we are playing the classical monty hall problem with the following modifications:

1. The car is not uniformly distributed between doors; it is behind the first with probability 2/200, the second 99/200, the third 99/200.
2. The contestant is forced to select door 2.
3. Then the host opens door 1 or 3, whichever has a goat behind it. If both have a goat the host chooses door 1 or 3 with a strategy which minimizes the chance that the contestant wins, instead of randomly as in the classical problem.
4. Then the contestant opens one of the two remaining closed doors of their choice

This is a fairly simple game to solve. The contestant has 4 pure strategies: Open door 1 if possible, else door 2, Open door 2, open door 3 if possible, else door 2, and open the other door. Call these strategies 1, 2, 3,  and 4, respectively. The host has two pure strategies: Open door 1, or open door 3 (since he only has a choice when both are goats). Here's a payoff table, where the payoff is that of the contestant and a win is +1, a loss -1. The payoff for the host is the negative.

                1          2          3        4
Door 1      .01       -.01     -.01     .01   

Door 3    -.01       -.01       .98     .01

Clearly it can never be better to choose strategies 1 or 2, so we just consider 3 and 4. Then it is never better for the host to choose to open door 3 if he has the choice, so then we are left with just Door 1, and strategies 3 and 4. Then of course the contestant should always switch, strategy 4.

So we got lucky and there was a pure-strategy equilibrium. The host should always open Door 1 if he has a choice*, and the contestant should always switch*. The contestant's expected payoff is than .01, or equivalently, he has a 101/200 = 50.5% chance of winning.

*Technically, the host could also open door 3 when he has a choice with probability up to and including 2/99, and then the contestant would be fine opening door 2 when the host opens door 3 if P(D3) = 2/99. The expected payoff remains the same of course.

ok, so the first thing I notice is we have the same result. Maybe I'm cut out for this math thing after all. Now I just need to figure out how you gou your result.

The first thing I don't understand isone entry on your table. If the contestant employs strategy 1, and the host always opens door 3 when possible, shouldn't the payout be -.98, because the contestant will only win if its behind door 1?
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #509 on: August 07, 2015, 06:32:42 pm »
0


                1          2          3        4
Door 1      .01       -.01     -.01     .01   

Door 3    -.01       -.01       .98     .01

Clearly it can never be better to choose strategies 1 or 2, so we just consider 3 and 4. Then it is never better for the host to choose to open door 3 if he has the choice, so then we are left with just Door 1, and strategies 3 and 4. Then of course the contestant should always switch, strategy 4.

So we got lucky and there was a pure-strategy equilibrium. The host should always open Door 1 if he has a choice*, and the contestant should always switch*. The contestant's expected payoff is than .01, or equivalently, he has a 101/200 = 50.5% chance of winning.

*Technically, the host could also open door 3 when he has a choice with probability up to and including 2/99, and then the contestant would be fine opening door 2 when the host opens door 3 if P(D3) = 2/99. The expected payoff remains the same of course.

The first thing I don't understand isone entry on your table. If the contestant employs strategy 1, and the host always opens door 3 when possible, shouldn't the payout be -.98, because the contestant will only win if its behind door 1?
You are correct, I will edit that now. That makes the table a bit more symmetric. It doesn't change the result.
Logged

WalrusMcFishSr

  • Minion
  • *****
  • Offline Offline
  • Posts: 642
  • An enormous walrus the size of Antarctica
  • Respect: +1793
    • View Profile
Re: Maths thread.
« Reply #510 on: August 08, 2015, 01:39:05 pm »
+4

Could you imagine the spectacle of 100-door Let's Make a Deal? I'm imagining a 10x10 wall of doors. Then simultaneously revealing 97 goats for virtually no reason! I'd watch it.
Logged
My Dominion videos: http://www.youtube.com/user/WalrusMcFishSr   <---Bet you can't click on that!

skip wooznum

  • Golem
  • ****
  • Offline Offline
  • Posts: 194
  • Shuffle iT Username: Skip Wooznum
  • he/him
  • Respect: +111
    • View Profile
Re: Maths thread.
« Reply #511 on: August 08, 2015, 09:37:22 pm »
0

Lio, how did you get to the host opening Door 3  2/99 of the time?
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #512 on: August 08, 2015, 10:35:36 pm »
0

Lio, how did you get to the host opening Door 3  2/99 of the time?
He needs to make sure that the utility of the contestant employing strategy 3 is never more than 0.01. If P(D3) is the probability he opens door 3, then the utility is .98 * P(D3) - .01 * (1 - P(D3)) = .99 * P(D3) - .01. This quantity is less than or equal to .01 only for P(D3) less than or equal to 2/99. For P(D3) = 2/99, there is equality and the contestant has equal utility with strategies 3 and 4.
Logged

skip wooznum

  • Golem
  • ****
  • Offline Offline
  • Posts: 194
  • Shuffle iT Username: Skip Wooznum
  • he/him
  • Respect: +111
    • View Profile
Re: Maths thread.
« Reply #513 on: August 08, 2015, 11:31:22 pm »
0

I just realized our answers are very different:
you're saying the host will open door 1 if he can, and the contestant should always switch (this is pre-your last paragraph). What this will result in is that in a situation where the host opens door 3, the contestant should switch for a guaranteed win. What you are referring to when you say 50.5% are the contestants chances before the game begins. What I was saying, was that at the point that the host opens door 3, there is a 50.5% it's in door 1.
« Last Edit: August 09, 2015, 03:08:39 am by skip wooznum »
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: Maths thread.
« Reply #514 on: August 08, 2015, 11:35:44 pm »
+4

As is common with math problems, xkcd has the best answer:

Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #515 on: August 08, 2015, 11:38:41 pm »
0

Hmmm, well I disagree with that. I'd say there is anywhere from a 97/99 to 1 probability that it is in the first door given the third was revealed. The host is really hoping the prize isn't in Door 1.
Logged

skip wooznum

  • Golem
  • ****
  • Offline Offline
  • Posts: 194
  • Shuffle iT Username: Skip Wooznum
  • he/him
  • Respect: +111
    • View Profile
Re: Maths thread.
« Reply #516 on: August 08, 2015, 11:53:48 pm »
0

Hmmm, well I disagree with that. I'd say there is anywhere from a 97/99 to 1 probability that it is in the first door given the third was revealed. The host is really hoping the prize isn't in Door 1.
what's wrong with saying that the host will open door one with probability 22/1111 in situations where he has a choice? If he does this does the contestant have some strategy that will give him better than 50.5% odds of winning? And wouldn't the host doing this get us to a 50.5% chance that it's behind door 1 and 49.5% chance it's in door 2?
Logged

skip wooznum

  • Golem
  • ****
  • Offline Offline
  • Posts: 194
  • Shuffle iT Username: Skip Wooznum
  • he/him
  • Respect: +111
    • View Profile
Re: Maths thread.
« Reply #517 on: August 09, 2015, 03:01:25 am »
0

Just realized I completely don't understand what you're saying :P. if the host opens door three 2 out of the 99 times where he has a choice (which is what you suggest is part of the range for most optimal strategy), then in 200 cases, door 3 will be opened 4 times; twice when it's actually in door 1, and twice when it's in door 2 (the other 97 times it's in door 2, he'd open door 1). Am I understanding all this correctly? If so, then in a situation where the host opens door 3, wouldn't you have a 50/50 shot? Out of 4 possible scenarios, there are 2 that would mean door two is correct and 2 that door one is correct. 
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #518 on: August 09, 2015, 09:05:00 am »
0

Hmmm, well I disagree with that. I'd say there is anywhere from a 97/99 to 1 probability that it is in the first door given the third was revealed. The host is really hoping the prize isn't in Door 1.
what's wrong with saying that the host will open door one with probability 22/1111 in situations where he has a choice? If he does this does the contestant have some strategy that will give him better than 50.5% odds of winning? And wouldn't the host doing this get us to a 50.5% chance that it's behind door 1 and 49.5% chance it's in door 2?
22/1111 = 2/101 < 2/99, so sure, the host can do that. Those probabilities are correct. But there's nothing special about 2/101, as far as I can see.

Oops, I got ahead of myself again. Yes, then the contestant has a 50/50 shot. In fact, this makes sense, because 2/99 is the point where strategies 3 and 4 are equally good, because they differ only in the case where door 3 is opened. So then there is anywhere from a 1/2 to 1 probability that the car is behind door 1, given door 3 was opened. So to be on the safe side, you should probably open door 1. This number is not uniquely determined because the strategy for the host is not uniquely determined; any value from 0 to 2/99 for the probability he opens door 3 if he has a choice yields the same expected payoff for the contestant: 1/100. If P(D3) =  x, then the probability it is in door 2 given door 3 was opened is (99x)/(2 + 99x), which ranges over all real values between 0 and 1/2 for x in [0, 2/99].
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #519 on: August 09, 2015, 09:11:47 am »
0

His best strategy is one that gives you the same chance of winning no matter what he does.
So this I think is your error. Because the host's actions depend on where the car is, and the contestant's chance of winning also depends on where the car is, the contestant's chance of winning changes depending on which door is opened. What IS true, and what's true for many many (all?) games, is that the contestant's expected payoff is the same no matter which of the pure strategies the host randomly adopts.

As it turns out, the host can achieve this equality and in fact it is a valid strategy for him. However, there are infinitely many others which don't have this symmetry but achieve the same outcome.
« Last Edit: August 09, 2015, 09:16:14 am by liopoil »
Logged

skip wooznum

  • Golem
  • ****
  • Offline Offline
  • Posts: 194
  • Shuffle iT Username: Skip Wooznum
  • he/him
  • Respect: +111
    • View Profile
Re: Maths thread.
« Reply #520 on: August 09, 2015, 09:34:11 am »
0

His best strategy is one that gives you the same chance of winning no matter what he does.
So this I think is your error. Because the host's actions depend on where the car is, and the contestant's chance of winning also depends on where the car is, the contestant's chance of winning changes depending on which door is opened. What IS true, and what's true for many many (all?) games, is that the contestant's expected payoff is the same no matter which of the pure strategies the host randomly adopts.

As it turns out, the host can achieve this equality and in fact it is a valid strategy for him. However, there are infinitely many others which don't have this symmetry but achieve the same outcome.

right. So I assumedthat the host would try to keep an equality that would make it that whatever door the host opens, the contestant still has a 50.5% chance. You're saying that that isn't exclusively the best strategy; as long as the host's strategy gives the contestant 50.5% of winning originally,  that strategy is optimal regardless of how the odds change later on. Gotchya. Anyway, thanks everyone for helping out, I hope this wasnt too primitive for you guys.
Logged

scott_pilgrim

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1102
  • Respect: +2144
    • View Profile
Re: Maths thread.
« Reply #521 on: August 26, 2015, 04:25:11 pm »
0

Here's a fun problem I came up with.  Writing a program to solve it is cheating.  (Very minor hint:) You should be able to solve it without using a calculator at all.

In a particular family, every man has one son and one daughter, and every woman has two sons and one daughter.  What is the difference between the number of great great...(100 total greats) grandsons a man in this family will have, and the number of great great...(100 total greats) granddaughters a woman in this family will have?

(Only the original man/woman and his/her descendants count as being "in the family".)
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #522 on: August 26, 2015, 05:17:57 pm »
+2

A grandchild is two generations, so we are counting the men/women in the 102nd generation, where the original person is the 0th generation.

To count the daughters, we count the total number of people in the 101th generation starting with a woman.

To count the sons, we count the total number of people in the 101th generation starting with a man, then add the number of women in the 101th generation starting with a man.

The number of women in the 101th generation starting with a man is the total number of people in the 100th generation starting with a man.

Let mi denote the set of people in the ith generation starting with a man, and wi denote the set of people in the ith generation starting with a woman. Note that w1 = m1 U m0. In each subsequent generation, the sets generate offspring independently, and so by induction w101 = m101 U m100. Therefore the difference is 0.

There is probably a more elegant way to state the solution, and maybe there is a better notation for what I did. The inductive step feels kind of handwavy.
Logged

scott_pilgrim

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1102
  • Respect: +2144
    • View Profile
Re: Maths thread.
« Reply #523 on: August 26, 2015, 06:25:39 pm »
+1

A grandchild is two generations, so we are counting the men/women in the 102nd generation, where the original person is the 0th generation.

To count the daughters, we count the total number of people in the 101th generation starting with a woman.

To count the sons, we count the total number of people in the 101th generation starting with a man, then add the number of women in the 101th generation starting with a man.

The number of women in the 101th generation starting with a man is the total number of people in the 100th generation starting with a man.

Let mi denote the set of people in the ith generation starting with a man, and wi denote the set of people in the ith generation starting with a woman. Note that w1 = m1 U m0. In each subsequent generation, the sets generate offspring independently, and so by induction w101 = m101 U m100. Therefore the difference is 0.

There is probably a more elegant way to state the solution, and maybe there is a better notation for what I did. The inductive step feels kind of handwavy.


That looks right, but you did it a little differently from me.  You can make some really cool sequences for the number of males, females, or total in each generation, and then do stuff with those.  The sequences follow a pattern similar to the Fibonacci numbers, so I tried to ask a question that you could answer without having a program generate the numbers for you, but I guess you don't actually need the sequences to answer that question.
Logged

jonts26

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2746
  • Shuffle iT Username: jonts
  • Respect: +3668
    • View Profile
Re: Maths thread.
« Reply #524 on: September 30, 2015, 07:22:17 pm »
+13

Logged
Pages: 1 ... 19 20 [21] 22 23 ... 47  All
 

Page created in 0.083 seconds with 21 queries.