Estimating the algorithmic complexity of stock markets

1.1Probabilistic versus algorithmic randomness

Traditionally, financial price motions were modeled (and are still modeled) as random walks⁴ (see equation 1):

In this equation, p _t stands for the price of one specific security at “t” and ɛ _t is a stochastic term drawn from a certain distribution law⁵. This stochastic term is often estimated by a Gaussian noise, though it fails to correctly represent some stylized facts such as the time dependence in absolute returns or the auto-correlation in volatility (see for example Mandelbrot & Ness (1968) or Fama (1965)). Several stylized facts are taken into account by volatility models (see, for instance GARCH models⁶, while others stay rarely exploited in financial engineering (for example, multi-scaling laws (Calvet & Fisher 2002), return seasonality ⋯).

In this sense, financial engineering proposes an iterative process which, step by step, improves the quality of financial time series models, both in terms of describing and forecasting⁷. At least from a theoretical point of view, this iterative process should deliver, at the end, a perfectly deterministic model⁸. If this final stage symbolizes the perfect comprehension of price dynamics, each step in this direction can be considered as a progress of our knowledge on financial time series. With an imperfect understanding of this latter, the iterative process will stop somewhere before the determinist model. Meanwhile, wherever we stop in this process, the resulting statistical model is a “compressed expression” (some symbols and parameters) of the long financial time series (hundreds or thousands of observations).

“To understand is to compress” is actually the main idea in Kolmogorov complexity (Kolmogorov 1965) whose definition is formally introduced as follows:

Definition 1.1. Let s denote a finite binary string consisting of digits from {0, 1}. Its Kolmogorov complexity K (s) is the length of the shortest program P generating (or printing) s. Here, the length of P depends on its binary expression in a so-called “universal language”⁹.

As a general indicator of randomness, Kolmogorov complexity of a given string should be relatively stable to the choice of universal language. This stability is shown in the following theorem (see (Kolmogorov 1965) or (Li & Vitányi 1997) for a complete proof) according to which, a change in the universal language has always a bounded impact on a string’s Kolmogorov complexity.

Theorem 1.2. Let K _{L 1}  (s) and K _{L 2}  (s) denote the Kolmogorov complexities of a string s respectively measured in two different universal languages L ₁ and L ₂. The difference between K _{L 1}  (s) and K _{L 2}  (s) is always a constant c which is completely independent of s:

According to this invariance theorem, one need not pay too much attention to the choice of universal language in Kolmogorov complexity estimations, since its intrinsic value (the part depending on s) remains stable with regard to programming technics in use.

Besides the invariance theorem, another property of Kolmogorov complexity, firstly proved in(Kolmogorov 1965), makes it a good randomness measure: a finite string’s Kolmogorov complexity always takes a finite value.

Theorem 1.3. If s is a sequence of length n then:

In equation 3, O (log (n)) only depends on the universal language in use. This property comes from the fact that all finite strings can at least be generated by the program, “print (s)”, whose length is close to the size of s.

Remark that most n-digit strings (provided that n is big enough) have their Kolmogorov complexity K (s) close to n. K (s) << n implies the existence of a program P which can generate s and is much shorter than s. In this case, P is said to have found a structural regularity in s, or P has compressed s.

On the contrary,

Definition 1.4. If for an infinite binary string denoted by S:

where S ↾ n denotes the first n digits of S and C a constant in the natural number set ℕ, then S is defined to be a “random string”.

This definition of random strings, proposed by Martin-Löf (1966), reformulated by Chaitin (1987) and reviewed in Downey & Hirschfeldt (2010), is irrelevant to any probability notion, and only depends on structural properties of S.

Following definition 1.4, the best compression rate one can get from the n first digits of a random string is calculated by

As n→ ∞, rate → 0. In other terms, random strings are incompressible ones.

Contra-intuitively, compressible strings are relatively seldom. For example¹⁰, among all n-digit strings, the proportion of those verifying K (s) < n - 10 does not exceed 1/1000.

To illustrate the relation between compressibility and regularity, let’s consider two compressible (regular) strings:

The first string, known as Champernowne sequence (i.e. string C on page 159), is generated with a quite simple arithmetic rule: it is the juxtaposition of natural numbers written in base 2. The optimal compression rate on the first million digits of is above 99% (c.f. annex B), which indicates that can be printed by a short program.

The second string was independently drawn from a random law (with the help of a physical procedure) delivering “1″ with a 2/3 probability and “0″ with a 1/3 probability. The computer program generating b can be much shorter than it. In fact, classical tools can obtain on b a compression rate calculated as follows¹¹:

While b is drawn from a random law, its compressibility remains perfectly compatible with statistical conjectures: composed by definitively more 1 than 0, b should not be considered as the path of a standard random walk.

Face to rare events, algorithmic and statistical approaches also deliver similar conclusions. Let c denote a 100-digit string exclusively composed of 0. To deduce whether c was generated by tossing a coin, one can make 2 kinds of conjectures:

However, despite the two preceding arguments, c could always have been generated by tossing a coin, since even with a zero probability, rare events do take place. This phenomenon is often referred to as “black swans” by financial practitioners.

In this section, Kolmogorov complexity is presented by comparing it with the statistical framework in regard to randomness consideration. Two properties - invariance theorem and boundedness theorem - of the former concept are stressed in this theoretical introduction since they allow Kolmogorov complexity to be a good indicator of the distance between a given sequence and random ones.

Based on this theoretical development, we will show in the following sections how Kolmogorov complexity can be used in empirical data analysis.

1.2Kolmogorov complexity of price series: a basic example

After the theoretical introduction of Kolmogorov complexity, we illustrate with the following example how to search structural regularities in certain sequences behind their complex appearance. This example is developed with a simulated price series which is plotted in Figure 1.

The first 14 values of the simulated series are:

One apparent regularity in e _1,t is that all prices seem to be concentrated around 1000. One can “erase” this regularity on taking the first order difference of e _1,t with equation: e _2,t  = p _t  - p _t-1. This process delivers the following sequence:

As positive series can be transformed into base 2 more easily, each element of e _2,t is added by 32, which gives:

Then, e _3,t is coded with binary numbers of 6 bits:

Without commas, e _4,t becomes:

Is e ₅ compressible? In other terms, will there remain structures in e ₅ after the preceding transformations? Before answering these questions, one must notice that the binary expression of e ₂ is already shorter than that of e ₁. Our first transformation actually corresponds to a first compression by exploiting the sequential, concentrated aspect of e ₁ ¹³.

Were e ₅ incompressible, our “regularity erasing procedure” (thereafter, REP) would have attained its final stage. However, it is not the case. In e ₅, there remains another structure which can be described as follows: if the (2n - 1) th term is 1 (resp. 0), so will be the (2n) th term. By exploiting this regularity, e ₅ can be compressed to e ₆ which only carries every second element of e ₅:

At this step of REP, have we got an incompressible (random) string? Once again, this is not the case. e ₆ is actually produced by a pseudo-random generator which theoretically, can be reduced to its seed! Thus, e ₅ is compressible in principle. However, it should be admitted that this ultimate compression is almost infeasible in practice, given the available range of compression tools.

This basic example highlights how three important regularities¹⁴ can hide behind the rather complex appearance of e _1,t , and how these structures can be revealed by a mere deterministic procedure.

In the next sections, with the help of classical compression algorithms¹⁵, we show how REP can be implemented on both simulated (c.f. Section 3) and real-world financial time series (c.f. Section 3).In particular, we highlight that REP can be used to discover regularities actually undetectable by most statistical tests.

2.1The lossless discretization principle

In this section, we propose a generic methodology to estimate Kolmogorov complexity of a logarithmic price series¹⁶, as what one can observe in real-world financial markets. As mentioned in Section 1.2, a first “compression” consists of transforming the logarithmic price sequence into returns. This operation, familiar to financial researchers, actually delivers unnecessarily precise data: for example, no one would be interested by the 18th decimal place of a financial return. Thus, without sensitive information loss, one can transform real number series into integer ones by associating to each integer a certain range of real returns.

We also posit that integers used for discretization belong to a subset of ℕ whose length is arbitrarily fixed to be powers of 2. The total number of integers should be powers of 2, since this allows to re-code the discretization result in base 2 without bias¹⁷. Once written in binary base, financial returns become a sequence consisting of 0 and 1, which is perfectly suitable for compression tools.

After presenting the main idea of discretization, three points must be discussed concerning this latter procedure:

2.2REP: an incremental procedure for pattern detection

As shown in Section 1.1, a generic methodology to capture financial dynamics requires to identify the underlying random process structuring ɛ _t (for example, i.i.d. Gaussian random innovations).

On introducing Kolmogorov complexity in finance, we want to consider whether it is possible or not to find, besides the well-documented stylized facts, other structures more subtly hidden in financial returns. In other terms, we try to find new and fainter regularities at the presence of more apparent ones.

If one uses compression methods on return series directly, algorithms would only catch the “main structures” in the data, and could potentially overlook weaker (but existing) patterns.

To expose these latters, we suggest an iterative process that, step by step, erases the most evident structures from the data. Resulting series are subject to compression tests for unknown structures. Due to this process, even if financial returns witness obvious patterns such as stylized facts, compression algorithms can always concentrate on unknown structures, since once erased, identified patterns would no longer be mixed with unknown structures, and any further compression could be related to the presence of new patterns.

To interpret the compression results from REP, we distinguish 3 situations:

Actually, given a finite time series, it is just impossible to attest wether it is a regular or random one with certainty. At least two arguments support this point:

So, compression tools only estimate Kolmogorov complexity, none of them should be considered as an ultimate solution that will detect all possible regularities in a finite sequence. This conclusion is closely related to the Gödel undecidability.

In this sense, compression algorithms share the same shortfall with statistical tests: both approaches are inept to deliver certain statements. Nevertheless, as statistical tests are making undeniable contributions to financial studies, compression algorithms can also be a powerful tool for pattern detection in return series.

To illustrate this point, we will compare algorithmic and statistical methods in the next section with regard to structure detection in numeric series.

3.1Illustration 1: Incompressible randomness

In this section, we simulate a series of 32000 i . i . d . N (0, 1) returns with the statistical language “R”, and examine the simulated data with statistical tests and compression algorithms respectively. We show that compression algorithms cannot compress random strings, and sometimes they even increase the length of the initial data.

The simulated series is quite similar to “consecutive financial returns” and can be used to generate an artificial “price sequence”. Figure 2 gives a general description of the data.

Statistical tests do not detect any specific structure in the normally distributed series, as we can witness in Tables 1, 2 and 3.

To check the performance of the algorithmic approach, we implement compression tools on the simulated data. As explained in the last section, before using compression algorithms, we should firstly transform the simulated real-number returns into integers (discretization). In other terms, we must associate to each return an integer ranging from 0 to 255, with “0” and “255” corresponding to the lower and upper bounds of the simulated data respectively. Here, instead of a “one to one” correspondence, each integer from 0 to 255 must represent a range of real numbers. The size of the interval associated to each integer (denoted by e) is fixed as follows:

where M and m represent the upper and lower bounds of the simulated returns.

Provided the value of e, we can divide the whole range [m, M] into 256 intervals, and associate, to each return (denoted by x), an integer k satisfying:

In other terms, after sorting the 256 “e-sized” intervals in ascending order, k is the rank of the one containing x. As k varies from 0 to 255, it should be coded with 8 bits, since 2⁸ = 256. Here, by dividing the real set [m, M] into 256 identical subsets, we will obtain a series of regular bounds on X-axis under the standard normal distribution curve, as represented by Fig. 3(a).

Using this discretization method, we obtain normally distributed integers: values close to 128 are much more frequent than those close to 0 or 255. An efficient compression algorithm will detect this regularity and compress the discretized data.

However, this normal-law-based compression is of little interest for financial return analysis. According to REP, the normal distribution should be erased from the simulated data in order to expose more sequential structures.

To do this, we propose a second discretization process that will deliver uniformly distributed integers, instead of normally distributed ones.

In this second process, the main idea stays the same: real number returns can be discretized in dividing the whole interval [m, M] into 256 subsets²², and then in associating to each return x the rank of the subset containing x.

However, this time, instead of getting equal-size subsets, we will fix the separating bounds in such a way that probability surface of the normal distribution would be divided into equal parts (c.f. Fig. 3(b)). To be more precise, we want to define 257 real-number bounds, denoted by flag (0) , flag (2) , . . . , flag (256), to make sure that each value draw from N (0, 1) has the same probability (1/256) to fall in each interval [flag (i) , flag (i + 1)]. Subsets defined like this don’t have the same size: as illustrated in Fig. 3(b), the more a subset is close to zero, the smaller it becomes.

The discretization process described in Fig. 3(b) is implemented to simulated returns. Discretized returns are presented in Fig 9. The ith point in this figure represents the integer associated to the ith return. One can notice that the plot of the discretized returns is relatively homogeneous without any particularly dense or sparse area (see Figure in appendix D).²³ This rapid visual examination confirms the uniform distribution of discretized returns.

When lossless compression algorithms are used on the ascii text obtained from the uniformly discretized returns (c.f. Fig. 10 in appendix D), these algorithmic tools turn out to be inefficient (c.f. Table 4).

This example clearly shows that normally distributed returns can be transformed into an uniformly distributed integer string whose length is entirely irreducible by lossless compression tools. We can conjecture from this experiment, that the initial series has a Kolmogorov complexity close to its length.

With data simulated from the standard normal law, we show that statistical and algorithmic methods deliver the same conclusion on random strings.

In a further comparison between the 2 approaches, we will “hide” some structures in an uniformly distributed sequence, and show that the hidden regularity is detectable by compression algorithms but not by statistical tests.

3.2Illustration 2: Statistically undetectable structures and compression algorithms

In this section, we make a further comparison between statistical and algorithmic methods with simulated series. More precisely, instead of random strings, we generate structured data to check the power of these two methods in pattern detection.

A return series can carry many types of structures. Some of them are easily detectable by standard statistical tests (for example, auto-regressive process or conditional variance process). However, to distinguish compression algorithms from statistical tests, this kind of regularities will not be the best choice. Here, we want to build statistically undetectable regularities that can be revealed by compression tools.

In this purpose, the return series is simulated as follows:

So, by construction, chron is a normally distributed series that will exhibit patterns after discretization. Are these structures detectable by both statistical and algorithmic methods? Or only one of these approaches can reveal the hidden regularities? That’s what we want to see with the following tests.

Simulated returns are plotted in Fig. 4, with Fig. 4(a) corresponding to case 1, and Fig. 4(b) to case 2.

As shown in Tables 5, 6 and 7, statistical tests detect no structure in chron.

After statistical tests, the REP is applied to chron. From a theoretical point of view, regularity hidden in case 1 implies a compression rate of 12.5%. This rate is calculated as follows: each integer in the discretized chron (which is actually text′) is coded with 8 bits, while only 7 of them are necessary. Actually, given the “parity alternation”, the last digit of each byte in text′ is determinist. In other terms, we can save 1 bit on every byte. Whence the theoretical compression rate 1/8 =12.5%. Following the same principle, we can calculate the theoretical compression rate in case 2: 3/8 =37.5%.

Table 8 presents compression results in the 2 cases. Notice that realized compression rates are close to theoretical ones, but they never attain their exact value. Among the three algorithms in use, Paq8o8 offers the best estimator of theoretical rates.

In this illustration, we show that the algorithmic approach, essentially based on Kolmogorov complexity, can sometimes identify statistically-undetectable structures in simulated data.

However, as mentioned in the theoretical part, the ultimate algorithm calculating the true Kolmogorov complexity for all binary strings does not exist. Compression tools also have practical limits. In other terms, certain structures are undetectable by available compression tools. We show this point in the next section.

3.3Practical limits of the algorithmic method: decimal digits of π

Besides the Euler numbers and the Fibonacci numbers, π is perhaps one of the most studied mathematic numbers. There are many methods to calculate π. The following two equations both deliver a big number of its decimal digits:

π can be transformed into a return series in 3 steps:

As exposed in Table 9, π-based return series is incompressible after discretization, since to our knowledge, no compression algorithm exploits decimalsof π.

The π-based simulation is another example that shows the possibility to hide patterns behind a random appearance. It also witnesses that some theoretically compressible structures may be overlooked by available compression tools. These structures are perfectly compressible in theory, but not in practice yet.

To check the performance of statistical tools on decimals of π, we conducted the same tests as in the preceding illustrations. We notice in Tables 10, 11 and 12, that statistical tests do nothing better than compression tools: none of them can reject H ₀ which implies the absence of regularity.

In this section, simulated data are used to illustrate the performance of compression tools in pattern detection. Two main results are supported by these illustrations: (1) Some statistically undetectable patterns can be traced by compression tools. (2) Certain structures stay undetectable by currently available compression tools.

In the next section, we test the algorithmic approach with real-world financial return series.