6 ms·

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 d

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.

philipodonnell 10y ago
This sounds like a variant of the two envelope problem: https://en.m.wikipedia.org/wiki/Two_envelopes_problem https://en.m.wikipedia.org/wiki/Two_envelopes_problem So is this one of those questions that's not possible to answer you're just trying to see how they handle the stress of the unsolvable?
- murbard2 10y ago
  It isn't. There's a clear, well defined answer.
  - twic 10y ago
    I'm just a programmer, but this seems really easy to me. What am I missing?
    - SonOfLilit 10y ago
      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 :-)
- simias 10y ago
  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? That'd be my guess at least.
thatcat 10y ago
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)
- mirceal 10y ago
  Why p=.5 for > .7 w/ 2 draws?
  - thatcat 10y ago
    I'm no quant but pretty sure to calculate the probability of two random events you use a union function, basically means probability of an event occurring in a or b. https://people.richland.edu/james/lecture/m170/ch05-rul.html https://people.richland.edu/james/lecture/m170/ch05-rul.html
mirceal 10y ago
Draw. If > 0.5 keep it. If not draw again.
- CalChris 10y ago
  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.
  - foldr 10y ago
    Yeah, this came up the last time murbard2 posted this: https://news.ycombinator.com/item?id=8699033 https://news.ycombinator.com/item?id=8699033 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.
    - murbard2 10y ago
      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.
      - foldr 10y ago
        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: https://www.economics.utoronto.ca/workingPapers/UT-ECIPA-ECPAP-95-04.ps https://www.economics.utoronto.ca/workingPapers/UT-ECIPA-ECP... 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.
danielvf 10y ago
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
deleted 10y ago
[deleted]
krabpaaltje 10y ago
Alternative option: spend time on other things because quants are about the big bucks
- SonOfLilit 10y ago
  Quants are actually all about winning 0.0001 cent on average on every iteration of a game played 1 billion times a day.
  - krabpaaltje 10y ago
    I know, but it was not defined in the spec
dreeves 10y ago
Oh my god it's the golden ratio! That's so cool! EDIT: I'll show my work, rot13'd... 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: q[g_] := CebonovyvglQvfgevohgvba[Vs[k<g, g, g+1], {k,0,1}] Fvzcyvsl[ Cebonovyvgl[k<l, {Qvfgevohgrq[k, q[g]], Qvfgevohgrq[l, q[h]]}], 0<g<1 && 0<gh<1] Gung tvirf hf gur cebonovyvgl gung g orngf h yvxr fb: c[h_,g_] := Cvrprjvfr[{ {(1+g-(1+g+g^2)*h+(1+g)*h^2)/2, h>g}, {(1+g-g^2+(g-g^2-1)*h+g*h^2)/2, h<g}, {((g^2-1)^2-g*(g^2-2)*h)/2, h==g}}] Abj jr jnag gur g gung znkvzvmrf gung sbe n tvira h, juvpu jr trg ol gnxvat gur qrevingvir jvgu erfcrpg gb g, frggvat vg gb mreb, naq fbyivat sbe g: Fvzcyvsl[Fbyir[Q[c[g, h], g] == 0, g], 0<h<1] Fb abj jr unir gur orfg erfcbafr gb na neovgenel fgengrtl g: oe[g_] := Cvrprjvfr[{ {(1+g+g^2)/(2+2*g), g<(Fdeg[5]-1)/2}, {(1-g+g^2)/(2*g), g>(Fdeg[5]-1)/2}}] Vs lbh cybg gung lbh frr gung gur orfg erfcbafr vf nyjnlf orgjrra .5 naq .618. Vs lbhe bccbarag nyjnlf xrrcf gurve svefg qenj gura lbh fubhyq hfr n guerfubyq bs .5. (Fnzr vs gurl nyjnlf gnxr gur frpbaq qenj bs pbhefr.) Ohg gurl jba'g qb gung. Vs gurl hfr n guerfubyq bs 1/2 gurzfrys gura oe[1/2] == 7/12. Ohg gurl jba'g qb gung rvgure. Jung jr jnag bs pbhefr vf gur svkrq cbvag, vr, gur Anfu rdhvyvoevhz, jurer oe[g]==g. Gung, boivbhf va gur cybg, vf g = (Fdeg[5]-1)/2 nxn gur tbyqra engvb!
- SonOfLilit 10y ago
  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?
quantgod 10y ago
Re-draw if the number is smaller than 2/3.
laxatives 10y ago
Just curious, can you share your role/organization and the people you typically pass and the people you typically fail in your interviews?
Xcelerate 10y ago
The problem seems ill-defined to me in the same sense that Bertrand's paradox is (https://en.wikipedia.org/wiki/Bertrand_paradox_(probability) https://en.wikipedia.org/wiki/Bertrand_paradox_(probability)). 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?
- murbard2 10y ago
  Assume you're playing against me :)
