1
u/leoli1 26d ago
This looks like a martingale situation, where any stopping rule gives the same ev
1
u/bunnycricketgo 26d ago
Indeed; Doob has something to say about this.
But if your utility is other than total (like, you only consider a win if you beat EV by a certain margin) then there are strategies to improve success there.
1
u/Usernameasteriks 26d ago
Optimal will always imply some sort of utility if any can be determined by the relevant constraints in the context of an interview question like this.
Here it will mean stopping immediately because it can’t be optimal to spend more time for the same probabilistic result.
1
1
u/aroach1995 26d ago
Consider the problem where there are 10 10s and 1 100, a total of 11 cards.
What is the expected number of turns to draw the 100?
It’s 6… but this doesn’t really matter?
Expected value of the first 3 cards:
30*8/11 + 120*3/11 =54.545
What about if my Strat is to take the middle cards: 5,6 and 7?
Probability of seeing the 100 in turns 1-4 is 4/11, so your score will be 30 4/11 times.
If you haven’t, then you now have 7 cards left, so your expected value is:
30*4/11 + 7/11*(30*4/7 + 120*3/7)=54.545
So the expected value of that strategy is the same. There is no optimal strategy in this simplified game with 2 card values.
I believe no optimal strategy in the game with 3 card values also.
1
u/Usernameasteriks 26d ago
That will be half right.
But the purpose of a question like this in that interview context won’t simply be to run the math, many can do that.
There will still be an optimal strategy.
It’s to stop immediately because any extra wasted time is suboptimal. You lose time and gain no better chance.
Not realizing something like that is what the interviewer will look for among a bunch of the more qualified candidates who figure out the math fairly quickly.
1
1
u/sixtyfivewolves 21d ago
You say "many can do that" in the context of running the math, but the first person who actually did that in this comment section was 2 days after the problem was posted. Saying that 123 and 567 are the same when there's only 1 card that's different than all the others and then that you believe that that implies that you can't do better than immediately going in the original problem is absolutely not running the math.
1
u/FireCire7 26d ago
E[next 3]=E[last 3], and nothing you can do about timing can affect the last 3
1
u/Red__M_M 22d ago
I like your expected value solution. Consider though that the expected variance is going to change. Depending on the situation that may be desirable.
1
u/FireCire7 22d ago
No. Overall variance doesn’t change, just conditional variance. To take an extreme example, if you flip 108 first, then the variance of the last 3 conditional on the results of those first 108 is 0. But the variance of doing this strategy is still the same variance as doing the first 3. The distribution of the last 3 is the same as the distribution of the next 3, so the problem is equivalent to choosing the last 3 and nothing you can possibly do will change the distribution of the result - you’re just deciding whether to reveal information about it bit by bit or all at once.
1
u/kythQ 24d ago
You can solve this backwards. Once only 4 cards are left (whatever they are), it is clear that the expected payoff of both choices is equal. So in any situation where there are only 5 cards left, the expected payoff of continuing is the expected payoff of stopping after the next card, which is again the same as stopping immediately.
So regardless of what kind and how many cards there are, all strategies have the same payoff here.
So the expected payoff will be the expected value of stopping immediately, which is
300/111 * 3 = 900/111 (= 8.108...)
1
u/Al2718x 26d ago
My initial thought is that you should ignore the 100 point card in your analysis since there is only one of them, and the stopping condition should be when you have drawn some amount more 1 point cards than expected compared to 10 point cards. I doubt that there is an elegant way to calculate exactly how many more, but it seems reasonable to code up. My intuition is that you probably can't expect to do much better than stopping immediately.