Tuesday, March 8, 2011

Can one beat a Random Walk-- IMPOSSIBLE (you say?)

Firstly, apologies for the long absence as I've been busy with a few things.  Secondly, apologies for the horrific use of caps in the title (for the grammar monitors).  Certainly, you'll gain something useful from today's musing, as it's a pretty profound insight for most (was for me at the time). I've also considered carefully, whether or not to divulge this concept, but considering it's often overlooked and in the public literature (I'll even share a source), I decided to discuss it.


Fig 1. Random Walk and the 75% rule

I've seen the same debate launched over and over on various chat boards, which concerns the impossibility of theoretically beating a random walk.  In this case, I am giving you the code to determine the answer yourself.
The requirements: 1) the generated data must be from an IID gaussian distribution 2) series must be coaxed to a stationary form.

The following script will generate a random series of data and follow the so called 75% rule which says,
Pr[Price>Price(n-1) & Price(n-1) < Price_median] Or [Price < Price(n-1) & Price(n-1) > Price_median] = 75%.  This very insightful rule (which is explained both mathematically and in layman's terms in the book 'Statistical Arbitrage' linked on the amazon box to the right), shows that given some stationary, IID, random sequence that has an underlying Gaussian distribution, the above rule set can be shown to converge to a correct prediction rate of 75%!

Now, we all know that market data is not Gaussian (nor is it commision/slippage/friction free), and therein lies the rub. But hopefully, it gives you some food for thought as well as a bit of knowledge to retort, when you hear the debates about impossibilities of beating a random walk.

R Code is below.

##################################################
#gen rnd seq for 75% RULE

#generate stationary rw time series
rw<-rnorm(100)

m<-median(rw)
trade<-rep(0,length(rw))

for(i in 1:(length(rw)-1)){
if(rw[i] < m) trade[i]<- (rw[i+1]-rw[i])
if(rw[i] > m) trade[i]<- (rw[i]-rw[i+1])
if(rw[i] == m) trade[i]<- 0}

eq_curve<-cumsum(trade)

par(mfrow=c(2,1))
plot(rw,type='l',main='random walk')
plot(eq_curve,type='l',main='eq_curve')

44 comments:

  1. there's a look ahead bias in the code, m = median(x), at time 0, you do not know all of x, so you cannot computed median(x).

    it should be m = 0

    ReplyDelete
  2. The exercise is based upon the assumption that the underlying distribution is normal. Therefore, the mean will converge to whatever value you set it to, with a sufficiently large sample. In this case, I used a small sample set with the mean defaulting to zero. Run a longer series and you'll see it converge to the expected mean(expect the median to approach the mean as well for the normal model) .

    In no way does that issue detract from the insights promulgated though.
    Thanks for commenting.

    ReplyDelete
  3. An RSI transformation of market prices is Gaussian - would the 75% rule be profitable on RSI(price) or does the "identically distributed" requirement cause a problem (or comms/slippage)?

    Nice equity curve - I will play with the code at the weekend.

    ReplyDelete
  4. I have trouble understanding this using my common sense. And I can't seem to find the book reference.
    A random walk would imply that return values have no autocorellation whatsoever ( r(1) is not influenced by r(<1) ). So at time t one has 50% chance of going up and 50% chance of going down and no 'clues' from the past data.
    So how does the algorithm manage to take the 'right' decision?

    ReplyDelete
  5. anon,
    Serial correlation is indeed an issue with real market data (as well as fat tails, friction, and other issues) and will alter the 75% rule. There are some relaxations on the strict requirements outlined above; please see the text for additional elaboration.

    ReplyDelete
  6. Sjev, the book can be accessed on the amazon showcase to the right.

    There is a great deal of intuitive geometrical interpretation covered in the text as well as analytical proofs. Yes, IID implies zero auto-correlation, as you noted. However, one way to think about it intuitively is to imagine the likelihood of two independent 3+ sigma events in the same direction (or even opposite) occurring in sequence. Ignoring the binary coin toss analogy for a moment, what do you imagine the likelihood of the above would be? Surely there should be a greater likelihood of hitting the bulk of the distribution area (the center of the bell curve) on the next trial (simply because there are many more samples that will occur in the center of the distribution, therefore they should be expected to be hit more likely over the average run)? I don't know if that's the best analogy, but it's one way to intuitively think about it. The 50/50 coin toss analogy is a bit limiting in this case.

    Hope that helps, IT.

    ReplyDelete
  7. So this is fairly obvious if it's bad today it's more likely to be better tomorrow (if on average it should be zero). Now I don't understand how you could use that for trading in any way since the chances of winning or loosing are still 1:1. I'm not sure if I misunderstood anything but i don't get why the median (0) is used and not the mean.

    ReplyDelete
  8. Because the error process is Gaussian and IID, it is an extremely well-behaved, stationary process, so it's trivially possible to trade it profitably (without considering costs). Although the 75% rule can be proved analytically (and Andrew Pole does prove it), I don't believe it is overlooked...I think the reason people don't talk about it is that you will probably never find a spread or price whose increments are IID, much less normally distributed!

    IMHO, the 75% rule is a nice academic concept to introduce the idea of trading mean-reverting series. And that's all it is.

    Maybe what people mean by "it's not possible to trade a random walk" is that it's not possible to build a successful trend model?

    ReplyDelete
  9. The chances of hitting any value (positive or negative) after a 3-sigma event are exactly the same as after NOT hitting it, by definition.
    I often have similar discussions, with people claiming (let's return to a coin for this one) that 10 same sides in a row is extremely improbable (0.5^10), so once you get 9 times 'heads' the next one should be 'tails'. But its wrong. The chance for *every* throw is exactly 50%, so is it for the 10'th.
    Unfortunately being a Matlab guy, I don't follow the R code. However, looking at your equity curve derived from random walk I suggest you double check for datasnooping.

    ReplyDelete
  10. the main issue is not that it is gaussian or not, the main issue is that you say "series must be coaxed to a stationary form".

    So you force your price to mean reverting, you trade it has if it was mean reverting and it works...

    do the same experiment without forcing the serie to mean revert and you'll see a loosing trading strategy

    Browian motion means actually "not mean reverting"

    ReplyDelete
  11. Beside median(x), you are using x[i+1] to compute rule_below[i] and rule_above[i]. If I only use information up to time i, my equity curve has a normal distribution.

    ReplyDelete
  12. Thanks for your intriguing post. I'm trying to interpret your code to get an understanding of the implied trading rule. Could I impose upon you to try to summarize the rule in language rather than code? I'm especially trying to get an understanding of whether the values in x are supposed to represent relative price changes akin to diff(log(timeseries)) or whether they are actual prices. It appears they are supposed to be relative price changes, but then I don't understand the assignment to change in:

    if(rule_below[i]!= 0) change[i]<-x[i+1]-x[i]
    if(rule_above[i]!= 0) change[i]<-x[i]-x[i+1]

    If these are one day holding periods, why are you taking the difference between each days relative price changes?

    Thanks

    ReplyDelete
  13. It might seem obvious after seeing the result, but I can tell you I've seen numerous people disagree with the conclusion over the years without seeing proof. I'll leave further applications for the creative=)

    The mean and median are the same in the case of Gaussian generated data, however, other types of generating processes (like log-normal distributions for example) require the median for the geometry to work out.

    Cheers,
    IT

    ReplyDelete
  14. alex,

    Thanks for the comment,and it's nice to see some get it. Believe me when I tell you that many will disagree vehemently at even the slightest notion of finding a method that beats any kind of random walk. By hopefully showing it in a simple manner, they can be persuaded to open up their beliefs.

    Cheers,
    IT

    ReplyDelete
  15. I'm not sure what do you think the code does, but in fact the loop is equivalent to the following:

    for( i in 1:(length(x)-1)){
    change[i]<- abs(x[i]) - sign(x[i]) * x[i+1]
    }

    Summing all the increments you find that each variable x(i) appears twice, with 50% probability one occurrence is positive and the other is negative, so they cancel out, with 50% probability both terms will be positive. No wonder that there is a trend...

    But you could just as well do the following (be long the days the market is up, be short the days the market is down):

    for( i in 1:(length(x)-1)){
    change[i]<- abs(x[i])
    }

    If you fix your code to actually use past information only the effect will disappear (as long as there is indeed no autocorrelation in the series)

    ReplyDelete
  16. Sjev,

    I thought of perhaps a better analogy last night (I often reply pretty quickly without giving too much thought). Rather than think of a coin toss, imagine a bag of marbles. Suppose you have two green marbles and 98 black marbles. If you draw one green marble, and throw it back in the bag, your next draw will be completely independent of the first. Do you see that the next draw will be less likely to be a green marble? The same analogy can be extended to drawing two three sigma observations in a row. Statistically, you have a joint likelihood of P(g,g) = 2/100*2/100, which is far less likely than P(g,b)=2/100*98/100. There is not violation of independence here, yet, the conditional likelihood simply collapses to the joint probability for independent events.

    IT

    ReplyDelete
  17. Don't get me wrong, I'm very open to all new insights, especially on the fundamental issues like this one. But I must admit that I just don't get it. I'd be glad to verify your results if you could explain in a little bit more detail how the strategy works. A piece of pseudocode would be very welcome.

    ReplyDelete
  18. Anon,
    Regarding look forward bias (others have mentioned similar concerns). rule_above/rule_below is only dependent on the median (which is obviously estimated by the average of the data stream in the gaussian case), the x[i+1] data is a signal generated by the rule.

    The equity curve is generated by taking the signal if an only if the signal tells you to take a positive or negative position (it must take the signal regardless of whether it was correctly predicted or not).

    Cheers,
    IT

    ReplyDelete
  19. Sjev and others,

    If for whatever reason, you are having trouble interpreting the code, I would highly suggest simply taking the basic rule as outlined in the blog body and generating your own literal interpretation of it. Only when you see it with your own eyes, will it convince you of its veracity (or not). I generated the R code pretty quickly, but I'm pretty confident the translation is correct (I haven't seen any glaring flaws pointed out yet).

    I've a few other comments to get to, which I will sometime today. Thanks for all the interest.

    IT

    ReplyDelete
  20. "Suppose you have two green marbles and 98 black marbles. If you draw one green marble, and throw it back in the bag, your next draw will be completely independent of the first. Do you see that the next draw will be less likely to be a green marble?"

    No, that is not correct. What you are describing is sampling with replacement. If you return the green marble to the bag, then there is still a 2% chance of drawing a green marble from the bag on the next try. That is the essence of independence.

    ReplyDelete
  21. Maybe you should fix the positions to make reference to x[i+1] and x[i+2]?

    As it stands now (assuming m=0) your loop is equivalent to

    for( i in 1:(length(x)-1)){
    change[i]<- abs(x[i]) - sign(x[i]) * x[i+1]
    }

    You're deciding to be long (short) each day depending on the market returns that same day...

    ReplyDelete
  22. Regarding the marbles: you are right about the chances of getting a 'royal flush' P(g,g,g,g,g) = 0.02^5 being pretty slim. Indeed, with the marbles you could determine the PDF by enough samples if you don't know it from the start. After you know that the chance of picking a black one is higher than the green one, you just start betting on picking a black one.

    Now, in the case of a symmetric gaussian PDF and no autocorrelation, there should be simply no way of changing the expected return per trial, which is in your case 0 by definition.

    ReplyDelete
  23. Pr[Price>Price(n-1) & Pr<(n-1) < Price_median] Or [Price < Price(n-1) & Price(n-1) > Price_median] = 75%

    Is this section a typo:
    & Pr<(n-1) < Price_median]

    Should it really be:
    & Pr(n-1) < Price_median]

    I'm slightly confused because it seems like there's one too many inequality signs. Thanks

    ReplyDelete
  24. IT has a valid code and no look forward bias

    As a programmer, hope IT doesn't mind I post another implement, it's really a great thing more and more people use R for these kind of analysis


    len <- 10000
    x<-rnorm(len)
    m <- median(x)

    change<-diff(x)
    signal <- ifelse(x<m,1,-1)[-len]

    hit <- sum((sign(change)-sign(signal))==0)/(len-1)

    par(mfrow=c(2,1))
    plot(cumsum(x),type='l',main='random walk')
    plot(cumsum(change*signal), type='l',main='rule based equity curve')

    ReplyDelete
  25. None of these comments seem to get at the real issue. It has nothing to do with the choice of distribution, looking forward in the time series, mean reversion, etc. etc.

    The issue is that the x's represent _increments_ (first differences) of the random walk (which is what you are betting on when you invest); however, when you are computing your total hit rate, you are computing the number of times the _change_ in the increments (i.e., second differences of the random walk) have the predicted sign. (In translating your rule, you represent "price" as "x", however, "x" is really the change in price. If you really do mean the price to be x, then the price is not a random walk but an iid sequence.)

    However, the second differences are _not_ a martingale with respect to the first differences. Moreover, when you are investing, you are making/losing money based on the daily returns (first differences), not the daily change in the returns (second differences). So, this is not a counterexample about beating a random walk.

    ReplyDelete
  26. Thanks for the contribution and validation, senne.
    I still have a lot of comments to address, but alas, I'm currently bogged down in repairing someone's BOD.

    ReplyDelete
  27. anon, thanks for catching the rule typo. Sometimes the html editor messes up my original draft, so it's nice to have viewers double check these things. Also, the comments and replies are not all in perfect order, as I don't have a way to align them (that I know of yet).

    ReplyDelete
  28. Thanks for all the comments (pro and con), I likely won't be addressing all of them.

    For the posters that asked for a simple language translation, I'll try to simplify. The basic idea is that if you have a stationary price series that is a gaussian distribution (you can induce it to that form or generate the stationary series as in this case); you apply the following rule to predict each next price change. If the price now is below the median, the next change will be predicted as a + one, if it is above the median predict the next change as a - one. You will see that over a very large number of trials, the total predictions will converge to 75% correct hit rate. The cumsum is the total cumulative equity of both correct and incorrect predictions.

    Please play with the program I gave and try to convince yourself whether it makes sense or not.

    If you can understand the concepts within, you have a good foundation to begin to understand the fundamental concepts behind statistical arbitrage.

    If you have any more questions, please do go out and get a copy of the book I sourced for a more elaborate explanation.

    IT

    ReplyDelete
  29. After some though, I came to the following conclusion. If the stationary variable is a spread, then IT's code is correct, as you can trivially trade a mean reverting level variable. However, IT is interpreting the stationary variable in the code to be the change in a random walk (i.e.the log-return). In this case, when calculating the P&L, there is a mistake. Basically, if at time t the return is above (below) the median, the strategy opens a short (long) position. So the P&L at time t+1 would be just the return a time t+1, multiplied by the direction of the trade opened at time t (1 for buy, -1 for sell), not a difference in "returns".

    Now, if the stationary variable is a spread, then the P&L is actually the difference in the spread, as IT has coded. The reason is that the spread is a level variable, and you can buy it at time t-1 and sell it at time t to earn the difference. But with log-returns, you are already working with a 1st difference, so you cannot buy the return at time t-1 to sell it at time t and earn r(t)-r(t-1). To earn that differential you would have needed an open position at time t-2. It's a simple case of look-ahead bias.

    This is the same point made by Anonymous at 1:12. By modifying the code; you will find that you do not beat the random walk. However, if you could find a stationary level variable such as a spread, you could still make money with the rule. Now, show me an iid spread, I've never seen one!

    ReplyDelete
  30. yes! it is a spread. That is (or was) the intention of the illustration. I'll think about your response a bit more, but I appreciate cogent replies. Thanks.

    Certainly there is no free lunch, or we would all be printing free money. But the intention is to show some of the seeds of statistical reversion properties that would otherwise be shot down in flames by those who believe there is no system that can somehow take a randomly generated time series and generate a guaranteed profitable rule set.

    How many traders would even agree that a IID spread,stationary random series could be traded profitably? As is evidenced in the replies; not many.

    IT

    ReplyDelete
  31. I've had a long day and had a chance to look back at some of the posts. Clearly, some astute observers have caught some not so clear expression of thoughts. Apologies for misleading on the notion of a true random walk in the integrated sense, yes, it should more fairly be called a random sequence (in this illustration). Note that there is a way to extend the concept to a true integrated random walk model that has guaranteed normal residuals, but I'll save that for another time perhaps.

    I've updated the code and fig to hopefully make that more clear for future readers. Thanks all for the great input.

    IT

    ReplyDelete
  32. "How many traders would even agree that a IID spread,stationary random series could be traded profitably? As is evidenced in the replies; not many."

    The replies (at least mine) were about beating a random walk, as depicted in the first figure. Your point is much clearer now, thanks for the clarifications and for updating the chart (which is no longer a random walk!). Given such a series of prices I think everyone agrees that buying when the price is below the "fair" value and selling when it's above you can get a profit. No need to be a trader... even my mother would get it.

    ReplyDelete
  33. The rule is correct, and so is the code. I have to say that the "anonymous" comment posted at March 9, 2011 1:29 PM is spot on! Alex's last post also pointed out the problem.

    Predicting the change-in-returns is not going to help decide which side to bet on. Unless the actual price series is "rnorm(100)", it is much much trickier than what meets the eye to translate the rule into a trading model.

    ReplyDelete
  34. There is an error I think.
    You can't know the Median for whole data at the begining. You should slide the median when were the trade time!

    The code should be like this:

    ##################################################
    #gen rnd seq for 75% RULE

    #generate stationary rw time series
    rw<-rnorm(100)
    trade<-rep(0,length(rw))

    cost=0.3
    for(i in 10:(length(rw)-1))
    {
    m<-median(rw[1:i-1])
    if(rw[i] < m && rw[i] m && rw[i]>rw[i-1]) trade[i]<- (rw[i]-rw[i+1]-cost)
    if(rw[i] == m) trade[i]<- 0
    }

    eq_curve<-cumsum(trade)

    par(mfrow=c(2,1))
    plot(rw,type='l',main='random walk')
    plot(eq_curve,type='l',main='eq_curve')

    ReplyDelete
  35. tig3r,

    It is true we can't know the median beforehand. However, in this illustration we know what it is because we are generating the underlying process (with rnorm(n) you implicitly set the mean & median to zero if the mean is not set otherwise).

    We should expect it to converge to zero over time. In a more practical application, however, a sliding window for short lengths, or a very large window with a median that converges to a stable value might be more appropriate. The key is to have some constant value and observe the dispersions about that value.

    Thanks for your comments,
    IT

    ReplyDelete
  36. the expectation of an ito integral is a martingale for any integrand defined on the same filtration. this holds too for integrators that include jump discontinuities so long as the integrator is chosen such that it is left continuous (this ensures your trading strategy cannot know the jump before it occurs). Shreve's stochastic calc vol II is the best treatment i have seen on the topic.
    but more generally it seems like your code and argument is along the lines of, "if we get a down (up) x sigma move the likelihood of a move in the same direction and of greater magnitude is f(x) < 50% so we buy (sell) the asset". Okay, so a stock is down 5% today and you buy, then its down another 2% tomorrow--you didnt make money.
    I'd challenge you to find any real financial series which you could back test this on and have it work. I'll even let you ignore transaction costs and trade at mid market.

    ReplyDelete
  37. emb,

    There have been some similar studies performed on bond instruments in literature. Pairs trading follows a similar logic as your explanation (there is a lot of literature available on this).

    But, the purpose of this illustration is not meant to give any secret trading secrets so much as to give ideas about possible ways to think about exploiting randomness (specifically, a well defined process such as stationary IID and Gaussian generated).

    I haven't read the Shreve text, but if I get a chance it sounds interesting. Thanks for sharing.

    IT

    ReplyDelete
  38. But the point is that ANY ito integral will be a martingale, so there is no way to "exploit randomness" in the sense that you cannot develop a trading strategy that has a positive expectation (as long as the random increments have zero mean and are uncorrelated). If you chose the integrator to be a simple brownian motion then the increments are normally distributed. The point is that your argument is incorrect, you will not be able to do what you described, either with a properly simulated data set or on a real financial series. Sorry, no free lunch here.
    emb

    ReplyDelete
  39. I am NOT saying you can't beat a random walk
    but there is a logical error in your code.

    Try replacing the rw data with your favorite stock or indice data. I tried it with one year of spy. Got over 200% CAGR !!!

    Another tell something is not right is that you can change the median to anything between -4 and 4 and still get very strong results.

    regards,

    prazor

    ReplyDelete
  40. prazor,

    I'm glad to see some posters experimenting with the code. Please continue to experiment and post observations. You might also want to post the modified script so others might share in your observations. Everyone learns something from looking at experiments first hand, and that's really the direction I intended on this thread.

    cheers,
    IT

    ReplyDelete
  41. I'd say you can beat a true random walk (not an integrated one) fairly easy. One dimensional random walks always returns to the origin (http://mathworld.wolfram.com/PolyasRandomWalkConstants.html), so the strategy is simple: buy. if you reach a previously chosen profit sell or sell when you hit again the first price. You can't lose money in the long run. Is there something wrong in this strategy?

    ReplyDelete
  42. Hello,

    First I would like to thank intelligent trading for this very intersting blog.
    Now concerning our problem, I think the trick lies in the wording of the problem.
    As already mentioned, we are dealing with a time serie that is randomely generated but not with a random walk. Let's take the first two steps to understand better.
    At the the first step we get x1 and p(x1) ~ N(0,1). We have genereted x so that it follows a Normal distribution.
    At the second step we get x2 so that p(x2|x1) ~ N(0,1), it is obviously the same as p(x1) by construction but this is not a random walk. To have a random walk you should have p(x2|x1) ~ N(x1,0), which means that being in the state x1 you have a probabilty to get to x2 that is normally distributed AROUND x1.
    So no you can't beat the random walk, but yes you can create a wining trading strategy if you can find stationarity in a distribution. Pair trading is based on this principles, we look for spreads (or more generally combination of assets) that are stationary, this is called cointegration.
    Thanks again for the posts.

    Pop

    ReplyDelete
  43. Thanks for all the latest comments. I hope there's enough in the prior comments to address any repeated issue(s). I think it's safe to say most readers agree that a random stationary series can have a corresponding algorithm with a long term hit rate > 50%. Some posters find this fact so simple 'my mom could do it,' others are a bit skeptical, but I think most agree by now.

    Although there are many comments regarding impossibility of ever coming up with an algorithm to beat a perfect (integrated) martingale on any time frame and any condition (and whether markets even exhibit this behavior under all conditions); I will simply leave it up to readers to draw their own conclusions here.

    IT

    ReplyDelete
  44. Fun food for thought... Thank you for that!

    Since: trade<-rep(0,length(rw))...

    if(rw[i] == m) trade[i]<- 0 :would be redundant.

    Cordially,

    -DD-

    ReplyDelete