String’s Depth of Burial

A string’s depth might be defined as the execution time of its minimal program.

The difficulty with this definition arises in cases where the minimal program is only a few bits smaller than some much faster program, such as a print program, to compute the same output x. In this case, slight changes in x may induce arbitrarily large changes in the run time of the minimal program, by changing which of the two competing programs is minimal. Analogous instability manifests itself in translating programs from one universal machine to another. This instability emphasizes the essential role of the quantity of buried redundancy, not as a measure of depth, but as a certifier of depth. In terms of the philosophy-of-science metaphor, an object whose minimal program is only a few bits smaller than its print program is like an observation that points to a nontrivial hypothesis, but with only a low level of statistical confidence.

To adequately characterize a finite string’s depth one must therefore consider the amount of buried redundancy as well as the depth of its burial. A string’s depth at significance level s might thus be defined as that amount of time complexity which is attested by s bits worth of buried redundancy. This characterization of depth may be formalized in several ways.

A string’s depth at significance level s be defined as the time required to compute the string by a program no more than s bits larger than the minimal program.

This definition solves the stability problem, but is unsatisfactory in the way it treats multiple programs of the same length. Intuitively, 2^k distinct (n + k)-bit programs that compute same output ought to be accorded the same weight as one n-bit program; but, by the present definition, they would be given no more weight than one (n + k)-bit program.

A string’s depth at signicifcance level s depth might be defined as the time t required for the string’s time-bounded algorithmic probability P_t(x) to rise to within a factor 2^−s of its asymptotic time-unbounded value P(x).

This formalizes the notion that for the string to have originated by an effective process of t steps or fewer is less plausible than for the first s tosses of a fair coin all to come up heads.

It is not known whether there exist strings that are deep, in other words, strings having no small fast programs, even though they have enough large fast programs to contribute a significant fraction of their algorithmic probability. Such strings might be called deterministically deep but probabilistically shallow, because their chance of being produced quickly in a probabilistic computation (e.g. one where the input bits of U are supplied by coin tossing) is significant compared to their chance of being produced slowly. The question of whether such strings exist is probably hard to answer because it does not relativize uniformly. Deterministic and probabilistic depths are not very different relative to a random coin-toss oracle A of the equality of random-oracle-relativized deterministic and probabilistic polynomial time complexity classes; but they can be very different relative to an oracle B deliberately designed to hide information from deterministic computations (this parallels Hunt’s proof that deterministic and probabilistic polynomial time are unequal relative to such an oracle).

(Depth of Finite Strings): Let x and w be strings and s a significance parameter. A string’s depth at significance level s, denoted D_s(x), will be defined as min{T(p) : (|p|−|p^∗| < s)∧(U(p) = x)}, the least time required to compute it by a s-incompressible program. At any given significance level, a string will be called t-deep if its depth exceeds t, and t-shallow otherwise.

The difference between this definition and the previous one is rather subtle philosophically and not very great quantitatively. Philosophically, when each individual hypothesis for the rapid origin of x is implausible at the 2^−s confidence level, then it requires only that a weighted average of all such hypotheses be implausible.

There exist constants c₁ and c₂ such that for any string x, if programs running in time ≤ t contribute a fraction between 2^−s and 2^−s+1 of the string’s total algorithmic probability, then x has depth at most t at significance level s + c₁ and depth at least t at significance level s − min{H(s), H(t)} − c².

Proof : The first part follows easily from the fact that any k-compressible self-delimiting program p is associated with a unique, k − O(1) bits shorter, program of the form “execute the result of executing p∗”. Therefore there exists a constant c₁ such that if all t-fast programs for x were s + c₁– compressible, the associated shorter programs would contribute more than the total algorithmic probability of x. The second part follows because, roughly, if fast programs contribute only a small fraction of the algorithmic probability of x, then the property of being a fast program for x is so unusual that no program having that property can be random. More precisely, the t-fast programs for x constitute a finite prefix set, a superset S of which can be computed by a program of size H(x) + min{H(t), H(s)} + O(1) bits. (Given x∗ and either t∗ or s∗, begin enumerating all self-delimiting programs that compute x, in order of increasing running time, and quit when either the running time exceeds t or the accumulated measure of programs so far enumerated exceeds 2^{−(H(x)−s)}). Therefore there exists a constant c₂ such that, every member of S, and thus every t-fast program for x, is compressible by at least s − min{H(s), H(t)} − O(1) bits.

