Pricing complexity options

1.1Motivation

We believe it may be of value in finance to have some notions of the complexity of a price path. Agents may want to insure against too complex or too simple price paths for a stock, for example. A very simple or complex path may be a sign that something is going on that the agent is not aware of.

Weather is somewhat periodic, and automatic complexity measures periodicity, to some extent. Hence a complexity option may be used as a weather derivative.

Casino owners may want to ensure that their casinos are truly random, so as to avoid unexpected losses. In general, anyone who makes an assumption of randomness may want to hedge that, as true randomness is not easy to guarantee, or even completely well-defined.

Automatic complexity: between two extremes. Of course, we can insure against certain types of non-randomness in simple ways. We can insure against a dramatic fall of a stock price by selling the stock short. This corresponds to run complexity (Section 3.2). At the other end, one cannot use Kolmogorov complexity(Section 2) as a basis for the security, because Kolmogorov complexity is not computable. The nondeterministic automatic complexity, being both

may be a promising middle ground.

1.2Automatic complexity and the idea of complexity deficiency

Kolmogorov complexity is an important notion that in a way is to complexity as Turing computability is to computability. It is computably approximable, but unfortunately not computable. As a remedy, Shallit and Wang (2001) defined the automatic complexity of a finite binary string x = x ₁ … x _n to be the least number A _D  (x) of states of a deterministic finite automaton M such that x is the only string of length n in the language accepted by M.

Automatix complexity is computable, but it does have a couple of awkward properties that make us want to tweak its definition. First, many of the automata used to witness the complexity have a dead state whose sole purpose is to absorb any irrelevant or unacceptable transitions. Second, some strings x = x ₁ … x _n have a different complexity from their reverse x _n  … x ₁. For instance (Hyde and Kjos-Hanssen 2014; Hyde and Kjos-Hanssen 2015),

We tweak the definition of automatic complexity by introducing nondeterminism.

Definition 1. (Hyde and Kjos-Hanssen (2015)). The nondeterministic automatic complexity A _N  (w) of a word w is the minimum number of states of an NFA M (having no ɛ-transitions) accepting w such that there is only one accepting path in M of length |w|.

Moreover, and most importantly for the present paper, A _N gives rise to a striking instance of the idea of complexity deficiency:

Theorem 2. (Hyde (2013) and Hyde and Kjos-Hanssen (2015)). The nondeterministic automatic complexity A _N  (x) of a string x of length n satisfies

Proof sketch. The proof is essentially contained in Fig. 1, although we must modify the picture slightly if x has even length. □

Definition 3. The nondeterministic automatic complexity deficiency of a string x is defined by

with b (n) as in Theorem 2. Sometimes we write D (x) for D _n  (x).

Experimentally we have found that about half of all strings have D _n  (x) =0 (Hyde and Kjos-Hanssen, 2015). We call such strings complex, and other strings simple, herein.

1.3Option types: Perpetual, American, European

We shall consider the following types of options and their prices.

We have

and

Theorem 4.

Proof. For the first inequality, it suffices to show

for each n. This holds because one possible exercise policy is the static strategy of exercising at time n no matter what.

For the third inequality, there are two cases.

Case 1: supnDn is almost surely finite. Note that D _n is integer-valued, so supnDn will be realized at some finite stage n ₀. Let us call magically prescient the strategy which waits for supnDn to be realized and then exercises the option. By contrast, an exercise policy should be a stopping time, i.e., it should not depend on future outcomes. We see that the payoff from the magically prescient strategy has a higher price than any exercise policy. It follows that V≤𝔼supnDn in this case.

Case 2: ℙ(supnDn=∞)>0. Then 𝔼supnDn=∞ and so we are done. □

Remark 5. In Case of Theorem 4, if ℙ(supnDn=∞)=ɛ>0 then we can even assert that V =∞. Indeed if V< ∞ then we can buy the option, and wait for D _n  > V/ɛ + 1. The expected payoff is at least

which would create an arbitrage.

We shall consider several complexity notions:

