I first posted this problem on Wilmott here (required login)
Thanks to Traden4Alpha and timeds on Wilmott for a clever solution which I didn't know about
On January 1st, 2007, you go to the Oracle of Delphi who tells you the EXACT future daily returns of a small stock (ticker FUTR) for the next N days. [N is very large]. Of course you are very happy about this, and want to profit optimally from it. But you have a 0.5% one-way transaction cost to buy or sell the stock. You can buy every day at the opening price and sell every day at the closing price (if you chose). After all N days have elapsed, you must sell the stock if you own it. What strategy do you follow?
(For people who like to make things overly-complicated, the stock is small and can't be shorted, has no options or futures, you cannot borrrow additional money to invest in the stock,etc.)
By the way, you don't own the stock currently, the first day the market opens is Jan 2, 2007 (tomorrow), and every opening price is the same as the closing price the day before.
Would you ever partially invest in the stock on any day??? Why or why not??
Is risk involved in any way???
What's the obvious strategy without transaction costs? Is that optimal with transaction costs? What sequence of stock prices would make it very much worse than optimal???
Would it be easy to prove that your answer is correct? If you implemented your answer as an algorithm, would it be O(N) or O(N^2)??
Now it's the same situation but the Oracle tells you the returns of each of K different assets for the next N days. That is, you are told a large k x N matrix of future asset reutrns. One of these assets is a "risk free" T-bill that never has negative return, but since you know the future none of the assets have any uncertainty for you: these future returns are guaranteed!!! What do you do?
Now, you pay a SINGLE transaction cost C to switch between assets, and you can never be neutral. i.e. if you don't hold any other asset, you must hold T-Bills, and it costs the same transaction cost to swtch between 2 stocks and to switch between a stock and T-Bills. Now you can trade assets if you want once at the begining of each day.
Looking for an O(N x k) algorithm, but O(N x k^2 ) is good.
These both have the same solution technique. I would expect people who have seen this solution technique before can do these without much trouble.