Here's my favorite interview question (spent 10 years as a quant, interviewed a bunch of people, most do not do well on this)
We're going to play a game. You draw a random number uniformly between 0 and 1. If you like it, you can keep it. If you don't, you can have a do-over and re-draw, but then you have to keep that final result.
I do the same. You do not know whether I've re-drawn and I do not know whether you've re-drawn. Decisions are made independently. We compare our numbers and the highest one wins $1.
What strategy do you use?
EDIT: The answer is not 0.5, it is not 0.7 either.
Jr pna cnenzrgrevmr n fgengrtl ol n guerfubyq g: gur inyhr gung gur svefg qenj arrqf gb or yrff guna va beqre gb pubbfr gb qenj ntnva. Hfvat guerfubyq g, gur cebonovyvgl bs trggvat yrff guna g vf g^2 orpnhfr lbh unir gb qenj orybj gur guerfubyq gjvpr va n ebj. Gung chgf gur cebonovyvgl bs raqvat hc nobir gur guerfubyq ng 1-g^2.
Gur cebonovyvgl vf havsbez nobir naq orybj gur guerfubyq fb gur cebonovyvgl qvfgevohgvba bs lbhe ahzore vf:
cqs(k) = { g vs k<g ryfr g+1 }
(Gur g+1 vf sebz fbyivat gb znxr gur vagrteny sebz 0 gb 1 or 1.)
Fnl lbhe bccbarag hfrf fgengrtl h naq lbh hfr fgengrtl g. Gura jr jnag gb znkvzvmr gur cebonovyvgl gung K~cqs(g) vf terngre guna L~cqs(h). Zngurzngvpn jvyy gryy hf gung vs jr nfx yvxr fb:
There is another way to do it, without integrals and convolutions. Say player A has threshold a and player B has threshold b, a <= b. Write 3x3 table of Player A win probabilities for ranges 0 to a, a to b, and b to 1. It will have 1/2 on the diagonal, 1 below, 0 above.
After some simplification, total Player A win probabilty is (-ba^2 + (b^2-b+1)a +(b^2-b+1))/2. Find a that maximizes this probability for any given b by taking the derivative and setting it to 0, which would be a = (b^2-b+1)/2b.
The game is symmetric, so at Nash equilibrium a==b. Now solve a = (a^2-a+1)/2a to get the golden ratio.
The lift over naive 0.5 threshold is very small, though, less than 1%.
This... rings so right... but me and probably many other programmers here lack the math to see the explanation immediately in front of our eyes when we hear the answer. Can you please elaborate?
Edit: thanks. This is convincing, but... given that we're looking for a fixed point of a process like... [bah, I lack words to describe a vague, non-rigorous intuition]... I expect that there is a convincing one-sentence explanation that also shows it to be the golden ratio. Am I wrong? Can anyone give a simpler explanation?
Your intuition is better than mine! I crunched it out (just now edited my answer to show how) but still have no intuitive sense of why it should be the golden ratio. Would love to hear some intuition for that!
Saying "It's intuitive to me that this answer someone worked out and told me is correct" is cheating.
But generally...
The process is something like:
If you choose 0.5, then 0.625 beats you because that is the expected average of someone redrawing below 0.5.
If you choose 0.625, then 0.617[2] beats you because that is the expected average of someone redrawing below 0.625.
If you choose 0.618, then 0.6182 beats you...
Lets ignore those numbers for a moment and focus on the process: "Given a number to redraw below, redraw below the expected value of redrawing below that number".
Trying to find a fixed point for this kind of process, the golden ratio has some kind of... mythological fit? Like, I've heard so many stories like this that ended up with a formula involving the golden ratio...
I wouldn't necessarily expect the answer to be phi, but I would so not be surprised to find it to be some formula involving phi, a rational factor, and maybe pi (just because I have absolutely no intuition for which series happen to sum to rational factors of pi).
[2] I'm getting these numbers by simulation, it's too late for me here in Israel to do math
s(k) is the function for "The number I should choose if my opponent chooses k" [1]. We arrived at the formula by asking "what is the best number for us to choose assuming our opponent chooses k?".
Now, obviously a smart opponent would not choose a number k where k != s(k), because s(k) would be a better choice. So the only numbers it makes sense for him to choose would be fixed points of s(k), points where k = s(k). And the smartest thing for me to do in that case would be to choose s(k), which just so happens to be equal to k.
[1] which may be more or less than s(k), e.g. if my opponent chooses to always redraw, i.e. k=1, it should be the same as if he chooses to never redraw, k=0, and we expect for both cases s(k)=0.5 < 1 (and it indeed is)
Why do you bring up expected value in the calculation. You may end up with the right result, but there's no good justification for why expected value should come into play.
Your optimal strategy involves maximizing an objective function that depends upon your opponent's strategy. "Assume nothing" about your opponent is an incomplete problem specification, because you must assume something in order to determine which function to maximize.
For example, consider that your opponent chooses to redraw any time his number is greater than 0.5. His expected value then becomes less than 0.5, which means that if you choose to redraw any time your own number is below 0.618..., then your strategy is suboptimal.
So, we have to assume something about the opponent's strategy. Is it a uniform strategy state space? Is it a state space where both players are superrational?
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.
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.
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.
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))
-
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.
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.
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.
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);
}
}
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
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.
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.
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.
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.
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.
But here you know the content of the "envelope" before you decide whether to switch or not.
If the adversary was only allowed one pick I guess I'd only re-draw if I had less than 0.5 since statistically you'd be more likely to have a greater number than a weaker one. I'm not sure what the maths are but a simple implementation gave me an average value of about 0.625 using this strategy, so definitely an improvement over a single pick.
But I have the feeling that since the adversary can chose the same strategy maybe you should be a little more aggressive and redraw if you are at 0.5? But then the adversary would do the same so I guess the solution would eventually converge to a value a little above 0.6?
See my post. As a mathematician, maybe you're missing some interesting theory of why if the opponent has an average of 0.625 and you got 0.55 you should redraw. However, as a programmer, the first thing you're missing is running a quick Monte Carlo simulation and seeing whether your idea actually wins :-)
If first draw is >= .7 don't redraw since chance of being larger than .7 is 50% for two draws. 50% probability is chosen since if you pick any number lower than .7, the probability increases favoring your opponent drawing a higher number.
calc: p(a union b) = p(a) + p(b) - (p(a)*p(b));
p(>=.7)=3/10;
.51 = (3/10) + (3/10) - (.3)(.3)
Agreed. I think the other 'more complex' answers assume there's communication or that you know your opponent's strategy. That's not in the problem statement.
The idea is to find a Nash equilibrium, but the question is stated in the wrong way, since it gives no indication that you're in a position to make any assumptions about your opponent's strategy.
It's an interview question, you're free to ask for clarifications.
That said, finding the Nash equilibrium is precisely the natural thing to do if you can't make assumptions about your opponent's strategy. It's a worst case scenario analysis. You can't statistically lose out to your opponent if you pick it. This does not mean that you know your opponent strategy.
Consider the context. This is algorithmic trading. If your strategy can be gamed, it will be gamed by someone else. Picking anything but the Nash equilibrium means you can be gamed.
A good candidate will immediately gravitates towards this solution, there is no ambiguity that this is the expected answer.
In the absence of any information about your opponent, you should assume that they're equally likely to be using any strategy.
>You can't statistically lose out to your opponent if you pick it.
Right, but you can miss out on an opportunity to fully exploit the fact that your opponent is using a really bad strategy. So if you want to maximize your probability of winning against an opponent with a randomly chosen strategy, it's not the right answer. Nothing in the statement of the question indicates that you are entitled to make any assumptions about your opponent's strategy. And it's not as if determining the best strategy in a context where you lack perfect knowledge of your opponent's strategy is an unknown concept in game theory:
I feel like the way you state the question at present may end up selecting for candidates who think exactly like you do. Why not just add the statement that the players have mutual knowledge of their rationality? That removes the ambiguity, and doesn't make the question fundamentally any easier.
1) There's no reason why you should assume every strategy is equally likely. It's absolutely not the case. When you play poker, do you assume your opponent play their cards randomly just because you don't know their strategy? It's not a realistic prior at all.
2) Playing the Nash equilibrium means that you may not be fully exploiting the opponent, true. It's also possible that you're opponent's strategy is to give you a million dollars if you say "abracadabra". So how about that? Check-mate interviewer.
3) If you want to make the problem harder on yourself, you can be my guest and try and assume a realistic distribution of strategies for your opponent. That distribution will have a peak around the nash equilibrium, so you'll have to end up calculating it.
Your way of looking at it is perfectly sensible. But a sensible person might also say that a uniform prior over strategies is appropriate in the absence of any information about your opponent. Choice of priors is always going to be partly subjective, and reasonable people can make different choices.
I would point out that in a real world scenario, a uniform prior is barely any less realistic than the a prior derived from the assumption of mutual knowledge of perfect rationality. Is your poker opponent equally likely to be doing their utmost to lose as to win? No. But on the other hand, they're not likely to be tracking 100% of available information and making the mathematically correct choice all the time.
In general, the question of what you should assume about an unknown opponent's strategy is a tricky philosophical question, and reasonable people can gravitate to different points of view on this issue. I think that might be why so few people give the answer you want. I was just suggesting that explicitly mentioning mutual knowledge of perfect rationality might help.
Do you think it's equally likely that a random opponent will redraw below 0.01 as it is that they will redraw below 0.5 or below phi?
Most people do not give the right answer not because of philosophical issues around the Nash equilibrium but because they have a hard time understanding that looking to maximize the expected value is not optimal.
>Do you think it's equally likely that a random opponent will redraw below 0.01 as it is that they will redraw below 0.5 or below phi?
If random really means random, then that's presumably true by definition. If we're talking about an opponent randomly selected from a representative group of people, then no, but equally, I wouldn't assume that they're going to pick the golden ratio as their threshold either.
The thing is that maximizing the expected value is optimal in the absence of any information about the opponent's strategy. But sure, I can easily believe that many people would get the question wrong anyway.
> If random really means random, then that's presumably true by definition.
No it's not. Randomness is always with respect to a given distribution. There is nothing special about the uniform distribution over a threshold. The space of strategies also include strategies where your opponent redraw only when they hit a number between 0.1 and 0.2, or where they redraw if the second decimal digit of the first draw is even.
> The thing is that maximizing the expected value is optimal in the absence of any information about the opponent's strategy.
Your statement is meaningless without a prior on the strategy. Under which prior is maximizing the expected value optimal? If you assume the other party randomly picks a threshold between 0 and 1, then the optimal answer is (sqrt(39)-3)/6 not 0.5. Not that this prior makes any sense. It's far more sensible to assume a strategic opponent.
Rethrowing below 0.5 is typically the optimal strategy when the opponent has no strategy at all, i.e. always or never rethrows.
If a strategy is any function from the preceding game state to keep/redraw, then I don't have the mathematical chops to specify a uniform prior over all such strategies and compute the optimal strategy that way. (In fact it may not necessarily be possible to do this in a sensible way, as Bertrand's paradox suggests, as another poster pointed out.)
However, there is a much simpler argument suggesting that maximizing EV would be the right approach in the absence of any knowledge about the opponent's strategy. Say the opponent chooses to redraw at random. Then in effect they are drawing once. If we redraw when the value is < a, then we just want to maximize the probability of winning, (1-a)(a + 0.5) + 0.5a, giving a = 0.5.
Modeling a process that we know nothing about as a random process seems reasonable. And the reasoning above does not actually involve computing EVs, though it happens that the right answer is the answer that maximizes the EV.
To justify this a bit further, we can reason as follows. If we know nothing about the opponent's strategy, then their initial draw tells us nothing about whether or not they will choose to redraw. So our estimate of their probability of redrawing, p, must be independent of their initial draw. Then the probability of winning is 0.5ap + (1-a)(1-p)(a + 0.5) + (1-a)p(a + 0.5) + 0.5a(1-p), which is invariant with respect to p, and which is at its maximum when a = 0.5.
>It's far more sensible to assume a strategic opponent.
Well, this is going round in circles, but I would say that this is sensible only if you know something about the opponent! I don't see how it's sensible to assume anything about your opponent if you know nothing about them. And if we're talking about the "real world", then of course you do know something, but you certainly don't know that they're perfectly rational.
We're going to play a game. You draw a random number uniformly between 0 and 1. If you like it, you can keep it. If you don't, you can have a do-over and re-draw, but then you have to keep that final result.
I do the same. You do not know whether I've re-drawn and I do not know whether you've re-drawn. Decisions are made independently. We compare our numbers and the highest one wins $1.
What strategy do you use?
EDIT: The answer is not 0.5, it is not 0.7 either.