Oracle of Delphi - Hint
If you just want a hint, think about this.
What if, on day i, you knew two things
1) The value of the optimal strategy which leaves you with a long position at the end of day (i-1)
2) The value of the optimal strategy which leaves you with a neutral position at the end of day (i-1)
Could you compute the end-of-day value of the optimal strategy on day i???
Oracle of Delphi - About
I first posted this problem on Wilmott here (required login)
Thanks to Traden4Alpha and timeds for another clever solution which is different from the one I present
Oracle of Delphi 1 - Full Solution
The solution uses a technique called Dynamic programming (more on that at the bottom). DP is very clever, I didn't invent it: I think it was invented in 1953 and basically predates cheap electronic computers.
First I'll give an explanation, than an algorithm
Define the value of a strategy as the wealth you have from following it.
At the end of any trading day, there are long two possible states that matter: we own the stock or we don't. What if we know the value of the OPTIMAL strategy up to day (i-1) which will leave us with a long position in the stock at the end of day (i-1): call this L(i). Also, assume we know the value of the optimal strategy up to day (i-1) which leaves is with a neutral position in the stock at the end of day (i-1): call this N(i-1). Then we can compute the next values L(i) and N(i) as follows.
L(i), which is the optimal value at the end of day(i) which leaves me with a LONG position in the stock, is the better of
1) Not owning the stock on day(i-1), buying it on day i, paying a trans. cost and earning the day(i) return
2) Owning the stock on day (i-1) and holding it, earning the day(i) return
N(i), the optimal value at the end of day(i) which leaves me with a NEUTRAL position in the stock at the end of the day, is the better of
1) Not owning the stock on day (i-1) and not buying it on day(i), earning 0% return on day(i)
2) Owning the stock on day(i-1), holding it on day(i) to earn the day(i) return, and selling it at the close on day(i), paying a trans. cost
(3) [don't worry about buying at the open of day i and selling at the close, because case 1 covers this]
Algorithm - Definitions
Define L(i) = {The maximum wealth you can have at the end of day i, given that you must hold the stock at the end day i.}
Define N(i) = {The maximum wealth you can have at the end of day i, given that you mush hold be neutral (not hold the stock) at the end of day i.}
R(i) = the return on day i, which is closing price on day i divided by the opening price on day i.
C = 1 - transaction cost. e.g. C=99.5% means a 0.5% transaction cost
Algorithm - Actual
L(0) = 0
N(0) = InitialWealth
for i = 1:NDays
L(i) = max[ L(i-1)*R(i-1) , N(i-1)*C*R(i) ]
N(i) = max[ N(i - 1) , L(i-1) * R(i) * C ]
end
OptimalWealthAtEnd = Max( N(NDays), L(Ndays)*C )
To figure out when to buy and sell, we work backwords from day(N+1) to see which of the clauses in the MAX had the highest value: this bookkeeping would clutter the solution but is simple.
Note this is O(NDays)
More about Dynamic Programming
When given a problem of size N, Dynamic programming works when the solution to the problem can be quickly gotten from a solution to the problem of size (N-1). Many problems that seem very hard to people who haven't seen them before can be solved by dynamic programming. The dynamic programming solutions to problems are hard to derive and explain, so they make great test questions on CS exams, but have some nice properties
1) The code is usually embarrassingly short and simple.
2) Usually a dynamic programming solution is constructed from a proof of optimality, so it's easy to prove the solution is optimal.
For the Oracle of Delphi problem, we know that
1) The optimal solution as of day(i) certainly acted optimally through day(i-1)
2) The optimal solution as of day(i) which ends day(i) with a long position certainly either bought the stock on day(i) or held if from day(i-1)
etc.
For an example of how to solve a problem that is 'hard' (if you've never seen it before) with dynamic programming, consider the string edit distance problem. You are given two text strings
'survey' and 'surgery', and much change the first into the second through the minimum number of the following three operations
a) delete a character from string 1
b) insert a character into string 1
c) change a character in string 1 into a different character.
The solution is elegant and gives VERY short code: see pages 3-5 of the following PDF (thanks to Prof. Faloutsos)
Oracle of Delphi 2 - Hint
Read the full solution to Oracle of Delphi 1
Oracle of Delphi 2
Now there are K different assets, and N days, and we know all the k x N returns R^j(i) for asset j on date i.
Definitions:
W^j( i ) is the maximum wealth you can have, at the end of day i, when you are fully invested in asset j at the end of day i.
We'll imagine asset 1 is the risk-free asset, and initially we're fully invested in T-bills on day 0, so
C is what remains after a transaction cost. e.g. C=0.995 if the transaction cost is 0.5%.
Algorithm O(N k^2)
W^1(0) = initialWealth
W^2(0) =W^3(0) = ... = W^k(0) = 0
for i = 1:N // for each day
for j = 1:k // for each asset
W^j(i) = R^j(i) * Max[ C*W^1(i-1), C*W^2(i-1), ..., W^j(i-1),... C*W^k(i-1) ] ***
next j
next i
Notes
Note that in the line marked ***, all assets except asset j are multiplied by C, the transaction cost reduction.
Speedup to O(Nk)
If we really care about speed, we can do the following
for i = 1:N // for each day
m = < index j of which W^j(i-1) with largest W^j(i-1).> a.k.a. < ARGMAX [over j] of W^j(i-1) >
for j = 1:k // for each asset
W^j(i) = R^j(i) * Max[ C*W^m(i-1), W^j(i-1) ]
next j
next i
I think these solutions are correct, but I'm not sure and open to comments: cdmurray80@gmail.com