4 ms·
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
by 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 agoWhen all else fails, test.
- Retric 10y agoI had a longer answer, but the distribution is important. A 0.5001 has a less than 50/50 shot of winning.
- ajkjk 10y agoIt 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 agoI 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.