For each notion we first define one or more suitable deficiency notions D _n  (x): for instance, D _n  (x) = n + c _C  - C (x) for a suitable constant c _C for C, and D _n  (x) = ⌊ n/2 ⌋ +1 - A _N  (x) for A _N . The following questions are natural for each of these deficiency notions:

2.1Plain complexity C

Let c _C be the least constant c _C such that C (x ∣ n) ≤ n + c _C for all strings x of any length n. If we define D _n  (x) = n + c _C  - C (x ∣ n) for x of length n, then D _n  (x) ≥0 for all x, and D _n  (x) =0 does occur. This is theoretically pleasant. Deficiencies are nonnegative and can be zero. Of course, c _C depends on the version of the plain length-conditional Kolmogorov complexity C (· ∣ ·) that we use. In this setting, we have

Theorem 6. supn𝔼Dn<∞.

Proof. Fix n. For any a, there are only 2 ^a  - 1 binary strings of length at most a. All descriptions witnessing complexity (given n) being at most a must be among them, so at most 2 ^a  - 1 many strings have complexity (given n) of at most a. Applying this to a = n + c _C  - k, at most 2 ^{n+c _C -k}  - 1 strings x (in particular, at most that many strings of length n) satisfy D _n  (x) ≥ k. That is, by Downey and Hirschfeldt (2010, Corollary 6.1.4),

Then we have

It turns out that for options expiring at time n, there is a significantly better exercise policy than the static strategy of waiting until the very end:

Theorem 7. For plain Kolmogorov complexity, supnVn=∞, even if we require efficient computation of the exercise policy.

The idea of the proof is to use complexity oscillations, first observed by Martin-Löf (1971): when the initial part of a string x is a binary encoding of the length of x, the plain Kolmogorov complexity of x will be low.

Proof. Martin-Löf (1971) showed that deficiency is unbounded for all reals: for each X and b there is an n with D (X ↾ n) > b. We can computably identify such an n. The well known idea is that we take a prefix X ↾ m; consider it as a binary representation of a length ℓ<2 ^m ; and then consider σ = X↾ ℓ. Since the beginning of σ is known just from the length of σ, σ is compressible. This translates into an exercise policy for our option: at time m we decide on the time ℓ at which we are going to exercise. The strategy just described is efficient, since we decide at time m⪡ ℓ to exercise at time ℓ. □

Remark 8. Since C (x ∣ n) ≤ ⁺ C (x), Theorem 7 holds equally for length-conditional plain Kolmogorov complexity, and Theorem 6 also holds if we consider plain Kolmogorov complexity that is not length-conditional.

2.2Prefix-free complexity K with C-style deficiency

Let K denote prefix-free Kolmogorov complexity. With D _n  (x) = n - K (x), there is no limiting deficiency distribution in this case (or one could say the deficiency is in the limit -∞ almost surely). That is, K (w) ≥ |w| - c for almost all w, for any c. Indeed, for each c∈ℤ,

as is easily shown using ∑ _σ 2^-K(σ) < 1. If the lim sup of the complement is δ > 0, then for each ɛ > 0 there exist N _k with

Theorem 9. For prefix-free Kolmogorov complexity the price of the perpetual option that pays D _n  - a is at most 2^-a .

Proof. We have

Let Dn+=max{Dn-a,0}. Since we would not exercise an option giving negative payoff, it follows that

2.3Prefix-free complexity K with its natural notion of deficiency

Theorem 10. (Deficiency based on an upper bound for K) If we fix a constant c _K such that for prefix-freeKolmogorov complexity K, K (x) ≤ n + K (n) + c _K for all x of any length n, and let D _n  (x) = n + K (n) + c _K  - K (x) ≥0, then 𝔼Dn is bounded but V _n → ∞.

Proof. The same proof as for Theorem 6 but using an analogous property shows that 𝔼Dn is bounded. In this case, however, sup D _n  (X ↾ n) will be ∞ for almost all X ∈ 2 ^ω . In fact Li and Vitányi showed D _n  (X ↾ n) > log n for infinitely many n for almost all X.

Solovay showed that lim inf D _n  (X ↾ n) will be finite (Miller and Yu, 2011).

