The Oracle at Delphi
On January 1st you go to the Oracle at Delphi who tells you the opening and closing prices of a small non-dividend-paying stock every trading day for the rest of the year. Every opening price is the same as the closing price the day before. You have a 0.5% one-way transaction cost in buying or selling the stock, and can buy every day at the opening price and sell every day at the closing price ... if you choose. On the last day of the year you must not own the stock. What is the best you can do, having this perfect foresight? Every day you can buy stock at the opening price if you don t own it, and sell stock at the closing price if you do own it. Keep the problem simple, no leveraging, no short selling, no options or futures, zero interest rate, etc.
(Thanks to cdmurray80.)
We must determine at the start of each day whether to buy if we are neutral, stay neutral or sell if we are long, and do so in a way that maximizes our wealth. How hard can that be? Approached correctly this is a straightforward problem in 'dynamic programming.
Before we start, one trivial observation: Days of consecutive gains/losses may as well be treated as a single day, so that the stock effectively goes up, down, up, down, etc., on consecutive days.
Introduce some symbols:
Li = The maximum wealth you can have at the end of day i, given that you must hold the stock at the end of day i
Ni = The maximum wealth you can have at the end of day i, given that you must be neutral at the end of day i.
Now imagine that we have found the optimal strategy up to and including day i — 1. At the end of that day either you own the stock or you don't. What should we do on day i? If we are long on day i — 1 then we either stay long or sell (losing on transaction costs in the process). If we are neutral on day i — 1 then we either stay neutral or go long (losing on transaction costs in the process). Optimization is then achieved simply by looking at which of the alternatives is better. If we end up long on day i we can only have got there from two states, long already, or flat the day before and have just bought:
where Ri is the return over day i and k is the transaction cost, 0.5% in this example. This simply asks which is better out of staying long or selling and going flat.
The following image may be of some help in understanding this.
The above is easily coded up, as a simple loop, you just need to add the initial conditions that L0 = 0andN0 = 1, representing the initial wealth, and then the final result is max(N/,(1 — k)Lw), where M is the total number of days.
You need to hire a secretary. There are n possible candidates to interview and you want to find the best, the most talented. The problem is that there is great demand for secretaries, so if you want to make sure that you get one you'll have to offer her the job on the spot. Once she walks out of the door she s gone. You start interviewing candidates one after the other, they can all be ranked, so this one is better than that, or that one is worse than another, etc. There are no ties. But the order in which they are interviewed is random. What is the best strategy for maximizing the probability of getting the best secretary?
This problem is known in mathematical circles as the Secretary Problem, the Marriage Problem, the Sultan's Dowry problem, etc.
The best strategy is first to interview a number applicants with no intention of accepting any of them, call this number m < n. Then continue interviewing the rest one by one and then offer the job to the next one that is better than all of the ones previously interviewed, i.e. better than all the first m candidates that you interviewed but rejected out of hand. This is an example of an optimal stopping problem (not dissimilar to the problem of when to exercise an American option!). The question then becomes how many to interview, i.e. what is m?
Let's suppose that you have interviewed and rejected the first m applicants. You now interview the (m + 1)th. You will accept this one if she is better than the first m. What is the probability that the (m + 1)th applicant is the best out of all n? This one is easy. The probability that this is the best applicant is the same as any one being the best, i.e. 1/n.
What is the probability of choosing candidate m + 1 and her turning out to be the best of all? This is harder because you have to have rejected candidate m + 1as being worse than the first m and candidate m + 1 has to be the best of all. Well, the probability of m + 1 actually being the best out of all candidates is still 1 /n but she will only being offered the job if the best applicant out of the first m + 1 is also the best applicant out of the initial rejected m. Now that's easy. Imagine lining up the m + 1 rejected applicants in order of increasing talent from left to right, what is the probability that the very best of these is not at the right-hand end? Just m/(m + 1). So the probability of candidate m +1 being the best and being accepted
Next what is the probability of choosing candidate m + 3 and her turning out to be the best? Again we have the 1 /n probability of her being the best. And the probability of the previous best being in the first m out of the total rejected m + 1is m/(m + 1). So the required probability
Keep going in this vein, and add up all the probabilities to find that the probability of hiring the best applicant using this strategy is
And this is what we have to maximize!
If n = 3then m = 1, i.e. interview the first applicant with no intention of accepting. And then start interviewing with the intention of accepting. This gives you a probability of 0.5 of choosing the best.
If n = 4then m = 1. This gives you a probability of 11/24 of choosing the best.
If n = 5then m = 2. This gives you a probability of 13/30 of choosing the best.
The secretary question is often posed with the extra '... for n large....' What is the optimal stopping time as n -^oo?
The probability of success can be written as
Y, the Euler constant, 0.57722...
the probability of success can be approximated for large n (and assuming that m is also large) by
The maximum of this is easily found by differentiating with respect to m/n and we find in the limit of large n that m = n/e where e. So you should interview a fraction 1/e of all candidates before contemplating hiring anyone!