The ability of universal machines to simulate one another efficiently implies a corresponding degree of machine-independence for depth: for any two efficiently universal machines of the sort considered here, there exists a constant c and a linear polynomial L such that for any t, strings whose (s+c)-significant depth is at least L(t) on one machine will have s-significant depth at least t on the other.

Depth of one string relative to another may be defined analogously, and represents the plausible time required to produce one string, x, from another, w.

(Relative Depth of Finite Strings): For any two strings w and x, the depth of x relative to w at significance level s, denoted D_s(x/w), will be defined as min{T(p, w) : (|p|−|(p/w)∗| < s)∧(U(p, w) = x)}, the least time required to compute x from w by a program that is s-incompressible relative to w.

Depth of a string relative to its length is a particularly useful notion, allowing us, as it were, to consider the triviality or nontriviality of the “content” of a string (i.e. its bit sequence), independent of its “form” (length). For example, although the infinite sequence 000… is intuitively trivial, its initial segment 0ⁿ is deep whenever n is deep. However, 0ⁿ is always shallow relative to n, as is, with high probability, a random string of length n.

In order to adequately represent the intuitive notion of stored mathematical work, it is necessary that depth obey a “slow growth” law, i.e. that fast deterministic processes be unable to transform a shallow object into a deep one, and that fast probabilistic processes be able to do so only with low probability.

(Slow Growth Law): Given any data string x and two significance parameters s₂ > s₁, a random program generated by coin tossing has probability less than 2^{−(s2−s1)+O(1)} of transforming x into an excessively deep output, i.e. one whose s₂-significant depth exceeds the s₁-significant depth of x plus the run time of the transforming program plus O(1). More precisely, there exist positive constants c₁, c₂ such that for all strings x, and all pairs of significance parameters s₂ > s₁, the prefix set {q : D_s2(U(q, x)) > D_s1(x) + T(q, x) + c₁} has measure less than 2^{−(s₂−s₁)+c₂.}

Proof: Let p be a s₁-incompressible program which computes x in time D_s1(x), and let r be the restart prefix mentioned in the definition of the U machine. Let Q be the prefix set {q : D_s2(U(q, x)) > T(q, x) + D_s1(x) + c₁}, where the constant c₁ is sufficient to cover the time overhead of concatenation. For all q ∈ Q, the program rpq by definition computes some deep result U(q, x) in less time than that result’s own s₂-significant depth, and so rpq must be compressible by s₂ bits. The sum of the algorithmic probabilities of strings of the form rpq, where q ∈ Q, is therefore

Σ_q∈Q P(rpq)< Σ_q∈Q 2^{−|rpq| + s₂} = 2^{−|r|−|p|+s2} μ(Q)

On the other hand, since the self-delimiting program p can be recovered from any string of the form rpq (by deleting r and executing the remainder pq until halting occurs, by which time exactly p will have been read), the algorithmic probability of p is at least as great (within a constant factor) as the sum of the algorithmic probabilities of the strings {rpq : q ∈ Q} considered above:

P(p) > μ(Q) · 2^{−|r|−|p|+s2−O(1)}

Recalling the fact that minimal program size is equal within a constant factor to the −log of algorithmic probability, and the s₁-incompressibility of p, we have P(p) < 2^{−(|p|−s1+O(1))}, and therefore finally

μ(Q) < 2^{−(s₂−s₁)+O(1)}, which was to be demonstrated.

Advertisement

Hyperbolic Brownian Sheet, Parabolic and Elliptic Financials. (Didactic 3)

Financial and economic time series are often described to a first degree of approximation as random walks, following the precursory work of Bachelier and Samuelson. A random walk is the mathematical translation of the trajectory followed by a particle subjected to random velocity variations. The analogous physical system described by SPDE’s is a stochastic string. The length along the string is the time-to-maturity and the string configuration (its transverse deformation) gives the value of the forward rate f(t,x) at a given time for each time-to-maturity x. The set of admissible dynamics of the configuration of the string as a function of time depends on the structure of the SPDE. Let us for the time being restrict our attention to SPDE’s in which the highest derivative is second order. This second order derivative has a simple physical interpretation : the string is subjected to a tension, like a piano chord, that tends to bring it back to zero transverse deformation. This tension forces the “coupling” among different times-to-maturity so that the forward rate curve is at least continuous. In principle, the most general formulation would consider SPDE’s with terms of arbitrary derivative orders. However, it is easy to show that the tension term is the dominating restoring force, when present, for deformations of the string (forward rate curve) at long “wavelengths”, i.e. for slow variations along the time-to-maturity axis. Second order SPDE’s are thus generic in the sense of a systematic expansion.

In the framework of second order SPDE’s, we consider hyperbolic, parabolic and elliptic SPDE’s, to characterize the dynamics of the string along two directions : inertia or mass, and viscosity or subjection to drag forces. A string that has “inertia” or, equivalently, “mass” per unit length, along with the tension that keeps it continuous, is characterized by the class of hyperbolic SPDE’s. For these SPDE’s, the highest order derivative in time has the same order as the highest order derivative in distance along the string (time-to-maturity). As a consequence, hyperbolic SPDE’s present wave-like solutions, that can propagate as pulses with a “velocity”. In this class, we find the so-called “Brownian sheet” which is the direct generalization of Brownian motion to higher dimensions, that preserves continuity in time-to-maturity. The Brownian sheet is the surface spanned by the string configurations as time goes on. The Brownian sheet is however non-homogeneous in time-to-maturity.

If the string has no inertia, its dynamics are characterized by parabolic SPDE’s. These stochastic processes lead to smoother diffusion of shocks through time, along time-to-maturity. Finally, the third class of SPDE’s of second-order, namely elliptic partial differential equations. Elliptic SPDE’s give processes that are differentiable both in x and t. Therefore, in the strict limit of continuous trading, these stochastic processes correspond to locally riskless interest rates.

The general form of SPDE’s reads

A(t,x) ∂²f(t,x)/∂t² + 2B(t,x) ∂²f(t,x)/∂t∂x + C(t,x) ∂²f(t,x)/∂x² = F(t,x,f(t,x), ∂f(t,x)/∂t, ∂f(t,x)/∂x, S) —– (1)

where f (t, x) is the forward rate curve. S(t, x) is the “source” term that will be generally taken to be Gaussian white noise η(t, x) characterized by the covariance

Cov η(t, x), η(t′, x′) = δ(t − t′) δ(x − x′) —– (2)

where δ denotes the Dirac distribution. Equation (1) is the most general second-order SPDE in two variables. For arbitrary non-linear terms in F, the existence of solutions is not warranted and a case by case study must be performed. For the cases where F is linear, the solution f(t,x) exists and its uniqueness is warranted once “boundary” conditions are given, such as, for instance, the initial value of the function f(0,x) as well as any constraints on the particular form of equation (1).

Equation (1) is defined by its characteristics, which are curves in the (t, x) plane that come in two families of equation :

Adt = (B + √(B2 − AC))dx —– (3)

Adt = (B − √(B2 − AC))dx —– (4)

These characteristics are the geometrical loci of the propagation of the boundary conditions.

Three cases must be considered.

• When B² > AC, the characteristics are real curves and the corresponding SPDE’s are called “hyperbolic”. For such hyperbolic SPDE’s, the natural coordinate system is formed from the two families of characteristics. Expressing (1) in terms of these two natural coordinates λ and μ, we get the “normal form” of hyperbolic SPDE’s :

∂²f/∂λ∂μ = P (λ,μ) ∂f/∂λ +Q (λ,μ) ∂f/∂μ + R (λ,μ)f + S(λ,μ) —– (5)

The special case P = Q = R = 0 with S(λ,μ) = η(λ,μ) corresponds to the so-called Brownian sheet, well studied in the mathematical literature as the 2D continuous generalization of the Brownian motion.

• When B² = AC, there is only one family of characteristics, of equation

Adt = Bdx —– (6)

Expressing (1) in terms of the natural characteristic coordinate λ and keeping x, we get the “normal form” of parabolic SPDE’s :

∂²f/∂x² = K (λ,μ)∂f/∂λ +L (λ,μ)∂f/∂x +M (λ,μ)f + S(λ,μ) —– (7)

The diffusion equation, well-known to be associated to the Black-Scholes option pricing model, is of this type. The main difference with the hyperbolic equations is that it is no more invariant with respect to time-reversal t → −t. Intuitively, this is due to the fact that the diffusion equation is not conservative, the information content (negentropy) continually decreases as time goes on.

• When B² < AC, the characteristics are not real curves and the corresponding SPDE’s are called “elliptic”. The equations for the characteristics are complex conjugates of each other and we can get the “normal form” of elliptic SPDE’s by using the real and imaginary parts of these complex coordinates z = u ± iv :

∂²f/∂u² + ∂²f/∂v² = T ∂f/∂u + U ∂f/∂v + V f + S —– (8)

There is a deep connection between the solution of elliptic SPDE’s and analytic functions of complex variables.

Hyperbolic and parabolic SPDE’s provide processes reducing locally to standard Brownian motion at fixed time-to-maturity, while elliptic SPDE’s give locally riskless time evolutions. Basically, this stems from the fact that the “normal forms” of second-order hyperbolic and parabolic SPDE’s involve a first-order derivative in time, thus ensuring that the stochastic processes are locally Brownian in time. In contrast, the “normal form” of second-order elliptic SPDE’s involve a second- order derivative with respect to time, which is the cause for the differentiability of the process with respect to time. Any higher order SPDE will be Brownian-like in time if it remains of order one in its time derivatives (and higher-order in the derivatives with respect to x).

For No Arbitrage Opportunities to Exist, Investment Strategy Must be a Martingale. (Didactic 2)

We postulate the existence of a stochastic discount factor (SDF) that prices all assets in this economy and denote it by M. This process is also termed the pricing kernel, the pricing operator, or the state price density. It is well known that assuming that no dynamic arbitrage trading strategies can be implemented by trading in the financial securities issued in the economy is roughly equivalent to the existence of a strictly positive SDF. For no arbitrage opportunities to exist, the product of M with the value process of any investment strategy must be a martingale. Technically, recall that a martingale is a family of random variables ξ(t) such that the mathematical expectation of the increment ξ(t₂)−ξ(t₁) (for arbitrary t₁ < t₂), conditioned on the past values ξ(s) (s ≤ t₁), is zero. The drift of a martingale is thus zero. This is different from the Markov process, which is better known in the physical community, defined by the independence of the next increment on past values.

Under an adequate definition of the space of admissible trading strategies, the product MV is a martingale, where V is the value process of any admissible self-financing trading strategy implemented by trading on financial securities. Then,

V(t) = E_tV(s) M(s)/M(t) —– (1)

where s is a future date and E_t[x] denotes the mathematical expectation of x taken at time t. In particular, we require that a bank account and zero-coupon discount bonds of all maturities satisfy this condition.

A security is referred to as a (floating-rate) bank account, if it is “locally riskless”. Thus, the value at time t, of an initial investment of B(0) units in the bank account that is continuously reinvested, is given by the following process

B(t) = B(0) exp{∫₀^t r(s)ds} —– (2)

where r(t) is the instantaneous nominal interest rate.

We further assume that, at any time t, riskless discount bonds of all maturity dates trade in this economy and let P (t,s) denote the time t price of the s maturity bond. We require that P (s,s) = 1, that P (t,s) > 0 and that ∂P(t,s)/∂s exists.

Instantaneous forward rates at time t for all times-to-maturity x > 0, f(t,x), are defined by

