Interesting Math Puzzle from 538.com

[silverscreenselect]

They've started a weekly contest on Friday at www.fivethirtyeight.com in which they have a puzzle that requires math or logic to solve. They will post the answer the next Friday. You don't get any prize for winning other than a shout out on their website if you are the "big" winner, but this week's puzzle at least is challenging.

Two players go on a hot new game show called “Higher Number Wins.” The two go into separate booths, and each presses a button, and a random number between zero and one appears on a screen. (At this point, neither knows the other’s number, but they do know the numbers are chosen from a standard uniform distribution.) They can choose to keep that first number, or to press the button again to discard the first number and get a second random number, which they must keep. Then, they come out of their booths and see the final number for each player on the wall. The lavish grand prize — a case full of gold bullion — is awarded to the player who kept the higher number. Which number is the optimal cutoff for players to discard their first number and choose another? Put another way, within which range should they choose to keep the first number, and within which range should they reject it and try their luck with a second number?

Intuitively, you would think the answer should be .5 because at that point your odds are 50/50 of improving or not. But if your opponent adopts that strategy, he's going to wind up with a number higher than .5 some 75% of the time, so if you stay on .5, you rate to lose. So your answer should be some number higher than .5, but I'm not sure what it is right now.

Here's the link to the puzzle: http://fivethirtyeight.com/features/can ... game-show/

[SpacemanSpiff]

They've started a weekly contest on Friday at http://www.fivethirtyeight.com in which they have a puzzle that requires math or logic to solve. They will post the answer the next Friday. You don't get any prize for winning other than a shout out on their website if you are the "big" winner, but this week's puzzle at least is challenging.

Two players go on a hot new game show called “Higher Number Wins.” The two go into separate booths, and each presses a button, and a random number between zero and one appears on a screen. (At this point, neither knows the other’s number, but they do know the numbers are chosen from a standard uniform distribution.) They can choose to keep that first number, or to press the button again to discard the first number and get a second random number, which they must keep. Then, they come out of their booths and see the final number for each player on the wall. The lavish grand prize — a case full of gold bullion — is awarded to the player who kept the higher number. Which number is the optimal cutoff for players to discard their first number and choose another? Put another way, within which range should they choose to keep the first number, and within which range should they reject it and try their luck with a second number?

Intuitively, you would think the answer should be .5 because at that point your odds are 50/50 of improving or not. But if your opponent adopts that strategy, he's going to wind up with a number higher than .5 some 75% of the time, so if you stay on .5, you rate to lose. So your answer should be some number higher than .5, but I'm not sure what it is right now.

Kind of sounds like how "Card Sharks" worked, except for the knowing what the opposition has.


Here's the link to the puzzle: http://fivethirtyeight.com/features/can ... game-show/

[BackInTex]

My first random number in my Excel model was .991885.

I think I stay. Probably will go home with the gold!

Will get back to you on what I think the optimum number is, though the assumption has to be your opponent will use the same thought process. Your opponent is an uncontrollable input. If you could judge your opponent and guess if they will use .5 as their number or not, it should change that 'optimal' number.

[smilergrogan]

Intuitively, you would think the answer should be .5 because at that point your odds are 50/50 of improving or not. But if your opponent adopts that strategy, he's going to wind up with a number higher than .5 some 75% of the time, so if you stay on .5, you rate to lose.

But you will also wind up higher than 0.5 75% of the time, so you will have a 50% chance of winning. This is true no matter the cutoff number as long as your opponent uses the same strategy as you.

So your answer should be some number higher than .5, but I'm not sure what it is right now.

