0
$\begingroup$

Consider a simple example where I have a prize behind one of two doors.

The prize is $1.90.

I will let you choose a door for $1.00.

If you choose the winning door first, you can walk away. If you choose the losing door first, you can pay me another dollar to open the other door.

So you'll either win on the first door and walk away with \$0.90 profit, or you'll lose on the first door, pay another dollar to open the second, and walk away with a -$0.10 loss.

1/2 * \$0.90 + 1/2 * -\$0.10 = $0.40 expected value.

How can this be extrapolated to a larger number of doors and a wider variety of prizes?

For example, 10 doors with 1 prize of \$7 and 2 prizes of \$1 and the rest \$0.

Edit with image for clarification: 3 Doors with values [3, 1, 0]

In this particular case I could just stop on "3" because it's obvious that's I can't win more. But how could I somehow programmatically or mathematically determine when the best place to stop is and what the expected value of the game is when I stop there?

$\endgroup$

1 Answer 1

0
$\begingroup$

First, you need to specify the conditions (whether deterministic or probabilistic) that a person will stop on. IE, they'll stop as soon as they profit, or they'll stop with probability (Profit/\$1).

Then, this just becomes a probability tree. In your given example, you had two branches: 50% chance they took the door with the prize and 50% they didn't. If you expand to your 10 door version, you start with 3 branches: .1 probability of \$7, .2 probability of \$1 and .7 probability of \$0.

After each branch, depending on your stop conditions, you'll either terminate at that point, or have further branches, which will be different based on which branch you're on.

Let's say that your stop condition is that you have to have profited (deterministic) to make things simpler. Then your \$7 branch and your \$1 branch are both immediate stops, and only the \$0 branch expands. The next step branches as follows: (1/9) chance of \$7, (2/9) chance of \$1, (6/9) chance of \$0.

You can repeat until your tree is complete with every end node being a point at which your player would stop.

Then, each end node has a probability equal to the product of every branch probability along the way.

For example, the end node of \$0 followed by \$7 would have a probability of 7/10 * 1/9 = 7/90.

Once you have a probability for each end node, you multiply by that node's value to calculate your expected value in the usual way.

$\endgroup$
4
  • $\begingroup$ Thanks. I'm trying to work through this again given what you said and I think I should have asked the question another way. What you said makes sense and I can work it out for some stopping condition, such as having made a profit. I'm stuck on figuring out how to do it if my stopping condition is: Stop if the value of stopping is greater than the value of continuing. I'm going to edit my question so I can get better formatting for a visualization. $\endgroup$
    – Eric Ihli
    Oct 23, 2018 at 15:16
  • $\begingroup$ Work out the probability tree for not stopping (IE, fully open all doors). Then evaluate your stopping condition backwards from the leaves, eliminating leaves where you'd have stopped at the previous point. As you do this, it will revise your expected value for each branch, all the way back to the start. I recommend using code to do this if you're doing it for anything larger than n=3. $\endgroup$
    – JKreft
    Oct 23, 2018 at 18:15
  • $\begingroup$ Makes sense. Got some working code. But my n = 12. What is that... 12! + 11! + 10!... possible nodes that I need to do calculations for? It was just too slow. Haven't been able to figure out a way to make it work. $\endgroup$
    – Eric Ihli
    Oct 25, 2018 at 15:11
  • $\begingroup$ As a shortcut, you can stop each branch when there are no doors with prizes left, since it will only get worse from there. That cuts down your cases significantly. Also, if you run this in C# with good code or MATLAB with decent code, it should compute in under a day. $\endgroup$
    – JKreft
    Oct 25, 2018 at 19:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .