4 ms·

This seems so simple. Decisions and draws are independent - we can ignore the other guy and just go for the highest value. Draw the first number. If it's below

This seems so simple. Decisions and draws are independent - we can ignore the other guy and just go for the highest value. Draw the first number. If it's below 0.5, draw again, since the odds then are that the next draw will be higher. Is there more?

thatcat 10y ago
Consider heads or tails: you get two flips, what are your chances of getting heads at least once? 50% for the first time then theres 50% chance you didn't, of that you now have a 50% chance to still get it .5*.5=.25. so for the two chances p(1)=.5, p(2)=.25, therefore overall p1+p2=.75 for redrawing at <50% or getting heads once with two tries.
- danielvf 10y ago
  You are agreeing with my solution? Though in this problem it seems the "average" final number would be 0.625, not 0.75 - since half the time you have an 0.75 expected outcome and the other half a 0.5 expected.
  - thatcat 10y ago
    No, having 2 chances obviously increases the probability. I don't see what you're averaging, but the formula for probability of an outcome of 2 unrelated events by the general addition rule is p(1 or 2) = (p1 + p2) - (p1*p2). in this case .5+.5-.25=.75; I was just trying to phrase it in an intuitive way.
  - laxatives 10y ago
    I think the point is that your strategy isn't independent of your opponent. Maybe a similar example is nontransitive dice: https://en.wikipedia.org/wiki/Nontransitive_dice https://en.wikipedia.org/wiki/Nontransitive_dice In other words, it isn't sufficient to shoot for the highest score possible.
    - murbard2 10y ago
      Absolutely. I was inspired by non transitive dice to create the problem.
CalChris 10y ago
That was my analysis as well. What the other guy does is unknown and therefore irrelevant. If you can improve your current expectation, you do. You can trivially search over that strategy space and see that, yep, 0.5 is the maximum. #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { for (double d = 0.25; d < .75; d += 0.01) { double e = 0; for (int j = 0; j < 100000; j++) { float r = ((float) random()) / ((float) RAND_MAX); if (r < d) r = ((float) random()) / ((float) RAND_MAX); e += r; } printf("d %lf e %lf\n", d, e / 100000); } }
- SonOfLilit 10y ago
  Careful, working in a language without a REPL encourages you to explore less. I was working in Python, and I did this and was about to post it, but then I asked myself "well, it can't be so easy, right? Why don't I also run a two-player simulation and make sure this strategy actually beats 0.6 first?", and - see my sibling post - it surprisingly loses. I can't yet explain why[1], but you can't argue with facts. [1] probably has to do with the probability distribution having a shape more interesting than a Gaussian bell
  - zodiac 10y ago
    > I can't yet explain why Your comment and simulation prompted me to attempt an explanation of where danielvf's analysis is incorrect, which I've posted here https://news.ycombinator.com/item?id=12941330 https://news.ycombinator.com/item?id=12941330
SonOfLilit 10y ago
I was 100% sure that redrawing below 0.5 is optimal, but a simple simulation disagrees: def tournament(a, b, n=1000): return sum(a() > b() for _ in xrange(n)) / n def redraw_below(c): x = random.random() if x < c: x = random.random() return x In [23]: tournament(lambda: redraw_below(0.5), lambda: redraw_below(0.6), n=10000000) Out[23]: 0.4948004 In [24]: tournament(lambda: redraw_below(0.5), lambda: redraw_below(0.6), n=10000000) Out[24]: 0.4948039 In [25]: tournament(lambda: redraw_below(0.5), lambda: redraw_below(0.6), n=10000000) Out[25]: 0.4948802 `redraw_below(0.5)` only beats `redraw_below(0.6)` 0.4948 of the times, very consistently, over three sets of a million rounds. This is despite `0.5` giving a better average (0.624 vs. 0.620). I'll think about why, but the result is very consistent and can't be ignored.
- tedunangst 10y ago
  When all else fails, test.
- Retric 10y ago
  I had a longer answer, but the distribution is important. A 0.5001 has a less than 50/50 shot of winning.
- ajkjk 10y ago
  It makes sense that the highest expected value doesn't necessarily indicate the best strategy. For example, suppose you're playing against someone who has taken the "reroll values greater than 0.5", giving them the expected value of 0.625. If you roll the value 0.55, you expected to lose more than half the time, because their expected value is 0.625. So you should reroll anyway.
  - soVeryTired 10y ago
    I think this is the key. Given that the game is winner-take-all, maximising your expected value isn't necessarily the right way to go. To take an extreme example, suppose I had a magic strategy that gave me a value of 1 every few throws and a lousy number most other times. That might give me a good expected value, but I'd still lose most rounds. So what's the right objective? Trying to beat your opponent's median score, so that you win more than half the time? Edit: I think you're on the right track, but I'm not sure I believe that you will lose more than half the time if you land below your opponent's expected value. I think that assumes their distribution of scores is non-skewed, which is not obvious to me.
andreschuelein 10y ago
- edit: To explain, why not 0.5? Because the probability of your opponent having drawn a smaller number than 0.5 after two attempts is <0.5 and the probability of a larger number is >0.5. A strategy of keeping >=0.5 after the first draw will loose against the optimal strategy on average.
- SonOfLilit 10y ago
  Definitely not 67% of cases, more like 50% + epsilon: def round(): x = random.random() if x <= 0.66666: x = random.random() y = random.random() if y <= 0.5: y = random.random() return x >= y sum(round() for _ in xrange(10000000)) 5001450 sum(round() for _ in xrange(10000000)) 5004434 sum(round() for _ in xrange(10000000)) 5000238 I also ran a test of 0.6666 vs. 0.625, and... sorry to say, but 0.625 wins hands down.
Retric 10y ago
Supose your facing someone using that strategy. They have a 0.5 chance of a .5+ on their first turn and a .25% chance of 0.5+ on their second turn and a 25% of under 0.5- on their second roll. Now, you get. 0.500001 on your first turn. There is a 25% chance they got less than 0.5 so you win 25% of the time. Well, if they are randomly under 50% then you have a better than 75% shot of beating them with a reroll. (50% your over 0.5 and thus win and 25% you are under 0.5 and still win.) But, they are above 0.50 then you gain a 25% chance of beating them (coin flip for over 50% and 50/50 odd or 50% of a loss) your under 50% and have even odds. Thus, you go from 25% win chance to .25 * .75 + 0.75 * 0.25 or 0.375% which is better odds for re rolling.
zodiac 10y ago
The problem with your analysis is that "go for the highest value" is not equivalent to "maximize expected value of the number you end up with" For example, consider a similar game where you draw and then optionally re-draw (like in the original game) but the amount of money you win if you end up with a number p is p if p < 0.8 and p + b if p > 0.8, where b is some constant. Then you're also trying to "go for the highest value". However it is clear that in the limit of large b, your best strategy is to redraw if p < 0.8.
chis 10y ago
Imagine being told exactly what number the other guy ended up with. Then, instead of maximizing value you would need to just redraw if you're below that number. I haven't solved it yet, but it's definitely some kinda recursive formula where you have to assume the other guy is also playing the optimal strategy.
- zodiac 10y ago
  > but it's definitely some kinda recursive formula where you have to assume the other guy is also playing the optimal strategy. I think it can be solved by searching for a pure strategy nash equilibrium
danielvf 10y ago
I am very humbled. The reason I'm wrong is that you are opposing another person's numbers - the expected dollars for a given number isn't linear. A .30 is worth way less than half as likely win you money than a .60 is. Because of this, the shape of your distribution matters more than its "average" value. I can't believe I forgot that AVG(F(X)) ain't necessarily F(AVG(X))

thatcat 10y ago

Consider heads or tails: you get two flips, what are your chances of getting heads at least once? 50% for the first time then theres 50% chance you didn't, of that you now have a 50% chance to still get it .5*.5=.25. so for the two chances p(1)=.5, p(2)=.25, therefore overall p1+p2=.75 for redrawing at <50% or getting heads once with two tries.

danielvf 10y ago
You are agreeing with my solution? Though in this problem it seems the "average" final number would be 0.625, not 0.75 - since half the time you have an 0.75 expected outcome and the other half a 0.5 expected.
- thatcat 10y ago
  No, having 2 chances obviously increases the probability. I don't see what you're averaging, but the formula for probability of an outcome of 2 unrelated events by the general addition rule is p(1 or 2) = (p1 + p2) - (p1*p2). in this case .5+.5-.25=.75; I was just trying to phrase it in an intuitive way.
- laxatives 10y ago
  I think the point is that your strategy isn't independent of your opponent. Maybe a similar example is nontransitive dice: https://en.wikipedia.org/wiki/Nontransitive_dice https://en.wikipedia.org/wiki/Nontransitive_dice In other words, it isn't sufficient to shoot for the highest score possible.
  - murbard2 10y ago
    Absolutely. I was inspired by non transitive dice to create the problem.

CalChris 10y ago

That was my analysis as well. What the other guy does is unknown and therefore irrelevant. If you can improve your current expectation, you do. You can trivially search over that strategy space and see that, yep, 0.5 is the maximum. #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { for (double d = 0.25; d < .75; d += 0.01) { double e = 0; for (int j = 0; j < 100000; j++) { float r = ((float) random()) / ((float) RAND_MAX); if (r < d) r = ((float) random()) / ((float) RAND_MAX); e += r; } printf("d %lf e %lf\n", d, e / 100000); } }

SonOfLilit 10y ago
Careful, working in a language without a REPL encourages you to explore less. I was working in Python, and I did this and was about to post it, but then I asked myself "well, it can't be so easy, right? Why don't I also run a two-player simulation and make sure this strategy actually beats 0.6 first?", and - see my sibling post - it surprisingly loses. I can't yet explain why[1], but you can't argue with facts. [1] probably has to do with the probability distribution having a shape more interesting than a Gaussian bell
- zodiac 10y ago
  > I can't yet explain why Your comment and simulation prompted me to attempt an explanation of where danielvf's analysis is incorrect, which I've posted here https://news.ycombinator.com/item?id=12941330 https://news.ycombinator.com/item?id=12941330

