Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Nov 12, 2010

Optimal Trading Execution

You are trying to buy a stock at the best price. You need to buy it in the next 100 minutes. Every minute you will receive a random price (uniform distribution) that is a number between 1 and 100 dollars and decide whether to buy it or not.

1. Assuming you buy the stock in one trade, give a condition for buying the stock.
2. On average how many minutes will pass before that condition holds (expression or approximation is fine)?
3. If you could split up the trade, i.e, buy different amounts at different minutes, what would you do differently?

Update(Nov 17, 2010):
Solution posted by Sumit Somani (Senior Undergraduate, CSE, IITB) in comments! Same solution posted by me with spreadsheet in comments!

13 comments:

  1. As best price is not defined, I assume that the the strategy should achieve the minimum expected value of the stock over all possible strategies.

    1) suppose instead of 100 minutes, there was only 1 minute. Then u cant do anything. U will take what the price is (coz u have to buy the stock).
    Let Sn denote the random variable whose expected value gives us the expected value of the strategy should the time it starts from is the nth minute.

    Let the value of stock at the ith minute be Xi. (all are iid uniform 1 to 100)

    Hence S100=X100 => E[S100]= 50.5
    Now suppose we want to calculate S99. We should buy it at the 99th time interval if and only if X99<=E[S100] coz if X99 > E[S100] then we can always skip the transaction and still get a better expected price at t=100
    Hence
    S99=min(X99,E[S100])
    Similarly we can continue the argument to get..
    S98 = min(X98,E[S99])
    ...
    S1 = min (X1,E[S2])
    and hence the best expected value of the stock that we can buy is E[S1]

    2) Let tn denote the expected time for executing strategy Sn.
    => t100=1
    t99 = 1*P(X99<=E[S100]) + (1+t100)*P(X99>E[S100])
    = 1 + P(X99>E[S100])*t100
    Hence we get all such equations and finally
    t1 = 1 + P(X1>E[S2])*t2

    3) Here we assume that at the end of the 100th minute we want exactly a fixed amount of the stock.(which was pre-decided). i,e we do not buy a lot of shares exceeding the no of shares we decided, if the price of the shares becomes very less. If we were able to do this, its easy to see that we could get a value as close as possible to min(X1,X2,...,X100)

    clearly S100 is the only possible strategy for the 100th minute. Now suppose we get X99. Now if X99E[S100] then if we split, we are still making a loss coz we should buy the stock at the 100th minute.

    If X99=E[S100] it does not matter whether we split or not, so we would want to get the stock as early as possible, so we buy at 99th minute. Hence the strategy at 99th minute is the same as in part 1 even if we are allowed to split. Continuing this logic we see that it does not make sense to split at any time. We should just follow the strategy in 1)

    ReplyDelete
  2. I don't think your solution is correct.

    Suppose instead of 100, you had 2 minutes.

    If after first minute, the random number generated is 1, then you will buy the stock after first minute.

    If the random number generated is 100, you will not buy it.

    In general, you will buy after first minute only if random number generated is < 50.5

    and we have to continue calculating in this fashion.

    This is my thought. I might be wrong. Comment!

    ReplyDelete
  3. I solved this using excel the results i present in form of a list of tuples i.e. if Ith tuple is (k,m) look for prices in range[1,k] for m turns as soon as you get the price u r looking for u stop.
    {(2,25),(3,23),(4,13),(5,7),(6,6),(7,4),(8,3),(9,2),(10,2),(11,2),12,13,14,15,16,18,20,22,26,30,38,50,100)

    Expected share price u would get is 2.39

    Expected time u need to wait is 35.61 minutes

    ReplyDelete
  4. 1)We buy a stock at time t if the price that we are given is less than the expected price at that time.

    For i(not i+1) to be min in a set of k numbers chosen uniformly between 1 to 100 is ((100-(i-1)^k)-((100-((i+1)-1))^k)= ((101-i)/100)^k -((100-i)/100)^k

    I used a MATLAB to find expected min from k=1 to 99

    At any time t we buy a the stock if given price P is less than expected price in next 100-i time.

    100.0000 50.5000 33.8350 25.5025 20.5033 17.1708 14.7907 13.0058 11.6178 10.5075 9.5992 8.8425
    8.2023 7.6537 7.1783
    6.7625 6.3957 6.0697
    5.7782 5.5158 5.2786
    5.0629 4.8661 4.6858
    4.5200 4.3670 4.2253
    4.0939 3.9716 3.8575
    3.7508 3.6508 3.5569
    3.4686 3.3854 3.3069
    3.2326 3.1623 3.0957
    3.0324 2.9723 2.9150
    2.8605 2.8085 2.7588
    ..... 1.6299 1.6197 1.6098
    1.6000 1.5905 1.5812

    We can find the floor and hence the ans

    2) Now expected time is easy. We sum over time t multiplying with prob that condition 1) is met and time t and condition has not been met anytime before

    Ans I get is 51.2256 min

    3) Even when we can split trades, we still use the same strategy, hence the same ans

    ReplyDelete
  5. Sumit's solution is correct! Great work!

    Let expected Payoff function be EP(t)

    EP(100)=50.5

    IntEP(t) = FloorFunction(EP(t))
    EP(t-1)= (1-IntEP(t)/100)*EP(t) + [IntEP(t)/100]*(1+IntEP(t))/2

    Condition for buying the stock at t is if RV(t) is less than EP(t+1), execute the trade

    Using this, we get the following spreadsheet: http://bit.ly/cXxgnk

    Expected share price u would get is 2.39

    Expected time u need to wait is 35.61 minutes

    ReplyDelete
  6. @Gavri (Vivek).. Your logic seems correct but the numbers are wrong. Have a look at it again!

    ReplyDelete
  7. For part 3, the "quant" solution would be:
    Note this is essentially an American option, it’s suboptimal if one does not exercise, or partially exercise the option when the optimal stopping condition is met. hence the freedom of splitting up the trade gives no difference.

    ReplyDelete
  8. pratik's strategy has property that if it gives a price A and any other strategy gives price B, then E[A] <= E[B]. Can we also say that most of the time A <= B i.e. probability [A<=B] >= probability [B<=A].

    ReplyDelete
  9. Instead of achieving the minimum expected value one should have a strategy as follows:
    if the probability that, in the future, I get a value better than the current value is greater than 0.5 than i should not buy the stock otherwise I should buy the stock.

    So I should choose a threshold such that this probability is exactly = 0.5.

    So the threshold for each time t should be
    100 / (2^(1/(100-t)))


    I think the expected value strategy should only be followed when you can play the game many times over and then the expected value will be +ve.

    ReplyDelete
  10. oops...
    the threshold should be
    100 - 100 / (2^(1/(100-t)))

    ReplyDelete
  11. Abhishek, the flaw you are posing is a basic decision theory axiom.

    Wiki Link for Decision Theory

    Would you make choices in life based on probability greater than half or expectation?

    Consider two cases:
    1) Rs 1 with prob 0.99 and Rs 10000 crores with prob 0.01
    2) Rs 1.01 with prob 1

    In the second case, you get more money 99% of the time, but most people would choose case one, I think.

    ReplyDelete