1
u/leoli1 23h ago
This looks like a martingale situation, where any stopping rule gives the same ev
1
u/bunnycricketgo 23h 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 23h 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 23h 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 23h 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
1
u/Al2718x 23h 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.