V =∞ in this case since we can simply wait for a sufficiently high D _n value. What about V _n ? Consider an arbitrary constant, which for expository vividness we will take to equal 17. Almost surely there will be an n with D _n  (X ↾ n) ≥17. Therefore for each ɛ there is an n ₀ such that

and so V _{n 0}  ≥ 17 (1 - ɛ). Moreover V _n  ≤ V _n+1 for American options. So V _n → ∞ in this case. The exercise policy would be to wait for D _n  = 17 to occur and then exercise. □

An overview of the deficiency option prices is given in Table 1.

Remark 11. Of course, one does not need to only consider deficiencies. One could consider an option paying out K (x) - n. This value will go to infinity, but how fast? What is our exercise policy if we are not given access to K? Another possibility is to consider dips in complexity associated with the Kolmogorov structure function (N. K. Vereshchagin and Vitányi 2004) and its automatic complexity variant (Kjos-Hanssen, 2016).

2.4Using runs

Remark 12. An anonymous referee suggested the following approach to obtaining results of the form V _n → ∞. Let R _n be the longest run of 0s in a string of length n and let 𝔼 and Var denote expectation and variance with respect to the uniform distribution on {0, 1}  ⁿ . Now, if U is a universal prefix-free machine, we can define another machine M by the following algorithm: on input x ^*, simulate U, and if U (x ^*) = x, then

for a fixed constant c. The domain of M equals the domain of U, hence M is also a prefix-free machine. Thus Let now m = |f (x) = |x + ⌊ log ₂|x ⌋ - c and y = f (x). Since K (n) ≤ ⁺ K (m) by the choice of m, we have and Now we employ the trading strategy whereby we wait until our input is of the form x 0^log₂|x-c |, and then exercise. By Theorem ?? below, |𝔼(Rn)-log2n| and Var (R _n ) are both bounded by a constant c. By the argument in Section 3.2 below, with high probability we will be able to exercise. Thus for American options, with payoff D _n  (x) either n + K (n) + c _K  - K (x) or c _C  - C (x), we obtain V _n → ∞.

Theorem 13. (Boyd (1972)) Let R _n be the longest run of heads in a binary sequence of length n distributed according to the Bernoulli distribution with parameter 1/2. Let log = ln. Then

where ɛ ₁ (α) is a function of period 1 which satisfies |ɛ ₁ (α) |<2 × 10^-6 for all α, and r ₁ (n) = O (n ^-1 (log n) ⁴) →0. Moreover, where ɛ ₂ (α) has period 1, and |ɛ ₂ (α) |<10^-4 for all α.

3.1Automatic complexity

Now the goal is to price the European/American option that pays the nondeterministic automatic complexity deficiency D _n of the movements of a stock from time 0 to the time n when the option is exercised. We suspect that finding the exact price is a computationally intractable problem, both because of the conjectured intractability of computing automatic complexity (Hyde and Kjos-Hanssen 2015), and because of the exponential number of price paths to consider.

The interest rate r can be set to 0 or to a positive value. For pedagogical reasons, Shreve (2004) uses r = 1/4 for his main recurring example, and we sometimes adopt that value as well.

In general when the risk-neutral probabilities are 1/2 each for up and down, then the value of the option is directly related to the distribution of the deficiency D _n : If D _n happened to be Poisson for large n, this is approximately λ (1 + r) ^-n , which is decreasing in n. However, we have just seen that the value for n = 2 is higher than for n = 0 and n = 1.

Remark 14. For an American version, one question is whether to exercise the option at time n = 2 after having seen 00. If we exercise we get $1. Otherwise the deficiency can at most go up by 1 each time step, whereas the interest factor with r = 1/4 > 0 is exponential, so an upper bound for our payoff is

indent This expression is maximized at n = 4 and at n = 5. Both places it takes the value 0.8192.

To obtain a reasonable level of abstraction it is valuable to consider infinite price paths and associate a finite complexity deficiency with them. We can do so if the nondeterministic automatic complexity deficiencies of prefixes of an infinite binary sequence are almost surely bounded (Conjecture 3.1; see also Table 1).

Conjecture 15. For nondeterministic automaticcomplexity A _N ,

