StuartReid | On April 18, 2016

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/customer/www/turingfinance.com/public_html/wp-content/plugins/latex/latex.php on line 47

In Hacking The Random Walk Hypothesis we applied the NIST suite of cryptographic tests for randomness to binarized daily market returns. Overall the NIST suite failed on the data. This result was taken to mean that markets are not quite the "coin flipping competition" famously posited by some notable academics. That having been said, some of the tests in the suite did pass indicating some degree of noise in market returns.

One such test, the linear complexity test, caught my eye because it applies compression to test the randomness of a sequence. This idea - that randomness is related to compressibility - dates back to Claude Shannon's information theory. Which, through algorithmic information theory, is related to Alonzo Church and Alan Turing's computability theory. Being a computer scientist these topics fascinate me; almost more-so than the markets do.

In this article we will expand upon this line of thought by applying greedy lossless compression algorithms to binarized and de-trended market index returns and, spoiler alert, we will arrive at some unexpected conclusions. Following this article we shall continue our non-random walk down wall street by considering lossy compression algorithms (including auto-encoder neural networks) and then Lo's test for long term memory in stock markets. 

.

As mentioned in my last post, Stock Markets Do Not Follow Random Walks, the featured images for this series of articles are simply screenshots from some of my favourite Wall Street inspired films. This featured image is taken from the classic 1987 Wall Street movie and is, of course, portraying the infamous Gordon Gekko. 

---

Article Outline

The article is broken up into the following sub sections,

1. The Efficient Market and Random Walk hypotheses.
2. Algorithmic Information Theory and Randomness.
3. Compression and Market Randomness; Challenges.
4. Proposed Compression Test of Market Randomness.
5. Overview of Lossless Compression Algorithms in R.
6. Results obtained and their meaning(lessness)?
7. Conclusions and further research efforts.
8. Appendix A: Link to all of the source code.

---

The Efficient Market and Random Walk hypotheses

The strong form of the efficient market hypothesis states that markets accurately and instantaneously discount all publicly and privately-available information about a security into its price. As such, the best forecast of any securities price tomorrow is just its price today because its price today is necessarily correct.

Furthermore, this hypothesis implies that no careful study of past prices - or fundamental or economic information - will result in a consistently more accurate forecast of the securities price in the future. In an informationally efficient market the change in price from today to tomorrow depends upon unknowable information from tomorrow; which is why the change is random from today's perspective and a rational reaction from tomorrow's perspective. Only time-travellers and high frequency information arbitrageurs can hope to beat this market.

Despite my inclination towards more "complex" market hypotheses such as evolutionary and behavioural finance, I cannot argue that the efficient market hypothesis is without merit. It has merit for three reasons. Firstly, markets are damn difficult to forecast. Secondly, the average active manager does not beat the market consistently. And thirdly, the efficient market hypothesis has enabled exciting financial innovations such as derivatives securities. However, having merit does not imply that the hypothesis is true; it most probably isn't true.

The strongest criticism of the efficient market hypothesis originates from behavioural finance which challenges the underlying assumption that investors are rational, or rather, that they are rational enough to accurately price securities. Given all the available information about a security it's unlikely that market agents would agree on a price. Agents do not have homogeneous expectations in reality; as such, there is no intrinsic value in reality.

My favourite criticism of the efficient market hypothesis comes from evolutionary finance. According to evolutionary finance markets are complex systems consisting of heterogeneous agents which interact with one another and are subject to evolutionary forces. Through these interactions and as a result of evolutionary forces statistical properties emerge. Emergent properties of markets include randomness, momentum, value, and reversion but none of these properties are persistent or truer than the others. Their magnitudes change as the population of market agents adapt, evolve, and succumb. Such properties are, therefore, not anomalies (as they are called under the efficient markets hypothesis), they are expected emergent properties of markets.