0.5 maximizes your expectation value for your final number at 0.625. Anything higher or lower than 0.5 decreases the expectation value symmetrically, so you will have no worse than a 50% chance of winning if you make the cutoff 0.5 (For example, at cutoffs of 0.2 and 0.8, the expectation value becomes 0.58. This assumes there is a distinct cutoff value which you and your opponent follow 100% of the time, but I don't think you can improve your odds with a different strategy.

[jarnon]

I submitted this answer:

Spoiler

(√5 - 1)/2 = 0.618, the Golden Ratio

.

[plasticene]

I submitted this answer:

Spoiler

(√5 - 1)/2 = 0.618, the Golden Ratio

.

I believe the answer is

Spoiler

√5 - 1

. If you use that as your threshold, there is no way for your opponent to gain an advantage by choosing a different threshold. If I use my answer and you use your answer, I'll win about 52.5% of the time.

I used a little bit of brute force to come up with that. I won't submit it unless I can figure out how to derive it from first principles.

[Bob78164]

I submitted this answer:

Spoiler

(√5 - 1)/2 = 0.618, the Golden Ratio

.

I believe the answer is

Spoiler

√5 - 1

. If you use that as your threshold, there is no way for your opponent to gain an advantage by choosing a different threshold. If I use my answer and you use your answer, I'll win about 52.5% of the time.

I used a little bit of brute force to come up with that. I won't submit it unless I can figure out how to derive it from first principles.

Isn't your answer larger than 1? --Bob

[smilergrogan]

I submitted this answer:

Spoiler

(√5 - 1)/2 = 0.618, the Golden Ratio

.

I believe the answer is

Spoiler

√5 - 1

. If you use that as your threshold, there is no way for your opponent to gain an advantage by choosing a different threshold. If I use my answer and you use your answer, I'll win about 52.5% of the time.

I used a little bit of brute force to come up with that. I won't submit it unless I can figure out how to derive it from first principles.

Huh? You must be understanding the question in a different way than I am.

If I choose 0.5 as the cutoff, then half the time the first number will be higher and on average that number will be 0.75 (evenly distributed between 0.5 and 1). The other half of the time it will be less than 0.5 so I will get a 2nd number which will be on average 0.5 (evenly distributed between 0 and 1). So my expectation value is 50% of 0.75 + 50% of 0.5 = 0.625

If I choose 0.618 as the cutoff, then 38.2% of the time the first number will be higher and on average that number will be 0.809 (evenly distributed between 0.618 and 1). The other 61.8% of the time it will be less than 0.618 so I will get a 2nd number which will be on average 0.5 (evenly distributed between 0 and 1). So my expectation value in that case is 38.2% of 0.809 + 61.8% of 0.5 = 0.618. How does that beat the first option?

[Bob78164]

I submitted this answer:

Spoiler

(√5 - 1)/2 = 0.618, the Golden Ratio

.

I believe the answer is

Spoiler

√5 - 1

. If you use that as your threshold, there is no way for your opponent to gain an advantage by choosing a different threshold. If I use my answer and you use your answer, I'll win about 52.5% of the time.

I used a little bit of brute force to come up with that. I won't submit it unless I can figure out how to derive it from first principles.

Huh? You must be understanding the question in a different way than I am.

If I choose 0.5 as the cutoff, then half the time the first number will be higher and on average that number will be 0.75 (evenly distributed between 0.5 and 1). The other half of the time it will be less than 0.5 so I will get a 2nd number which will be on average 0.5 (evenly distributed between 0 and 1). So my expectation value is 50% of 0.75 + 50% of 0.5 = 0.625

If I choose 0.618 as the cutoff, then 38.2% of the time the first number will be higher and on average that number will be 0.809 (evenly distributed between 0.618 and 1). The other 61.8% of the time it will be less than 0.618 so I will get a 2nd number which will be on average 0.5 (evenly distributed between 0 and 1). So my expectation value in that case is 38.2% of 0.809 + 61.8% of 0.5 = 0.618. How does that beat the first option?

Because the issue isn't expectation value. It's frequency. It's possible that a few "large" losses swamp a number of "small" wins. Your analysis doesn't rule out that possibility.

Simple calculus easily demonstrates that 0.5 maximizes your expectation value, but that doesn't necessarily mean it's the correct answer to this question. --Bob

[Bob78164]

They've started a weekly contest on Friday at http://www.fivethirtyeight.com in which they have a puzzle that requires math or logic to solve. They will post the answer the next Friday. You don't get any prize for winning other than a shout out on their website if you are the "big" winner, but this week's puzzle at least is challenging.

Two players go on a hot new game show called “Higher Number Wins.” The two go into separate booths, and each presses a button, and a random number between zero and one appears on a screen. (At this point, neither knows the other’s number, but they do know the numbers are chosen from a standard uniform distribution.) They can choose to keep that first number, or to press the button again to discard the first number and get a second random number, which they must keep. Then, they come out of their booths and see the final number for each player on the wall. The lavish grand prize — a case full of gold bullion — is awarded to the player who kept the higher number. Which number is the optimal cutoff for players to discard their first number and choose another? Put another way, within which range should they choose to keep the first number, and within which range should they reject it and try their luck with a second number?

Intuitively, you would think the answer should be .5 because at that point your odds are 50/50 of improving or not. But if your opponent adopts that strategy, he's going to wind up with a number higher than .5 some 75% of the time, so if you stay on .5, you rate to lose. So your answer should be some number higher than .5, but I'm not sure what it is right now.

Here's the link to the puzzle: http://fivethirtyeight.com/features/can ... game-show/

This analysis can't be right. If you and your opponent adopt the same strategy, your odds of winning must be 50-50. The problem with your analysis is that if you decide to redraw when you get 0.5, you will decrease your chances of winning half the time.

I don't have time to work through the analysis right now, but I think the right approach is to assume that you choose x, fixed, as your cutoff and then let your opponent choose y, variable, as hers. You want to choose x that maximizes your minimum (which will occur when your opponent also chooses x). I believe Nash's Theorem still applies in this setting, in which case that choice of x is the best you can do.

You then have 4 possibilities to consider -- you and your opponent each do or do not end up with a first number below the chosen cutoff. In each case, with a little care you can figure out the likelihood that you win. The values of x and y tell you how likely you are to fall into each of the four cases, and your likelihood of winning then falls out as a function of x and y.

You probably have to do the analysis twice, once assuming x < y, and once assuming x > y. --Bob

[Bob78164]

I don't have time to work through the analysis right now, but I think the right approach is to assume that you choose x, fixed, as your cutoff and then let your opponent choose y, variable, as hers. You want to choose x that maximizes your minimum (which will occur when your opponent also chooses x). I believe Nash's Theorem still applies in this setting, in which case that choice of x is the best you can do.

You then have 4 possibilities to consider -- you and your opponent each do or do not end up with a first number below the chosen cutoff. In each case, with a little care you can figure out the likelihood that you win. The values of x and y tell you how likely you are to fall into each of the four cases, and your likelihood of winning then falls out as a function of x and y.

You probably have to do the analysis twice, once assuming x < y, and once assuming x > y. --Bob

To take this a step farther, if you and your opponent are both above your cutoffs on the first draw and x < y, then you will certainly lose with probability y - x (because your number is below your opponent's cutoff) and you have 50-50 odds of winning the remainder of the time you're in this subcase, so your odds of winning this subcase are (1 + x - y)/2. You'll be in this subcase with probability (1 - x)(1 - y).

If you and your opponent both end up below your respective cutoffs (so that you both redraw), your odds of winning are 50-50. You'll be in this subcase with probability xy. The remaining two subcases I leave as an exercise for the reader. --Bob

[silverscreenselect]

The answer actually is .5 (I think), and I did the calculations.

For any value Y, your expected result is:

(.5)(Y) + ((1+Y)/2) x (1-Y)

Do all the calculations and you get (2 + Y - Y*2)/2. To get the maximum value, you take the derivative, which is -Y + .5 and set it to zero, which makes Y = .5

[silverscreenselect]

I don't have time to work through the analysis right now, but I think the right approach is to assume that you choose x, fixed, as your cutoff and then let your opponent choose y, variable, as hers. You want to choose x that maximizes your minimum (which will occur when your opponent also chooses x). I believe Nash's Theorem still applies in this setting, in which case that choice of x is the best you can do.

You then have 4 possibilities to consider -- you and your opponent each do or do not end up with a first number below the chosen cutoff. In each case, with a little care you can figure out the likelihood that you win. The values of x and y tell you how likely you are to fall into each of the four cases, and your likelihood of winning then falls out as a function of x and y.

You probably have to do the analysis twice, once assuming x < y, and once assuming x > y. --Bob

To take this a step farther, if you and your opponent are both above your cutoffs on the first draw and x < y, then you will certainly lose with probability y - x (because your number is below your opponent's cutoff) and you have 50-50 odds of winning the remainder of the time you're in this subcase, so your odds of winning this subcase are (1 + x - y)/2. You'll be in this subcase with probability (1 - x)(1 - y).

If you and your opponent both end up below your respective cutoffs (so that you both redraw), your odds of winning are 50-50. You'll be in this subcase with probability xy. The remaining two subcases I leave as an exercise for the reader. --Bob

I don't think what your opponent does is relevant, because you don't know what he does and your beginning number is independent of his (it's not like The Price Is RIght when you spin the wheel in sequence). So the answer is simply to maximize your own value, which happens at .5 and results in an expected value of .625

[Bob78164]

The answer actually is .5 (I think), and I did the calculations.

For any value Y, your expected result is:

(.5)(Y) + ((1+Y)/2) x (1-Y)

Do all the calculations and you get (2 + Y - Y*2)/2. To get the maximum value, you take the derivative, which is -Y + .5 and set it to zero, which makes Y = .5

It's (1 + y - y^2)/2, not what you wrote. But as I noted above, maximizing the expectation value does not necessarily solve the problem. You really need to walk through the process outlined in my posts above. --Bob

[silverscreenselect]

But as I noted above, maximizing the expectation value does not necessarily solve the problem. You really need to walk through the process outlined in my posts above. --Bob

Yes it does, because you don't know what your opponent has or what his strategy is. He doesn't start with the same number you do. His number might be higher or lower. He might stay or spin again. But you have no way of knowing. If you adopt a strategy with an expected value of .625, then the worst you can do is have a 50/50 chance of winning the game. If your opponent adopts any other strategy than that, he's going to have a lower expected value and you will have a greater than 50% chance of winning.

[Bob78164]

If my calculations are correct, for any fixed value of x, the best possible choice of y is 1/(1 + x^2). --Bob

[smilergrogan]

But as I noted above, maximizing the expectation value does not necessarily solve the problem. You really need to walk through the process outlined in my posts above. --Bob

Yes it does, because you don't know what your opponent has or what his strategy is. He doesn't start with the same number you do. His number might be higher or lower. He might stay or spin again. But you have no way of knowing. If you adopt a strategy with an expected value of .625, then the worst you can do is have a 50/50 chance of winning the game. If your opponent adopts any other strategy than that, he's going to have a lower expected value and you will have a greater than 50% chance of winning.

No, Bob is right and I was wrong. I tried breaking it down into percentiles using x = 0.5 and y = 0.618 as the two cutoffs, and I get 0.618 beating 0.5 by about 50.5 % to 49.5%. The 2nd choice introduces an asymmetry so that even though 0.5 beats 0.618 if the final numbers are low or medium, and the opposite if they are high, they will more often be high so 0.618 wins at a slightly higher frequency. I would be interested to see how the golden ratio applies; people need to show their work or I will have to deduct points from their grades!

[silverscreenselect]

If my calculations are correct, for any fixed value of x, the best possible choice of y is 1/(1 + x^2). --Bob

What is X and what is Y?

You're creating two variables when there's only one... your number. Now, if your number is X, then it generates an expected value according to a formula, but that's not a "choice."

[silverscreenselect]

I just realized that we're all overthinking this.

You have two expected values. The expected value if you keep the first number, which equals that number, and the expected value if you draw again, which equals .5.

So, if you started with a number less than .5, you will probably get a better number if you draw again. The closer you are to 0, the more likely you will improve by drawing again, and the more likely you'll improve yourself a lot than you'll hurt yourself a lot (if you draw on .01, you can't do much worse).

If you start with a number greater than .5, you will probably get a better number if you stand. The closer you are to 1, the less likely you will improve by drawing again, and the more likely you'll hurt yourself a lot than you'll improve yourself a lot (if you draw on .99, you can't do much better).

So, for every number less than .5, you have a better chance of improving your hand than of hurting your hand, so the best strategy is to draw. For every number greater than .5, you have a better chance of hurting your hand than of improving your hand, so your best strategy is to stay.

You don't know what your opponent has or what he will do, so you can't strategize on that basis. However you can always ask yourself, am I better off by staying or drawing?

[plasticene]

I submitted this answer:

Spoiler

(√5 - 1)/2 = 0.618, the Golden Ratio

.

I believe the answer is

Spoiler

√5 - 1

. If you use that as your threshold, there is no way for your opponent to gain an advantage by choosing a different threshold. If I use my answer and you use your answer, I'll win about 52.5% of the time.

I used a little bit of brute force to come up with that. I won't submit it unless I can figure out how to derive it from first principles.

Isn't your answer larger than 1? --Bob

That was supposed to be a 2, not a 5. I was copying and pasting the radical symbol from jarnon's answer and was in a rush, so I didn't check my post.

[plasticene]

The answer really is

Spoiler

√2 - 1

. If both players happen to use that as their threshold, they'll each have an equal chance of winning. If player 1 uses it and player 2 uses anything else, then player 1 will have the edge.

You could derive it using partial derivatives, or confirm it with ordinary derivatives, but the probability formula looks like a pain to differentiate. But if player 1 uses my answer as their threshold, here are player 1's probabilities of winning given a few possible choices of player 2's threshold:

.4100: 0.5000093950
.4141: 0.5000000068
.4142: 0.5000000001
.4143: 0.5000000040
.4200: 0.5000178107

Is that convincing?

[Bob78164]

But as I noted above, maximizing the expectation value does not necessarily solve the problem. You really need to walk through the process outlined in my posts above. --Bob

Yes it does, because you don't know what your opponent has or what his strategy is. He doesn't start with the same number you do. His number might be higher or lower. He might stay or spin again. But you have no way of knowing. If you adopt a strategy with an expected value of .625, then the worst you can do is have a 50/50 chance of winning the game. If your opponent adopts any other strategy than that, he's going to have a lower expected value and you will have a greater than 50% chance of winning.

Lower expected value does not mean lower chance of winning this game. Your intuition is based on a uniform distribution of final numbers, but in this problem the distribution of final numbers is not uniform. --Bob

[Bob78164]

I don't have time to work through the analysis right now, but I think the right approach is to assume that you choose x, fixed, as your cutoff and then let your opponent choose y, variable, as hers. You want to choose x that maximizes your minimum (which will occur when your opponent also chooses x). I believe Nash's Theorem still applies in this setting, in which case that choice of x is the best you can do.

You then have 4 possibilities to consider -- you and your opponent each do or do not end up with a first number below the chosen cutoff. In each case, with a little care you can figure out the likelihood that you win. The values of x and y tell you how likely you are to fall into each of the four cases, and your likelihood of winning then falls out as a function of x and y.

You probably have to do the analysis twice, once assuming x < y, and once assuming x > y. --Bob

To take this a step farther, if you and your opponent are both above your cutoffs on the first draw and x < y, then you will certainly lose with probability y - x (because your number is below your opponent's cutoff) and you have 50-50 odds of winning the remainder of the time you're in this subcase, so your odds of winning this subcase are (1 + x - y)/2. You'll be in this subcase with probability (1 - x)(1 - y).

If you and your opponent both end up below your respective cutoffs (so that you both redraw), your odds of winning are 50-50. You'll be in this subcase with probability xy. The remaining two subcases I leave as an exercise for the reader. --Bob

This is wrong. You will certainly lose with probability (y - x)/(1 - x) and you will win half of the remaining (1 -y)/(1 - x) times in this subcase. --Bob

[plasticene]

I'm starting to think I messed up my probability formula too. Maybe jarnon's answer was right after all! I've got more work to do.

[smilergrogan]

I'm starting to think I messed up my probability formula too. Maybe jarnon's answer was right after all! I've got more work to do.

Using my inelegant method I get x = 0.5 beating y = 0.414 by about 51.2% to 48.8%, and x = 0.5 beating y = 0.7 by about 50.9% to 49.1%. y = 0.6 beats x = 0.5 by about 50.5% to 49.5%, and y = 0.618 beats x = 0.5 by very slightly more: 50.55% to 49.45%. So that seems to back up jarnon; I wish I knew how he arrived at his answer.