Remark 16. Pakravan and Saadat (2013) studied a perpetual American option that pays the complexity deficiency of the sequence of up and down ticks (considered as 1s and 0s) upon exercise. With interest rate set to zero (r = 0) the price of this security may be infinity, based on tentative numerical evidence. That is, for A _N ,

although 𝔼Dn seems to approach a finite limit (see Table 2). For positive interest rates the price is finite (see Remark 4). They found numerical evidence that for r = 1/4 the price is 0.47. See Fig. 2 for the deficiencies of strings of length at most 4, and Fig. 3 for corresponding calculated option prices. The price of the American option with expiry 2k and expiry 2k + 1 are the same, as is easy to prove.

Definition 17. Let V ⁽ⁿ⁾ be the price of the European option paying the nondeterministic automatic complexity deficiency D (x) for the price path x oflength n.

Decision problem: PRICE.

Instance: A pair of nonnegative integers n and k with

Question: Is V ⁽ⁿ⁾ ≥ k/2 ⁿ ?

Recall that E is the class of single-exponential time decidable decision problems.

Theorem 18. PRICE is in E.

Proof. Hyde and Kjos-Hanssen (2015) considered the problem DEFICIENCY of deciding whether, given an integer k and a sequence x, the nondeterministicautomatic complexity deficiency D (x) satisfies D (x) ≥ k. They showed that DEFICIENCY is in E. Since there are only single-exponentially many price paths of length n, the usual backwards recursive algorithm for option pricing in the binomial model (Shreve, 2004) gives the theorem. □

The same proof shows that the analogous statement to Theorem 18 for American options holds as well.

3.2Run complexity

If the payoff of our option is just the longest run of heads then Alikhani (2014) showed that the price of the option is Θ (log ₂ n). This corresponds to automata that always proceed to a fresh state, except that one state may be repeated (namely, the state of the longest run).

Definition 19. The run complexity C _R of a binary sequence x is defined by C _R  (x) = n + 1 - r, where n is the length of x and r is the length of the longest run of 0s or 1s in x.

This complexity notion has the advantage that it is efficiently computable. Kjos-Hanssen (2014) studied it in more detail and also considered multiple runs, as in the Wald–Wolfowitz runs test.

In the rest of this subsection we give the argument of Alikhani (2014). We assume familiarity with basic discrete options (Shreve, 2004). A coin tossing sequence is ω ₁ … ω _N where each ω _i  ∈ {H, T}. (Read H as “heads” and T as “tails”.)

Definition 20. For each 0 ≤ n ≤ N, the current run of heads in the coin tossing sequence ω ₁ … ω _n is defined by

The run option is the American option where thepayoff when exercised at time n ≤ N is G _n  (ω). Let V ^A be the price of the run option. Define a stopping time τ _t by where R _N is the longest run of heads in a coin tossing sequence of length N.

Thus, the trading strategy corresponding to τ _t is to wait for a run of heads that is almost as long as we ever expect to see before time N, with “almost” being qualified and measured by the parameter t.

Definition 21. Let [x] denote the nearest integer of x. In particular, [x] is an integer k with k - 1 ≤ x ≤ k + 1.

Theorem 22. Given N there is a deterministic choice of t = t _N such that there is a sequence of numbers ɛ _N with limN→+∞ɛN=0, and constants c ₂ and c, such that for large N,

Proof. The price process VnA for the run option satisfies the American risk-neutral formula

So for each t, Now we find a lower bound on 𝔼(Gτt). By Theorem 13, for large N. Let 𝔼(RN)=a; then we get Now we find the t = t _N such that the right-hand side of (*) is maximized. The corresponding third degree polynomial has negative discriminant. Therefore it has one real root, which was calculated by Mathematica: By the second derivative test, since we see that t maximizes the right-hand side of (*). We have and hence Therefore, t=tN∈Θ(lnN3) and so □

Corollary 23. V ^A  ∼ log ₂ N.

Proof. V ^A is bounded below by the expected payoff of the strategy that waits for [E (R _N )] - t _N heads, with t _N as in Theorem 22, and then exercises. On the other hand, V ^A is bounded above 𝔼(RN). Therefore

By Theorem 13, and so by Theorem 22, Dividing by log ₂ N we get □