In response to such criticism two variations of this hypothesis were proposed. The semi-strong form of the efficient market hypothesis relaxes the definition by stating that only publicly available information is discounted into a securities price and the weak-form of the efficient market hypothesis states that, at the very least, all historical price and volume data is discounted into a securities price. The key takeaway is that regardless of the definition you choose, in the absence side-information, the evolution of asset prices follows a Markov process; a random walk.

This theory, dubbed the random walk hypothesis, lies at the heart of almost all modern day asset pricing models which essentially assume that prices evolve according to a Markov process or random walk. Whether or not this is true has obvious and profound implications for you, me, and (almost) everybody else on this planet. Which might explain why academics and practitioners have spent decades studying the relative efficiency and / or randomness of markets. Our last article introduced one such test: Lo and MacKinlay's heteroskedastic variance ratio test. In this article we will consider, amongst others, the popular Lempel-Ziv compression test.

---

References for this discussion

If you enjoy the philosophy of markets as much as I do, here are a few of my favourite publications:

---

Algorithmic Information Theory and Randomness

The study of randomness is not an activity unique to quantitative analysis and economics, it is central to many fields including cryptography, quantum mechanics, and genetics. Therefore, it is quite unsurprising that we have borrowed and re-purposed ideas from other fields to argue in favour of, or against, the efficiency or randomness of markets. Nowhere is this more true than the field of algorithmic information theory, an amalgamation of computability theory and information theory (a.k.a a computer scientists dream). As Gregory Chaitin once stated,

---

"It [algorithmic information theory] is the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously."

---

As mentioned previously one of the ideas borrowed from algorithmic information theory by economists is the idea that random sequences are incompressible. Let's take some time to explain the thought process behind this ...