f(t,x)=−∂logP(t,t+x)/∂x —– (3)

which is the rate that can be contracted at time t for instantaneously riskless borrowing or lending at time t + x. We require that the initial forward curve f (0,x), for all x, be continuous.

Equivalently, from the knowledge of the instantaneous forward rates for all times- to-maturity between 0 and time s − t, the price at time t of a bond with maturity s

can be obtained by

P(t,s) = exp {−∫₀^s−t f(t,x)dx} —– (4)

Forward rates thus fully represent the information in the prices of all zero-coupon bonds. The spot interest rate at time t, r(t), is the instantaneous forward rate at time t with time-to-maturity 0,

r(t) = f(t,0) —– (5)

For convenience, we model the dynamics of forward rates. Clearly, we could as well model the dynamics of bond prices directly, or even the dynamics of the yields to maturity of the zero-coupon bonds. We use forward rates with fixed time-to-maturity rather than fixed maturity date. The model of HJM starts from processes for forward rates with a fixed maturity date. This is different from what we do. If we use a “hat” to denote the forward rates modeled by HJM,

f^ˆ(t,s) = f (t,s−t) —– (6)

or, equivalently,

f^ˆ(t,x) = f(t,t+x) —– (7)

for fixed s. Brace and Musiela define forward rates in the same fashion. Miltersen, Sandmann and Sondermann, and Brace, Gatarek and Musiela use definitions of forward rates similarly, albeit for non-instantaneous forward rates. Modelling forward rates with fixed time-to-maturity is more natural for thinking of the dynamics of the entire forward curve as the shape of a string evolving in time. In contrast, in HJM, forward rate processes disappear as time reaches their maturities. Note, however, that we still impose the martingale condition on bonds with fixed maturity date, since these are the financial instruments that are actually traded.

Financial Forward Rate “Strings” (Didactic 1)

Imagine that Julie wants to invest $1 for two years. She can devise two possible strategies. The first one is to put the money in a one-year bond at an interest rate r₁. At the end of the year, she must take her money and find another one-year bond, with interest rate r_1/2 which is the interest rate in one year on a loan maturing in two years. The final payoff of this strategy is simply (1 + r₁)(1 + r_1/2). The problem is that Julie cannot know for sure what will be the one-period interest rate r_1/2 of next year. Thus, she can only estimate a return by guessing the expectation of r_1/2.

Instead of making two separate investments of one year each, Julie could invest her money today in a bond that pays off in two years with interest rate r₂. The final payoff is then (1 + r₂)². This second strategy is riskless as she knows for sure her return. Now, this strategy can be reinterpreted along the line of the first strategy as follows. It consists in investing for one year at the rate r₁ and for the second year at a forward rate f₂. The forward rate is like the r_1/2 rate, with the essential difference that it is guaranteed : by buying the two-year bond, Julie can “lock in” an interest rate f₂ for the second year.

This simple example illustrates that the set of all possible bonds traded on the market is equivalent to the so-called forward rate curve. The forward rate f(t,x) is thus the interest rate that can be contracted at time t for instantaneously riskless borrowing 1 or lending at time t + x. It is thus a function or curve of the time-to-maturity x², where x plays the role of a “length” variable, that deforms with time t. Its knowledge is completely equivalent to the set of bond prices P(t,x) at time t that expire at time t + x. The shape of the forward rate curve f(t,x) incessantly fluctuates as a function of time t. These fluctuations are due to a combination of factors, including future expectation of the short-term interest rates, liquidity preferences, market segmentation and trading. It is obvious that the forward rate f (t, x+δx) for δx small can not be very different from f (t,x). It is thus tempting to see f(t,x) as a “string” characterized by a kind of tension which prevents too large local deformations that would not be financially acceptable. This superficial analogy is in the follow up of the repetitious intersections between finance and physics, starting with Bachelier who solved the diffusion equation of Brownian motion as a model of stock market price fluctuations five years before Einstein, continuing with the discovery of the relevance of Lévy laws for cotton price fluctuations by Mandelbrot that can be compared with the present interest of such power laws for the description of physical and natural phenomena. The present investigation delves into how to formalize mathematically this analogy between the forward rate curve and a string. We formulate the term structure of interest rates as the solution of a stochastic partial differential equation (SPDE), following the physical analogy of a continuous curve (string) whose shape moves stochastically through time.