SonOfLilit 10y ago

I was 100% sure that redrawing below 0.5 is optimal, but a simple simulation disagrees: def tournament(a, b, n=1000): return sum(a() > b() for _ in xrange(n)) / n def redraw_below(c): x = random.random() if x < c: x = random.random() return x In [23]: tournament(lambda: redraw_below(0.5), lambda: redraw_below(0.6), n=10000000) Out[23]: 0.4948004 In [24]: tournament(lambda: redraw_below(0.5), lambda: redraw_below(0.6), n=10000000) Out[24]: 0.4948039 In [25]: tournament(lambda: redraw_below(0.5), lambda: redraw_below(0.6), n=10000000) Out[25]: 0.4948802 `redraw_below(0.5)` only beats `redraw_below(0.6)` 0.4948 of the times, very consistently, over three sets of a million rounds. This is despite `0.5` giving a better average (0.624 vs. 0.620). I'll think about why, but the result is very consistent and can't be ignored.

tedunangst 10y ago
When all else fails, test.
Retric 10y ago
I had a longer answer, but the distribution is important. A 0.5001 has a less than 50/50 shot of winning.
ajkjk 10y ago
It makes sense that the highest expected value doesn't necessarily indicate the best strategy. For example, suppose you're playing against someone who has taken the "reroll values greater than 0.5", giving them the expected value of 0.625. If you roll the value 0.55, you expected to lose more than half the time, because their expected value is 0.625. So you should reroll anyway.
- soVeryTired 10y ago
  I think this is the key. Given that the game is winner-take-all, maximising your expected value isn't necessarily the right way to go. To take an extreme example, suppose I had a magic strategy that gave me a value of 1 every few throws and a lousy number most other times. That might give me a good expected value, but I'd still lose most rounds. So what's the right objective? Trying to beat your opponent's median score, so that you win more than half the time? Edit: I think you're on the right track, but I'm not sure I believe that you will lose more than half the time if you land below your opponent's expected value. I think that assumes their distribution of scores is non-skewed, which is not obvious to me.

andreschuelein 10y ago

- edit: To explain, why not 0.5? Because the probability of your opponent having drawn a smaller number than 0.5 after two attempts is <0.5 and the probability of a larger number is >0.5. A strategy of keeping >=0.5 after the first draw will loose against the optimal strategy on average.

SonOfLilit 10y ago
Definitely not 67% of cases, more like 50% + epsilon: def round(): x = random.random() if x <= 0.66666: x = random.random() y = random.random() if y <= 0.5: y = random.random() return x >= y sum(round() for _ in xrange(10000000)) 5001450 sum(round() for _ in xrange(10000000)) 5004434 sum(round() for _ in xrange(10000000)) 5000238 I also ran a test of 0.6666 vs. 0.625, and... sorry to say, but 0.625 wins hands down.

Retric 10y ago

Supose your facing someone using that strategy. They have a 0.5 chance of a .5+ on their first turn and a .25% chance of 0.5+ on their second turn and a 25% of under 0.5- on their second roll. Now, you get. 0.500001 on your first turn. There is a 25% chance they got less than 0.5 so you win 25% of the time. Well, if they are randomly under 50% then you have a better than 75% shot of beating them with a reroll. (50% your over 0.5 and thus win and 25% you are under 0.5 and still win.) But, they are above 0.50 then you gain a 25% chance of beating them (coin flip for over 50% and 50/50 odd or 50% of a loss) your under 50% and have even odds. Thus, you go from 25% win chance to .25 * .75 + 0.75 * 0.25 or 0.375% which is better odds for re rolling.

zodiac 10y ago

The problem with your analysis is that "go for the highest value" is not equivalent to "maximize expected value of the number you end up with" For example, consider a similar game where you draw and then optionally re-draw (like in the original game) but the amount of money you win if you end up with a number p is p if p < 0.8 and p + b if p > 0.8, where b is some constant. Then you're also trying to "go for the highest value". However it is clear that in the limit of large b, your best strategy is to redraw if p < 0.8.

chis 10y ago

Imagine being told exactly what number the other guy ended up with. Then, instead of maximizing value you would need to just redraw if you're below that number. I haven't solved it yet, but it's definitely some kinda recursive formula where you have to assume the other guy is also playing the optimal strategy.

zodiac 10y ago
> but it's definitely some kinda recursive formula where you have to assume the other guy is also playing the optimal strategy. I think it can be solved by searching for a pure strategy nash equilibrium

danielvf 10y ago

I am very humbled. The reason I'm wrong is that you are opposing another person's numbers - the expected dollars for a given number isn't linear. A .30 is worth way less than half as likely win you money than a .60 is. Because of this, the shape of your distribution matters more than its "average" value. I can't believe I forgot that AVG(F(X)) ain't necessarily F(AVG(X))