In the 1930's Alan Turing introduced an abstract model for computation called the automatic machine or, as it has come to be known today, the Turing Machine. I'm not going to explain the mechanism behind the Turing Machine (you can find that at Cambridge's website or Wolfram Mathworld) because it is not relevant to our discussion of randomness. All you need to know is this: "despite the model's simplicity, given any computer algorithm, a Turing machine can be constructed that is capable of simulating that algorithm's logic" - Wikipedia.

.

What is an algorithm? In it's most simple form an algorithm is a deterministic sequence of steps for transforming a set of inputs into a set of outputs. Consider the the Fibonacci sequence as an example. The sequence of numbers starts with 0, 1 and proceeds as follows: 1, 2, 3, 5, 8, 13, .... The algorithm for reproducing this sequence can be stated very simply: the next term in the sequence is just the sum of the previous two terms. Additionally it is extremely easy for a Turing Machine to emulate this logic; the resulting program - found here - is quite simple.

What is complexity? According to another great mathematician, Andrey Kolmorogov, the complexity of a sequence can be measured by the length of the shortest computer program that produces the sequence as output. If that program is shorter than the original sequence then we have compressed that sequence; we have encoded it.

What happens when we give our Turing Machine a random sequence, S? If the data is random that means that there is no logic that was used to produce it. If there is no logic there is nothing for the Turing Machine to simulate. Therefore, the only program that will produce the random sequence as an output, is the random sequence: print S. 

The program, print S, is longer than the random sequence, S. Therefore a random sequence necessarily has a Kolmorogov complexity greater than the original the sequence itself. This can be interpreted as saying: a random sequence is incompressible ... but here's the [halting] problem: how do we know for a fact that the program we have found which outputs the sequence is the shortest one possible? We would have had to have to tried every single possible program, of which there are an infinity, to make such a conclusion. It's an impossible task.

Put simply the Kolmorogov complexity of a sequence is incomputable and, as such, randomness is incomputable. We cannot prove that a sequence is random but, that doesn't mean that we can't test the probability that a sequence might be random. This is where all of our statistical tests for randomness come into play ... some of which use compression algorithms to test whether or not a statistically significant amount of compression is achievable.

---

Some of those who we have to thank for algorithmic information theory:

 

---

Compression and Market Randomness; Challenges

There have been quite a few academics who have attempted to use compression algorithms to test the efficiency of markets. At face value this may seem like a well formulated idea, but the idea faces some unique challenges. 

---

Challenge 1 - Infinite vs. Finite Sequences

The first challenge (which isn't really a problem) is that our information theory definition of randomness applies as sequences approach infinite length. Any sufficiently finite sequence is likely to be slightly compressible on the basis of probability alone. As such when using compression to test relatively short sequences of market returns we are not interested in whether the algorithm was able to compress the returns, we are interested in whether the degree of compression is statistically significantly more than what is expected on a random sequence.

---

Challenge 2 - Market Drift

The second problem is that there are different types of randomness. The first type, often called the Martingale property or true, algorithmic, or Kolmorogov randomness, is the one most often associated with information theory and computer science (especially cryptography). The second type of randomness, called predictability or the Markov property, is most often associated with finance, stochastic processes, and the random walk hypothesis.

---

Challenge 3 - Stochastic Volatility & Jumps

The third problem is that the non-stationarity of volatility can cause certain returns to appear more or less frequently than they theoretically should. This problem is commonly called "fat tails" and manifests itself because of either stochastic volatility or discontinuities (jumps) in market returns. However, if we assume that the noise present in market returns is centred around zero, then we can show that regardless of jumps and stochastic volatility by binarizing the market returns we remove this problem all-together - see the next section.

---

So what do these challenges mean for researchers wishing to refute the random walk hypothesis using compression-based tests of randomness? It just means that we need to think about our methodology carefully.

---

Proposed Compression Test for Market Randomness

Academics have applied lossless compression algorithms to market returns in order to test or rank their efficiency for many years now. At the end of this section you will find links to relevant papers which take this approach.

Most of the papers concluded that developed markets exhibit high levels of efficiency whereas some developing markets exhibit excess compressibility and, therefore, some degree of inefficiency. Such inefficiencies can only be explained by specific return patterns having higher-than-expected probabilities through time.

---

Our testing methodology

The following testing methodology is followed for three well-known compression algorithms: {gzip, bzip2, and xz}, on a set of developed and developing market indices, and foreign exchange rates.

1. Download the market index prices from Quandl.com.
2. Compute the logarithmic returns of the index and denote them as .
3. Compute the mean logarithmic return (drift component), .
4. De-trend by subtracting (drift) from .
5. Binarize  by replacing >0 returns with 1's and <0 returns with 0's.
6. Split  into overlapping discrete windows, , of 7 years each (+-450 data points).
7. Convert each window, , into hexadecimal (4-day sub-sequences), .
8. Compress each , , and compute the compression ratio,
9. Return the average compression ratio over all windows, .
10. Compute the expected compression ratio using pseudo-random data, .
11. If : market exhibits no excess compressibility which implies efficiency.
12. If : market exhibits some excess compressibility which implies inefficiency.

The test proposed above is similar to those used in the literature - we use binarized returns and multiple lossless compression algorithms - but also dissimilar in some important ways - we de-trend market returns to remove the influence of drift and we compute the average compressibility using a walk-forward methodology.

---

Our test in R

Very little R code was required to construct this test 🙂 due to the memCompress and memDecompress functions which exist in R. Similar Python functions, encode and decode, exist for readers who favour Python.

---

Some relevant academic papers:

1. Shmilovici, Armin, Yael Alon-Brimer, and Shmuel Hauser. "Using a stochastic complexity measure to check the efficient market hypothesis." Computational Economics 22.2-3 (2003): 273-284.
2. Giglio, Ricardo, Raul Matsushita, and Sergio Da Silva. "The relative efficiency of stockmarkets." Economics Bulletin 7.6 (2008): 1-12.
3. Risso, Wiston Adrián. "The informational efficiency: the emerging markets versus the developed markets." Applied Economics Letters 16.5 (2009): 485-487.
4. Shmilovici, Armin, et al. "Measuring the efficiency of the intraday forex market with a universal data compression algorithm." Computational Economics 33.2 (2009): 131-154.
5. Giglio, Ricardo, et al. "Algorithmic complexity theory and the relative efficiency of financial markets." EPL (Europhysics Letters) 84.4 (2008): 48005.

 

---

Overview of Lossless Compression Algorithms in R

A detailed discussion of each of the lossless compression algorithms available to R's memCompress and memDecompress functions is beyond the scope of this article. Below you will find a very brief summary of the three compression schemes used as well as references to their underlying compression algorithms.

---

gzip compression

gzip is based on the DEFLATE algorithm, which combines LZ1 and Huffman coding. The LZ1 algorithm, named after Abraham Lempel and Jacob Ziv, works by replacing repeated patterns in the sequence with references to a copy of that pattern from earlier in the uncompressed sequence. Each match is encoded using a length-distance pair which tells the decoder that: the next y characters is equal to the characters x distance characters behind it. The Huffman Coding algorithm, named after David Huffman, works by constructing an optimal prefix tree given the occurrences of patterns in the sequence. For a great visualization of this checkout this YouTube video.

---

bzip2 compression

bzip2 uses three mechanisms in its compression: the Burrows-Wheeler Transform, the Move-to-Front Transform, and then Huffman Coding. The Burrows-Wheeler Transformation is a reversible method for rearranging the sequence into runs of similar characters so that it can be more easily compressed by Run-Length-Encoding schemes or Move-to-Front encoding. Move-to-front transformations work as follows: letters in the sequence are replaced with their indices in a stack containing the most recently observed letters. As such, long sequences of identical letters are replaced by smaller integers whereas infrequent letters are replaced with larger integers. Lastly the transformed data is fed through the Huffman Coding algorithm as with the DEFLATE algorithm.

---

xz compression

xz implements the (very cool sounding) Lempel–Ziv–Markov chain algorithm (LZMA) which was developed in the 7z compression format. LZMA is a dictionary compression algorithm derived from the LZ1 algorithm. It's output is encoded using a model which makes a probability prediction of each bit, called an adaptive binary range coder. 

---

All of these algorithms are available natively in R via the memCompress and memDecompress functions. The biggest challenge in using these functions (at least for our purposes) was that the input needs to be given as a raw hexadecimal sequence. Converting daily, binarized returns into hexadecimal sequences is done by the function bin2rawhex. Essentially what this does is break our daily returns sequence into discrete, non-overlapping, four-day, sub-sequences which can then be converted directly into hexadecimal. It's not ideal, but it seems to work.

---

Results obtained and their meaning(lessness)?

For this article we ran our compression test on 51 global stock market indices from developed and developing markets and 12 liquid currency pairs. These sequences were tested on both a weekly and daily frequency.

The exact breakdown of tested assets is given below:

All of these assets were compressed using gzip, bzip2, and xz lossless compression algorithms within the walk-forward averaging methodology explained earlier and, for once, the results are really easy to communicate ...

With the exception of the US Dollar to Russian Ruble foreign exchange rate, none of the assets demonstrated excess compressibility. In fact, none of the assets demonstrated any compressibility whatsoever.

Our results with gzip, bzip2, and xz - sophisticated compression algorithms - confirm our negative result obtained in Hacking The Random Walk Hypothesis with the linear complexity test. But they contradict our results obtained with NIST tests and our results obtained with Lo and MacKinlay's Heteroskedastic Variance Ratio Test. Why?

Since I was unsatisfied with the results I decided to dig a bit deeper and develop a test for the compression test ... and what I found was really, really interesting ;-).

---

Testing the compression test

People who refute the random walk hypothesis, like me, are not arguing that markets are 100% deterministic; we are arguing that they are not 100% stochastic. In other words, we are arguing that markets have two faces: the signal and the noise. The signal manifests itself in the many hundreds of so-called anomalies: value, momentum, reversion, indexation, etc. and the noise manifests itself as apparent randomness and efficiency. They are two sides of the same coin; both emergent properties of a complex adaptive system of heterogeneous, imperfect agents. We then go one step further and claim that the amount of noise produced by the system does not drown out the signal and that it is, therefore, possible to beat the market by identifying such signals and exploiting them. 

With that in mind I set out to design a simple test of our compression test:

Consider the following toy market:  where

As we increase the size of the standard deviation of the noise component, , we see that the compressibility of the returns begins to degrade. When the standard deviation passes 0.01 the compression test almost-always fails:

Example outputs from our toy market for , , and  look as follows:

According to our compression test all of these toy markets are random or efficient because they could not be compressed using the lossless compression algorithms gzip, bzip2, or xz. I must admit they look quite random too! But remember, they consist of both a signal and a noise so they are definitely not truly random.

Now, for added good measure, consider the following mean-reversion betting strategy / algorithm:

• Inputs: window size, .
• For time, , in time:
  • Compute the cumulative return of the past days excluding day , .
  • If < 0.0: go long 100% the asset (bet the asset goes up)
  • Else: go short 100% the asset (bet the asset goes down)

Below you will find two charts for each of the noise levels. The first chart will show thirty equity curves generated by our simple mean reversion betting strategy and the second chart will show the average toy market return (from above) against the average mean reversion betting strategy return on these markets. 

Now obviously this is a silly / extreme example but it highlights a contradiction:

If a market (even our toy market) is incompressible it "follows" that it is efficient but if it were truly efficient then there could not exist any betting strategy which consistently beats it, such as the above one. 

To resolve this we must accept that because we cannot prove randomness, the sequence is actually not random and our compression test has failed. Why? I think that the test is failing because it is more sensitive to noise than our trading strategy - my simulations indicate that in the case of our toy market the compression test in up to 10x more sensitive to noise than our trading strategy - this may be due to using greedy or lossless compression algorithms. 

The code for running this test of the compression test is shown below.

---

Conclusions and further research efforts

In this article we introduced the concept of using compression as a test for randomness and explained how such tests have been applied to the market to conclude that they are relatively efficient. We then developed a "meta test" for market randomness tests based on greedy lossless compression algorithms which indicates that such tests are highly sensitive to any noise. This may explain why they are contradicted by other randomness tests.

From this article we might want to conclude the following:

1. After de-trending markets exhibit enough noise to make them incompressible using greedy, lossless compression algorithms such as gzip, bzip2, xz, and a linear feedback shift register. 
2. If the sensitivity of the test to noise is greater than our trading strategies robustness in the presence of noise, the negative result does not imply that markets are efficient in the sense that they cannot be beaten.
3. Our toy market shows that the sensitivity of the greedy lossless compression algorithms used to test market efficiency can be as much as 10x more sensitive to noise than a simple betting strategy.
4. As such, some academic literature in support of the efficient market hypothesis presented in this article may inadvertently be applying a too-strict interpretation of non-randomness to market returns.
5. Statistical tests for market randomness vary in terms of their size, power, and sensitivity. Multiple tests should be used in favour of single tests for more statistically significant and robust results.

As I mentioned in the introduction, further research efforts stemming from this article with include a study of lossy compression algorithms most notably, a stacked auto-encoder neural network. We will follow much the same methodology as we did here: look for excess compressibility beyond what would be expected from some finite pseudo-random sequence and then test how sensitive the lossy compression tests are to noise.

If you have any criticisms, counter-arguments, compliments, or suggestions for our upcoming article on lossy compression algorithms I would love to hear them in the comment section below :-). Thanks for reading!

---

Appendix A: All the Source Code

All of the source code required to run this analysis is available in R on GitHub here.