The equation of motion of macroscopic physical strings is derived from conservation laws. The fundamental equations of motion of microscopic strings formulated to describe the fundamental particles derive from global symmetry principles and dualities between long-range and short-range descriptions. Are there similar principles that can guide the determination of the equations of motion of the more down-to-earth financial forward rate “strings”?

Suppose that in the middle ages, before Copernicus and Galileo, the Earth really was stationary at the centre of the universe, and only began moving later on. Imagine that during the nineteenth century, when everyone believed classical physics to be true, that it really was true, and quantum phenomena were non-existent. These are not philosophical musings, but an attempt to portray how physics might look if it actually behaved like the financial markets. Indeed, the financial world is such that any insight is almost immediately used to trade for a profit. As the insight spreads among traders, the “universe” changes accordingly. As G. Soros has pointed out, market players are “actors observing their own deeds”. As E. Derman, head of quantitative strategies at Goldman Sachs, puts it, in physics you are playing against God, who does not change his mind very often. In finance, you are playing against Gods creatures, whose feelings are ephemeral, at best unstable, and the news on which they are based keep streaming in. Value clearly derives from human beings, while mass, charge and electromagnetism apparently do not. This has led to suggestions that a fruitful framework to study finance and economy is to use evolutionary models inspired from biology and genetics.

This does not however guide us much for the determination of “fundamental” equa- tions, if any. Here, we propose to use the condition of absence of arbitrage opportunity and show that this leads to strong constraints on the structure of the governing equations. The basic idea is that, if there are arbitrage opportunities (free lunches), they cannot live long or must be quite subtle, otherwise traders would act on them and arbitrage them away. The no-arbitrage condition is an idealization of a self-consistent dynamical state of the market resulting from the incessant actions of the traders (ar- bitragers). It is not the out-of-fashion equilibrium approximation sometimes described but rather embodies a very subtle cooperative organization of the market.

We consider this condition as the fundamental backbone for the theory. The idea to impose this requirement is not new and is in fact the prerequisite of most models developed in the academic finance community. Modigliani and Miller [here and here] have indeed emphasized the critical role played by arbitrage in determining the value of securities. It is sometimes suggested that transaction costs and other market imperfections make irrelevant the no-arbitrage condition. Let us address briefly this question.

Transaction costs in option replication and other hedging activities have been extensively investigated since they (or other market “imperfections”) clearly disturb the risk-neutral argument and set option theory back a few decades. Transaction costs induce, for obvious reasons, dynamic incompleteness, thus preventing valuation as we know it since Black and Scholes. However, the most efficient dynamic hedgers (market makers) incur essentially no transaction costs when owning options. These specialized market makers compete with each other to provide liquidity in option instruments, and maintain inventories in them. They rationally limit their dynamic replication to their residual exposure, not their global exposure. In addition, the fact that they do not hold options until maturity greatly reduces their costs of dynamic hedging. They have an incentive in the acceleration of financial intermediation. Furthermore, as options are rarely replicated until maturity, the expected transaction costs of the short options depend mostly on the dynamics of the order flow in the option markets – not on the direct costs of transacting. For the efficient operators (and those operators only), markets are more dynamically complete than anticipated. This is not true for a second category of traders, those who merely purchase or sell financial instruments that are subjected to dynamic hedging. They, accordingly, neither are equipped for dynamic hedging, nor have the need for it, thanks to the existence of specialized and more efficient market makers. The examination of their transaction costs in the event of their decision to dynamically replicate their options is of no true theoretical contribution. A second important point is that the existence of transaction costs should not be invoked as an excuse for disregarding the no-arbitrage condition, but, rather should be constructively invoked to study its impacts on the models…..