- deleted 10y ago
  [deleted]

philipodonnell 10y ago

This sounds like a variant of the two envelope problem: https://en.m.wikipedia.org/wiki/Two_envelopes_problem https://en.m.wikipedia.org/wiki/Two_envelopes_problem So is this one of those questions that's not possible to answer you're just trying to see how they handle the stress of the unsolvable?

murbard2 10y ago
It isn't. There's a clear, well defined answer.
- twic 10y ago
  I'm just a programmer, but this seems really easy to me. What am I missing?
  - SonOfLilit 10y ago
    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 :-)
simias 10y ago
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? That'd be my guess at least.

thatcat 10y ago

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)

mirceal 10y ago
Why p=.5 for > .7 w/ 2 draws?
- thatcat 10y ago
  I'm no quant but pretty sure to calculate the probability of two random events you use a union function, basically means probability of an event occurring in a or b. https://people.richland.edu/james/lecture/m170/ch05-rul.html https://people.richland.edu/james/lecture/m170/ch05-rul.html

mirceal 10y ago

Draw. If > 0.5 keep it. If not draw again.

CalChris 10y ago
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.
- foldr 10y ago
  Yeah, this came up the last time murbard2 posted this: https://news.ycombinator.com/item?id=8699033 https://news.ycombinator.com/item?id=8699033 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.
  - murbard2 10y ago
    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.
    - foldr 10y ago
      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: https://www.economics.utoronto.ca/workingPapers/UT-ECIPA-ECPAP-95-04.ps https://www.economics.utoronto.ca/workingPapers/UT-ECIPA-ECP... 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.

danielvf 10y ago

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

deleted 10y ago

[deleted]

krabpaaltje 10y ago

Alternative option: spend time on other things because quants are about the big bucks

SonOfLilit 10y ago
Quants are actually all about winning 0.0001 cent on average on every iteration of a game played 1 billion times a day.
- krabpaaltje 10y ago
  I know, but it was not defined in the spec

dreeves 10y ago

Oh my god it's the golden ratio! That's so cool! EDIT: I'll show my work, rot13'd... 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: q[g_] := CebonovyvglQvfgevohgvba[Vs[k<g, g, g+1], {k,0,1}] Fvzcyvsl[ Cebonovyvgl[k<l, {Qvfgevohgrq[k, q[g]], Qvfgevohgrq[l, q[h]]}], 0<g<1 && 0<gh<1] Gung tvirf hf gur cebonovyvgl gung g orngf h yvxr fb: c[h_,g_] := Cvrprjvfr[{ {(1+g-(1+g+g^2)*h+(1+g)*h^2)/2, h>g}, {(1+g-g^2+(g-g^2-1)*h+g*h^2)/2, h<g}, {((g^2-1)^2-g*(g^2-2)*h)/2, h==g}}] Abj jr jnag gur g gung znkvzvmrf gung sbe n tvira h, juvpu jr trg ol gnxvat gur qrevingvir jvgu erfcrpg gb g, frggvat vg gb mreb, naq fbyivat sbe g: Fvzcyvsl[Fbyir[Q[c[g, h], g] == 0, g], 0<h<1] Fb abj jr unir gur orfg erfcbafr gb na neovgenel fgengrtl g: oe[g_] := Cvrprjvfr[{ {(1+g+g^2)/(2+2*g), g<(Fdeg[5]-1)/2}, {(1-g+g^2)/(2*g), g>(Fdeg[5]-1)/2}}] Vs lbh cybg gung lbh frr gung gur orfg erfcbafr vf nyjnlf orgjrra .5 naq .618. Vs lbhe bccbarag nyjnlf xrrcf gurve svefg qenj gura lbh fubhyq hfr n guerfubyq bs .5. (Fnzr vs gurl nyjnlf gnxr gur frpbaq qenj bs pbhefr.) Ohg gurl jba'g qb gung. Vs gurl hfr n guerfubyq bs 1/2 gurzfrys gura oe[1/2] == 7/12. Ohg gurl jba'g qb gung rvgure. Jung jr jnag bs pbhefr vf gur svkrq cbvag, vr, gur Anfu rdhvyvoevhz, jurer oe[g]==g. Gung, boivbhf va gur cybg, vf g = (Fdeg[5]-1)/2 nxn gur tbyqra engvb!

SonOfLilit 10y ago
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?

quantgod 10y ago

Re-draw if the number is smaller than 2/3.

laxatives 10y ago

Just curious, can you share your role/organization and the people you typically pass and the people you typically fail in your interviews?

Xcelerate 10y ago

The problem seems ill-defined to me in the same sense that Bertrand's paradox is (https://en.wikipedia.org/wiki/Bertrand_paradox_(probability) https://en.wikipedia.org/wiki/Bertrand_paradox_(probability)). 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?

murbard2 10y ago
Assume you're playing against me :)
deleted 10y ago
[deleted]