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?
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
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.
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.
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.
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))
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
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.
#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);
}
}[1] probably has to do with the probability distribution having a shape more interesting than a Gaussian bell
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
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.
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.
In other words, it isn't sufficient to shoot for the highest score possible.
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.
I think it can be solved by searching for a pure strategy nash equilibrium