SIG (Susquehanna International Group) Interview Question
Financial Application EngineersCountry: United States
Actually my answer was for the starting case and for 2nd case too. You will have to offer only on average price or if it is in fraction Least integer of that amount. If you are offer users to play without replacement then average will change in every new trail. Otherwise it will be remain same.
First case :
Card are drawn randomly from hat, so probability of each card is 1/10
So expected value is :
1*1/10 + 2*1/10 + 3*1/10 + ... + 9*1/10 + 10*1/10 = (1+2+....+9+10)/10 = 5.5
Second Case : If the person has to choose second card, then the answer is same, but if not then, we need to know the probability distributon that if 1 comes then what is the probability that he gonna make 2nd choice. once we know that we can able to find the ourcome.
A rational user draws a second card in exactly 50% of cases, i.e. only if the first card is 1/2/3/4/5. If the cases where he holds the first card, his expected return is 8, i.e the average of 6/7/8/9/10. In the cases where he draws a second card, his expected return is 5.5. His overall expected return is the mean of 8 and 5.5, which is 6.75. If the user were allowed to return up to two cards to the hat (i.e. up to three turns), then on the first turn, he only holds the 7/8/9/10, knowing the result of the two-turn game. His expected outcome then becomes 0.4*8.5 + 0.6*6.5, or 7.3. In the four-turn game, he only settles with 8/9/10 on the first hand, and his expected return is 0.3*9 + 0.7*7.3, or 7.81. You can obviously write a program to determine the strategy for an arbitrary number of turns. For a high enough n, the user's strategy is eventually to return anything other than a 10, but for low values of n, he needs to be careful about throwing away 6s, 7s, 8s, etc., for fear of getting worse cards on the redraws.
My numbers were off a bit in the prior comment, but here's the program:
def strategy(n):
# A user draws a card from 1 to 10, and if
# he doesn't like it, he can return the card
# for up to n turns. He acts rationally.
# Return a tuple of the cards he keeps and
# his mean expected outcome.
if n == 0:
return ([1,2,3,4,5,6,7,8,9,10], 5.5)
next_keepers, next_outcome = strategy(n-1)
# This next bit of code could be generalized, but
# I'm leaving it explicit for clarity.
if next_outcome < 6:
return ([6,7,8,9,10], 0.5*8 + 0.5*next_outcome)
elif next_outcome < 7:
return ([7,8,9,10], 0.4*8.5 + 0.6*next_outcome)
elif next_outcome < 8:
return ([8,9,10], 0.3*9 + 0.7*next_outcome)
elif next_outcome < 9:
return ([9,10], 0.2*9.5 + 0.8*next_outcome)
else:
return ([10], 0.1*10 + 0.9*next_outcome)
for n in range(10):
keepers, outcome = strategy(n)
print n, '%.2f' % outcome, keepers
Output:
0 5.50 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1 6.75 [6, 7, 8, 9, 10]
2 7.45 [7, 8, 9, 10]
3 7.91 [8, 9, 10]
4 8.24 [8, 9, 10]
5 8.49 [9, 10]
6 8.69 [9, 10]
7 8.86 [9, 10]
8 8.98 [9, 10]
9 9.09 [9, 10]
Need to phrase question more properly.
But this is a variation of standard dice problem where we play a game to maximize our payout where we can chose the first outcome on dice or second. Answer there would be (3.5+5)/2
Now, suppose we are choosing outcome from second draw. Expected value is 5.5.
But for choosing an outcome from first draw it needs to be greater than 5.5 i.e. 6 to 10.
Thus, 50% chance that first would get 6-10(expected value is 8). And remaining 50% chance we would move forward to second draw and get expected value of 5.5.
Thus value of game = 0.5(8+5.5) = 6.75
I think the second case is more favorable to the player
Strategy: If number drawn is <= 5, try again.
With this strategy, Probability of getting more than 5.5 = 1/2 (drawn more than 5.5 in first try) + 1/2 * 1/2 (drawn less than 5.5 in first try and more than 5.5 in second try) = 0.75
So the price should be higher for the second case
Let X = 2/3 * (10+1) = 22/3
Probability of getting more than X is 1/3(Probability of drawing it in first try) + 1/2 * 1/3 (probability of drawing less than 5.5 in the first try, followed by drawing more than X in the second try) = 1/3 + 1/6 = 1/2
So the average payout is 22/3. So charge 8 per game
For case 1: 5.5 is the optimum price. If you want to make profit, charge higher :)
For case 2: 5.5 too
This is making the assumption that once a player picks a number that number is removed from the hat. This would mean however that the last player does not get a chance to put back and pick a card .
If the number is placed back in the hat , then you'll need to charge 10 (for assured profit in case 2) or 5.5 (in case 1)
You should charge the average price = 1+2+3+....+10 / 10 = 5.5
- shravan40 March 12, 2013or little more 6 but not more than it.
Since every number has equal probability for outcome.