Treffer: THE COST OF ACHIEVING THE BEST PORTFOLIO IN HINDSIGHT: The cost of achieving the best portfolio in hindsight

For a market with m assets consider the minimum, over all possible sequences of asset prices through time n, of the ratio of the final wealth of a nonanticipating investment strategy to the wealth obtained by the best constant rebalanced portfolio computed in hindsight for that price sequence. We show that the maximum value of this ratio over all nonanticipating investment strategies is Vn = [∑ 2−nH(n_1/n,…,n_m/n)(n!/(n1! … nm!))]−1, where H(·) is the Shannon entropy, and we specify a strategy achieving it. The optimal ratio Vn is shown to decrease only polynomially in n, indicating that the rate of return of the optimal strategy converges uniformly to that of the best constant rebalanced portfolio determined with full hindsight. We also relate this result to the pricing of a new derivative security which might be called the hindsight allocation option.

AN0001446422;MOR01NOV.98;2000Jul26.20:31;v4.1

THE COST OF ACHIEVING THE BEST PORTFOLIO IN HINDSIGHT 

For a market with m assets consider the minimum, over all possible sequences of asset prices through time n, of the ratio of the final wealth of a nonanticipating investment strategy to the wealth obtained by the best constant rebalanced portfolio computed in hindsight for that price sequence. We show that the maximum value of this ratio over all nonanticipating investment strategies is

Multiple line equation(s) can not be represented in ASCII text.

where H(ù) is the Shannon entropy, and we specify a strategy achieving it. The optimal ratio V[subn] is shown to decrease only polynomially in n, indicating that the rate of return of the optimal strategy converges uniformly to that of the best constant rebalanced portfolio determined with full hindsight. We also relate this result to the pricing of a new derivative security which might be called the hindsight allocation option.

<bold> 1. Introduction. </bold> Hindsight is not available when it is most useful. This is true in investing where hindsight into market performance makes obvious how one should have invested all along. In this paper we investigate the extent to which a nonanticipating investment strategy can achieve the performance of the best strategy determined in hindsight.

Obviously, with hindsight, the best investment strategy is to shift one's wealth daily into the asset with the largest percentage increase in price. Unfortunately, it is hopeless to match the performance of this strategy in any meaningful way, and therefore we must restrict the class of investment strategies over which the hindsight optimization is performed. Here we focus on the class of investment strategies called the constant rebalanced portfolios. A constant rebalanced portfolio rebalances the allocation of wealth among the available assets to the same proportions each day. Using all wealth to buy and hold a single asset is a special case. Therefore the best constant rebalanced portfolio, at the very least, outperforms the best asset.

In practice, one would expect the wealth achieved by the best constant rebalanced portfolio computed in hindsight to grow exponentially with a rate determined by asset price drift and volatility. Even if the prices of individual assets are going nowhere in the long run, short-term fluctuations in conjunction with constant rebalancing may lead to substantial profits. Furthermore, the best constant rebalanced portfolio will in all likelihood exponentially outperform any fixed constant rebalanced portfolio which includes buying and holding the best asset in hindsight.

The intuition that the best constant rebalanced portfolio is a good performance target is motivated by the well-known fact that if market returns are independent and identically distributed from one day to the next, the expected utility, for a wide range of utility functions including the log utility, is maximized by a constant rebalanced portfolio strategy. Additionally, "turnpike" theory (see Huberman and Ross 1983, Cox and Huang 1992, and references therein) finds an even broader class of utility functions for which, by virtue of their behavior at large wealths, constant rebalancing becomes optimal as the investment horizon tends to infinity. In all these settings, the optimal constant rebalanced portfolio depends on the underlying distribution, which is unknown in practice. Targeting the best constant rebalanced portfolio computed in hindsight for the actual market sequence is one way of dealing with this lack of information.

The question is: To what extent can a nonanticipating investment strategy perform as well as the best constant rebalanced portfolio determined in hindsight? We address this question from a distribution-free, worst-sequence perspective with no restrictions on asset price behavior. Asset prices can increase or decrease arbitrarily, even drop to zero. We assume no underlying randomness or probability distribution on asset price changes.

The analysis is best expressed in terms of a contest between an investor and nature. After the investor has selected a nonanticipating investment strategy, nature, with full knowledge of the investor's strategy (and its dependence on the past), selects that sequence of asset price changes which minimizes the ratio of the wealth achieved by the investor to the wealth achieved by the best constant rebalanced portfolio computed in hindsight for the selected sequence. The investor selects an investment strategy that maximzes the minimum ratio. In the main part of the paper we determine the optimum investment strategy and compute the max-min value of the ratio of wealths.

It may seem that such an analysis is overly pessimistic and risk averse since in reality there is no deliberate force trying to minimize investment returns. What is striking, however is that if investment performance is measured in terms of rate of return or exponential growth rate per investment period, even this pessimistic point of view yields a favorable result. More specifically, the main result of this paper is the identification of an investment algorithm that achieves wealth S??[subn] at time n that satisfies

Multiple line equation(s) can not be represented in ASCII text.

for every market sequence, where S[sup*][subn] is the wealth achieved by the best constant rebalanced portfolio in hindsight, and H(p[sub1],...,p[subm]) = - universal quantifier p[subj] log p[subj] is the Shannon entropy function.

Since it can be shown that

Multiple line equation(s) can not be represented in ASCII text.

(for m = 2 assets), this factor, the price of universality, will not affect the exponential growth rate of wealth of S??[subn] relative to S[sup*][subn], i.e., lim inf(1/n) log(S??[subn]/S[sup*][subn]) greater than or equal to 0. In other words, the rate of return achieved by the optimal strategy converges over time to that of the best constant rebalanced portfolio computed in hindsight, uniformly for every sequence of asset price changes. The bound (1) is the best possible; there are sequences of price changes that hold S??[subn]/S[sup*][subn] to this bound for any nonanticipating investment strategy.

The problem of achieving the best portfolio in hindsight leads naturally to the consideration of a new derivative security which might be called the hindsight allocation option. The hindsight allocation option has a payoff at time n equal to S[sup*][subn], the wealth earned by investing one dollar according to the best constant rebalanced portfolio (the best constant allocation of wealth) computed in hindsight for the observed stock and bond performance. This option might, for example, interest investors who are uncertain about how to allocate their wealth between stocks and bonds. By purchasing a hindsight allocation option, an investor achieves the performance of the best constant allocation of wealth determined with full knowledge of the actual market performance.

In section4 we argue that the max-min ratio computed above yields a tight upper bound on the price of this option. Specifically, Equation (1) suggests that S??[subn] is an arbitrage opportunity if the option price is more than 1/V[subn]. We compare this bound to the no-arbitrage option price for two well-known models of market behavior, the discrete time binomial lattice model and the continuous time geometric Wiener model. We consider only the simple case of a volatile stock and a bond with a constant rate of return. It is shown that the no-arbitrage prices for these restricted market models have essentially the same asymptotic csquare root of n behavior as the upper bound 1/V[subn]. Different model parameter choices (volatility, interest rate) can yield more favorable constants c.

The pricing of the hindsight allocation option in the binomial and geometric Wiener models can also be thought of in terms of the max-min framework. The models can be viewed as constraints on nature's choice of asset price changes. The underlying distribution in the geometric Wiener model serves as a technical device for constraining the set of continuous asset price paths from which nature can choose. Because these markets are complete for the special case of one stock and one bond, the best constant rebalanced portfolio computed in hindsight can be hedged perfectly given a unique initial wealth. This wealth corresponds to the no-arbitrage price of the hindsight allocation option. Furthermore, the max-min ratio of wealths obtained by the investor and nature, when nature is constrained by these models, must be the reciprocal of this unique initial wealth.

Early work on universal portfolios (portfolio strategies performing uniformly well with respect to constant rebalanced portfolios) can be found in Cover and Gluss (1986), Larson (1986), Cover (1991), Merhav and Feder (1993), and Cover and Ordentlich (1996).

Cover and Gluss (1986) restrict daily returns to a finite set and provide an algorithm, based on the approachability-excludability theorem of Blackwell (1956a, 1956b), that achieves a wealth ratio

Multiple line equation(s) can not be represented in ASCII text.

for m = 2 stocks, where c is a positive constant. Larson (1986), also restricting daily returns to a finite set, uses a compound Bayes approach to achieve

Multiple line equation(s) can not be represented in ASCII text.

for arbitrarily small delta > 0. Cover (1991) defines a family of mu-weighted universal portfolios and uses Laplace's method of integration to show, for a bounded ratio of maximum to minimum daily asset returns, that S??[subn]/S[sup*][subn] greater than or equal to c[subn]/n[sup(m-1)/2] for m stocks, where c[subn] is the determinant of a certain sensitivity matrix measuring the empirical volatility of the price sequence. Merhav and Feder (1993) establish polynomial bounds on S??[subn]/S[sup*][subn] under the same constraints.

The first individual sequence (worst-case) analysis of the universal portfolio of Cover (1991) is given in Cover and Ordentlich (1996), where it is shown that a Dirichlet(1/2) weighted universal portfolio achieves a worst case performance of

Multiple line equation(s) can not be represented in ASCII text.

This analysis is also extended to investment with side information, with similar results. Jamshidian (1992) applies the universal portfolio of Cover (1991) (with mu uniform) to a geometric Wiener market, establishing the asymptotic behavior of S??(t)/S[sup*](t), and showing (l/t) log S??(t)/S[sup*](t) function mapping 0, for such markets.

The paper is organized as follows. Section 2 establishes notation and some basic definitions. The individual-sequence performance and game-theoretic analysis are established in section3. Section 4 contains the hindsight allocation option pricing analysis.

<bold> 2. Notation and definitions. </bold> We represent the behavior of a market of m assets for n trading periods by a sequence of nonnegative, nonzero (at least one nonzero component) price-relative vectors x[sub1], ..., x[subn] is an element of R[supm][sub+]. We refer to x[supn] = x[sub1], ..., x[subn] as the market sequence. The jth component of the ith vector denotes the ratio of closing to opening price of the jth asset for the ith trading period. Thus an investment in asset j on day i increases by a factor of x[subij].

Investment in the market is specified by a portfolio vector b = (b[sub1],...,b[subm])[supt] with nonnegative entries summing to one. That is, b is an element of B, where

Multiple line equation(s) can not be represented in ASCII text.

A portfolio vector b denotes the fraction of wealth invested in each of the m assets. An investment according to portfolio b[subi] on day i multiplies wealth by a factor of

Multiple line equation(s) can not be represented in ASCII text.

A sequence of n investments according to portfolio choices b[sub1], ..., b[subn] changes wealth by a factor of

Multiple line equation(s) can not be represented in ASCII text.

A constant rebalanced portfolio investment strategy uses the same portfolio b for each trading day. Assuming normalized initial wealth S[sub0] = 1, the final wealth will be

Multiple line equation(s) can not be represented in ASCII text.

For a sequence of price-relatives x[supn] it is possible to compute the best constant rebalanced portfolio b[sup*] as

Multiple line equation(s) can not be represented in ASCII text.

which achieves a wealth factor of

Multiple line equation(s) can not be represented in ASCII text.

The best constant rebalanced portfolio b[sup*] depends on knowledge of market performance for time 1, 2, ..., n; it is not a nonanticipating investment strategy.

This brings up the definition of a nonanticipating investment strategy.

DEFINITION 1. A nonanticipating investment strategy is a sequence of maps

Multiple line equation(s) can not be represented in ASCII text.

where

b[supi] = b[supi](x[sup1], ..., x[subi-1])

is the portfolio used on day i given past market outcomes x[supi-1] = x[sub1],...,x[subi-1].

<bold> 3. Worst-case analysis. </bold> We now present the main result, a theorem characterizing the extent to which the best constant rebalanced portfolio computed in hindsight can be tracked in the worst case. Our analysis is best expressed in terms of a contest between an investor, who announces a nonanticipating investment strategy b??[subi](ù); and nature, who, with full knowledge of the investor's strategy, selects a market sequence x[supn] = x[sub1], x[sub2], ..., x[subn] to minimize the ratio of wealths S??[subn](x[supn])/S[sup*][subn](x[supn]), where S??[subn](x[supn]) is the investor's wealth against sequence x[supn] and is given by

Multiple line equation(s) can not be represented in ASCII text.

Thus, nature attempts to induce poor performance on the part of the investor relative to the best constant rebalanced portfolio b[sup*] computed with complete knowledge of x[supn]. The investor, wishing to protect himself from this worst case, selects that nonanticipating investment strategy b??[subi](ù) which maximizes the worst-case ratio of wealths.

Theorem 1 (Max-min ratio). For m assets and all n,

Multiple line equation(s) can not be represented in ASCII text.

where

Multiple line equation(s) can not be represented in ASCII text.

and

Multiple line equation(s) can not be represented in ASCII text.

is the Shannon entropy function.

Remark. For m = 2, the value V[subn] is simply

Multiple line equation(s) can not be represented in ASCII text.

and it is shown in section3.2 that

Multiple line equation(s) can not be represented in ASCII text.

for all n. Thus V[subn] behaves essentially like 1/square root of n. For m > 2,

Multiple line equation(s) can not be represented in ASCII text.

Remark. It is noted in section3.3 that

Multiple line equation(s) can not be represented in ASCII text.

in the sense that

Multiple line equation(s) can not be represented in ASCII text.

For m = 2 this reduces to

Multiple line equation(s) can not be represented in ASCII text.

Remark. The max-min optimal strategy for m = 2 will be specified in Equations (8) - (13). These equations are followed by an alternative definition of the optimal strategy in terms of extremal strategies.

We note that the negative logarithm of the max-min ratio of wealths given by Equation (2) also corresponds to the solution of a min-max pointwise redundancy problem in universal data compression theory. The pointwise redundancy problem was studied and solved by Shtarkov (1987) and earlier works referenced therein. A principal result of the present work, which is developed in greater information theoretic detail in Cover and Ordentlich (1996) and Ordentlich (1996), is that worst sequence market performance is bounded by worst sequence data compression.

The strategy achieving the maximum in Theorem 1, as developed in the proof below, depends on the horizon n. We note, however, that Cover and Ordentlich (1996) exhibits an infinite horizon investment strategy, the Dirichlet-weighted universal portfolio, denoted by b??[supD](ù), which for m = 2 assets achieves a wealth ratio S??[supD][subn](x[supn])/S[sup*][subn](x[sup*]) satisfying

Multiple line equation(s) can not be represented in ASCII text.

At time i, the Dirichlet-weighted universal portfolio investment strategy uses the portfolio

Multiple line equation(s) can not be represented in ASCII text.

where

Multiple line equation(s) can not be represented in ASCII text.

The measure mu on the portfolio simplex B is the Dirichlet (1/2, ..., 1/2) prior with density

Multiple line equation(s) can not be represented in ASCII text.

where GAMMA(ù) denotes the Gamma function. The running wealth factor achieved by the Dirichlet-weighted universal portfolio through each time n is

Multiple line equation(s) can not be represented in ASCII text.

Thus the max-min ratio can be achieved to within a factor of square root of 2pi for all n by a single infinite horizon strategy. The bound (4) generalizes to m > 2 so that for each m, the worst-case wealth achieved by the Dirichlet-weighted universal portfolio is within a constant factor (independent of n) of V[subn].

The significance of Theorem 1 can be appreciated by considering some naive choices for the optimum investor strategy b??. Suppose, for m = 2 assets, that b?? corresponds to investing half of the initial wealth in a buy-and-hold of asset 1 and the other half in a buy-and-hold of asset 2. In this case the first two portfolio choices are

Multiple line equation(s) can not be represented in ASCII text.

Since we are allowing nature to select arbitrary price-relative vector sequences, nature could set x[sub1] = (0, 2)[supt] and x[sub2] = (2, 0)[supt], in which case the investor using the split buy-and-hold strategy (6) goes broke after two days. On the other hand, for this two-day sequence, the best constant rebalanced portfolio is b[sup*] = (1/2, 1/2)[supt] and yields a wealth factor S[sup*][sub2](x[sub1], x[sub2]) of 1.

Suppose the investor instead opts to rebalance his wealth daily to the initial (1/2, 1/2) proportions. Here b??[subi] is the constant rebalanced portfolio b = (1/2, 1/2)[supt]. If nature then chooses the sequence of price-relative vectors x[supn] = (2, 0)[supt], (2, 0)[supt],..., (2, 0)[supt] the investor earns a wealth factor

Multiple line equation(s) can not be represented in ASCII text.

while the best constant rebalanced portfolio b[sup*] = (1, 0)[supt] earns S[sup*][subn] (x[supn]) = 2[supn]. The ratio S??[subn]/S[sup*][subn] of these two wealths decreases exponentially in n while the max-min ratio V[subn] decreases only polynomially. In particular, the wealth achieved by the max-min optimal strategy is at least

Multiple line equation(s) can not be represented in ASCII text.

for this sequence.

These two investment strategies are particularly naive. A more sophisticated scheme might start off with b??[sub1] = (1/2, 1/2)[supt] and then use the best constant rebalanced portfolio for the observed past. This scheme, however, is also flawed, since if nature chooses x[sub1] = (1, 0)[supt], the investor would use b??[sub2] = (1, 0)[supt] the following day and then would go broke if nature set x[sub2] = (0, 1)[supt]. One might think of fixing this scheme by using a time varying mixture of the (1/2, 1/2) portfolio and the best constant rebalanced portfolio for the past. However, this class of strategies also fails to achieve V[subn].

We now proceed with the proof of Theorem 1. The following lemma is used. In the sequel we adopt the conventions that a/0 = infinity if a > 0, and that 0/0 = 0.

Lemma 1. If alpha[sub1], ..., alpha[subn] greater than or equal to 0, beta[sub1], ..., beta[subn] greater than or equal to 0, then

Multiple line equation(s) can not be represented in ASCII text.

Proof of Lemma 1. Let

Multiple line equation(s) can not be represented in ASCII text.

The lemma is trivially true if alpha[subJ] = 0 since the right side of (7) is zero. So assume alpha[subJ] > 0. Then, if beta[subJ] = 0 the lemma is true since both the left and right sides of (7) are infinity. Therefore assume alpha[subJ] > 0 and beta[subJ] > 0. Then

Multiple line equation(s) can not be represented in ASCII text.

because

Multiple line equation(s) can not be represented in ASCII text.

which implies

Multiple line equation(s) can not be represented in ASCII text.

for all j.

Proof of Theorem 1. For ease of exposition we prove the theorem for m = 2. The generalization of the argument to m > 2 is straightforward.

Thus, for the case of m = 2 we must show that

Multiple line equation(s) can not be represented in ASCII text.

where

Multiple line equation(s) can not be represented in ASCII text.

We prove that

Multiple line equation(s) can not be represented in ASCII text.

by explicitly specifying the max-min optimal strategy b??. We define the strategy by keeping track of the indices of the terms in the product

Multiple line equation(s) can not be represented in ASCII text.

For sequences j[supn] is an element of {1, 2}[supn] let n[sub1](j[supn) and n[sub2](j[supn]) denote, respectively, the number of 1's and the number of 2's in j[supn]. That is, if j[supn] = (j[sub1],...,j[subn]),

Multiple line equation(s) can not be represented in ASCII text.

where I(ù) is the indicator function. Let

Multiple line equation(s) can not be represented in ASCII text.

Then, since

Multiple line equation(s) can not be represented in ASCII text.

is a probability measure on the set of sequences j[supn] is an element of {1, 2}[supn]. For l < n, let

Multiple line equation(s) can not be represented in ASCII text.

be the marginal probability mass of j[sub1],...,j[subl]. This marginal probability may also be denoted by w(j[supl-1], j[subl]). Finally, define the nonanticipating investment strategy

Multiple line equation(s) can not be represented in ASCII text.

and

Multiple line equation(s) can not be represented in ASCII text.

with

An alternative characterization of the max-min optimal strategy, which turns out to be equivalent to the above, is as follows. Break the initial wealth into 2[supn] piles, one corresponding to each sequence j[supn], where the fraction of initial wealth assigned to pile j[supn] is precisely w(j[supn]) as given in (9). Now invest all the wealth in pile j[supn] in asset j[sub1] on day 1. From then on, for each day i, shift the entirety of the running wealth for this pile into asset j[subi]. Do this in parallel for each of the 2[supn] piles j[supn]. We refer to the strategy used to manage pile j[supn] as the extremal strategy corresponding to the sequence j[supn].

The wealth factor achieved by the investor using (11) and (12) is

Multiple line equation(s) can not be represented in ASCII text.

where

Multiple line equation(s) can not be represented in ASCII text.

and (14) follows from a telescoping of the product.

It is apparent from Equation (14) that the extremal strategy formulation of the max-min optimal strategy is equivalent to the portfolio formulation (8) - (13). The extremal strategies simply "pick off" the product of the price relatives corresponding to the sequence of assets with indices j[supn]. Equation (14) represents the sum of the wealths obtained by the extremal strategies operating in parallel.

Note that for 0 less than or equal to k less than or equal to n,

Multiple line equation(s) can not be represented in ASCII text.

Also note that S[sup*][subn](x[supn]) can be rewritten as

Multiple line equation(s) can not be represented in ASCII text.

where

Multiple line equation(s) can not be represented in ASCII text.

achieves the maximum in (16).

Therefore, for any market sequence x[supn], Lemma 1 and the above imply that

Multiple line equation(s) can not be represented in ASCII text.

where (17) follows from a combination of Lemma 1 and the cancellation of the sums of products of ??, and (18) follows from (15). Since the above holds for all sequences x[supn], we have shown that

Multiple line equation(s) can not be represented in ASCII text.

To show equality in (19) we consider the following possibilities for x[supn], For each j[supn] is an element of {1, 2)[supn] define x[supn](j[supn]) = x[sub1](j[sub1]),..., x[subn](j[subn]), as

Multiple line equation(s) can not be represented in ASCII text.

Let

Multiple line equation(s) can not be represented in ASCII text.

be the set of such extremal sequences x[supn].

An important property shared by all nonanticipating investment strategies b??(ù) on the sequences (20) is that

Multiple line equation(s) can not be represented in ASCII text.

Also note that, for x[supn] (j[supn] is an element of K, the best constant rebalanced portfolio is easily verified to be

Multiple line equation(s) can not be represented in ASCII text.

so that

Multiple line equation(s) can not be represented in ASCII text.

Therefore

Multiple line equation(s) can not be represented in ASCII text.

Since the minimum is less than any average, we obtain equality in (19) from

Multiple line equation(s) can not be represented in ASCII text.

which holds for any b??. Thus

Multiple line equation(s) can not be represented in ASCII text.

Combining this with (19) completes the proof of the theorem.

<bold> Complexity. </bold> It appears from (11) and (12) that computing the max-min optimal portfolio requires keeping track of the products

Multiple line equation(s) can not be represented in ASCII text.

for each sequence j[subl-1]. This quickly becomes prohibitively complex, since the number of such sequences is exponentially increasing in l. Fortunately, a simplification can be made.

This follows from the observation that w(j[supn]) defined in (9) depends on j[supn] only through its type (n[sub1](j[supn]), n[sub2](j[supn])), the number of 1's and 2's. This implies that w(j[subn-1], j[subn]), for fixed j[subn], is a function of j[supn-1] only through (n[sub1](j[supn-1]), n[sub2](j[supn-1])). The same applies to

Multiple line equation(s) can not be represented in ASCII text.

Thus, by induction w(j[supl-1], j[subl]) and w(j[supl-1]), for all l, are constant on j[supl-1] with the same type.

Using this fact, the numerator and denominator of (11) and (12) can be evaluated by grouping the products

Multiple line equation(s) can not be represented in ASCII text.

according to the type of j[supl-1]. More specifically, the numerator of (11), for example, can be written as

Multiple line equation(s) can not be represented in ASCII text.

where w'[l-1](k, 1) equals w(j[supl-1], 1) when n[sub1](j[supl-1]) = k and

Multiple line equation(s) can not be represented in ASCII text.

The denominator can be rewritten in a similar way.

It is now clear that only the quantities X[subl-1] (k) need be computed and stored instead of the exponentially many products

Multiple line equation(s) can not be represented in ASCII text.

The complexity of this is linear in l, since there are only I such quantities. The simple recursions

Multiple line equation(s) can not be represented in ASCII text.

suffice to update the X[supl-1] (k).

The above generalizes in the obvious way to m > 2 assets resulting in a computational complexity growing like 1[supm-1]. Therefore, the max-min optimal portfolio is, in fact, computationally feasible for moderate m.

<bold> 3.1. Game-theoretic analysis. </bold> A full game-theoretic result can also be proved. Specifically, we imagine the same contest as above, except that mixed strategies are allowed. The payoff function is

Multiple line equation(s) can not be represented in ASCII text.

As before, the investor and nature respectively try to maximize and minimize the payoff. Let G[subn] denote the game when played with this payoff function.

A mixed strategy for the investor is a probability distribution P(b??) on. the space of nonanticipating investment strategies,

Multiple line equation(s) can not be represented in ASCII text.

Similarly, nature's mixed strategies are probability distributions on the space of price-relative sequences and will be denoted by 2(x[supn]). The following theorem can then be proved.

Theorem 2. The Value of the game G[subn] is

Multiple line equation(s) can not be represented in ASCII text.

where V[subn] is given by (2). Further, the investor's optimum strategy P[sup*] is the pure strategy specified by (8) - (13).

Proof. We prove this for m = 2, the generalization being obvious. The pure strategy P[sup*] is precisely the max-min optimal strategy (8)-(13) achieving the maximum in Theorem 1. Nature's optimum mixed strategy 2[sup*] (for m = 2) consists of choosing sequences from

Multiple line equation(s) can not be represented in ASCII text.

according to the probability distribution w(j[supn]) given by (9). The proof of

Multiple line equation(s) can not be represented in ASCII text.

follows from Equations (22) through (25). The theorem follows from (26) and (19).

The full game-theoretic analysis brings out a nice symmetry between the optimal investment strategy and nature's optimal strategy. The optimal investment strategy P[sup*] is a pure strategy constructed from the distribution w(j[supn]) on binary strings given by (9). Nature's optimal strategy, on the other hand, is to choose 0-1 price-relative vectors at random according to this same probability distribution.

This analysis generalizes to games with payoff

Multiple line equation(s) can not be represented in ASCII text.

for which the following holds.

Theorem 3. For concave nondecreasing phi, the game G[subn](phi) with payoff A[subphi](b??, x[supn]) has a value V (G[subn](phi)) given by

V(G[subn(phi)) = phi(V[subn),

where V[subn] is given by (2) and the optimal strategies are the same as those for G[subn].

<bold> 3.2. Bounds on </bold> V[subn]. We prove the following lemma for m = 2.

Lemma 2. For all n,

Multiple line equation(s) can not be represented in ASCII text.

Proof. We first prove the lower bound. In Cover and Ordentlich (1996), a sequential portfolio selection strategy called the Dirichlet(1/2, ..., 1/2) weighteduniversal portfolio was shown to achieve a wealth S??[supD][subn](x[supn]) satisfying

Multiple line equation(s) can not be represented in ASCII text.

Therefore

Multiple line equation(s) can not be represented in ASCII text.

proving the lower bound on V[subn].

We now establish the upper bound. Write 1/V[subn] as

Multiple line equation(s) can not be represented in ASCII text.

where

Multiple line equation(s) can not be represented in ASCII text.

dt is the Gamma function. If x is an integer, then GAMMA(x + 1) = x!. In Marshall and Olkin (1979), it is shown that

Multiple line equation(s) can not be represented in ASCII text.

is Schur convex. This implies that under the constraint x[sub1] + x[sub2] = n, it is minimized by setting x[sub1] = x[sub2] = n/2. Therefore, each term in the summation (27) can be bounded from below by

Multiple line equation(s) can not be represented in ASCII text.

to obtain

Multiple line equation(s) can not be represented in ASCII text.

The identity (see Rudin (1976))

Multiple line equation(s) can not be represented in ASCII text.

can now be applied to obtain

Multiple line equation(s) can not be represented in ASCII text.

The log convexity of GAMMA(x) (see Rudin 1976) now implies that

Multiple line equation(s) can not be represented in ASCII text.

where we have used the identity GAMMA(x + 1) = xGAMMA(x). Combining (29) and (30) we obtain

Multiple line equation(s) can not be represented in ASCII text.

thereby proving that

Multiple line equation(s) can not be represented in ASCII text.

for all n.

This bound can be generalized to m > 2 with the help of

Multiple line equation(s) can not be represented in ASCII text.

an extension of (28) to general m.

3.3. Asymptotics of V[subn]. The following lemma characterizes the asymptotic behavior of V[subn] for m stocks.

Lemma 3. For all m, V[subn] satisfies

Multiple line equation(s) can not be represented in ASCII text.

in the sense that

Multiple line equation(s) can not be represented in ASCII text.

The quantity V[subn] arises in a variety of settings including the max-min data compression problem (see Shtarkov 1987), the distribution of the longest common subsequence between two random sequences (Karlin 1996), and bounds on the probability of undetected errors by linear codes (see Kl??ve 1995, Massey 1978, and Szpankowski 1995). Lemma 3 is proved in Shtarkov, Tjalkens, and Willems (1995) and an asymptotic expansion of V[subn] to arbitrary order is given in Szpankowski (1995, 1996). A direct proof of Lemma 3 based on a Riemannsum approximation is given in Ordentlich (1996).

In addition, Shtarkov (1987) obtains the bound

Multiple line equation(s) can not be represented in ASCII text.

implying one half of the asymptotic behavior in Equation (31).

<bold> 4. The hindsight allocation option. </bold> The results of the previous section motivate the analysis of the hindsight allocation option, a derivative security which pays S[sup*][subn] (x[supn]), the result of investing one dollar according to the best constant rebalanced portfolio computed in hindsight for the observed market behavior x[supn] Let

Multiple line equation(s) can not be represented in ASCII text.

Certainly the price of the hindsight allocation option should be no higher than H??[subn]. This follows because H??[subn] dollars invested in the nonanticipating strategy described in the proof of Theorem 1 is guaranteed to result in wealth at time n no less than S[sup*][subn] (x[subn]) for all market sequences x[supn]. If the price of the hindsight allocation option were more than H??[subn], selling the option and investing only H??[subn] of the proceeds in the above strategy would be an arbitrage. Note that this argument assumes the existence of a riskless asset for investing the surplus.

Therefore, H??[subn] is an upper bound on the price of the hindsight allocation option valid for any market model (with a risk free asset). Furthermore, while the return of the best constant rebalanced portfolio is expected to grow exponentially with n, the upper bound on the price of the hindsight allocation option H??[subn] behaves like square root of n. This polynomial factor is exponentially negligible relative to S[sup*][subn].

Is H??[subn] a reasonable price for the hindsight allocation option? Probably not; the price should be lower. Pricing the option at H??[subn] may be appropriate if no assumptions about market behavior can be made. This is the case in section3, where no restrictions are placed on nature's choice for the market behavior. Returns on assets can be arbitrarily high or low, even zero. Actual markets, however, are typically less volatile. We gain more insight into this issue by using established derivative security pricing theory to determine the noarbitrage arbitrage price of the hindsight allocation option for two much studied models of market behavior, the binomial lattice and continuous time geometric Brownian motion models.

<bold> 4.1. Binomial lattice price. </bold> We consider a risky stock and a riskless bond. Accordingly, the price-relatives x[subi] are assumed to take on one of two values

Multiple line equation(s) can not be represented in ASCII text.

with r greater than or equal to 0, u > r > d. The first component of x[subi] reflects the change in the price of the stock as measured by the ratio of closing to opening price. The second component indicates that the riskless bond compounds at an interest rate of r for each investment period. The parameters of the model are thus u, d, and r. If the stock price changes by a factor of 1 + u it has gone "(u)p"; if it changes by a factor of 1 + d it has gone "(d)own."

We will find that the no-arbitrage price H[subn] of the hindsight allocation option for this model is closely related to H??[subn], the upper bound obtained in the previous sections. It will be apparent that for certain choices of d, u, and r, the upper bound H??[subn] is essentially attained.

For a sequence of n price-relatives x[supn] = x[sub1],..., x[subn], the wealth acquired by a constant rebalanced portfolio b = (b, 1 - b)[supt] can be written as

Multiple line equation(s) can not be represented in ASCII text.

where k is the number of vectors x[subi] for which x[subi1] = 1 + u. Since log S[subn](b) is concave in b, the best constant rebalanced portfolio b[sup*] = (b[sup*], 1 - b[sup*])[supt] is easily determined using calculus. For 0 < k < n, define b??[sup*] as the solution to

Multiple line equation(s) can not be represented in ASCII text.

It is given by

Multiple line equation(s) can not be represented in ASCII text.

For k = 0, set b??[sup*] = 0, and for k = n, set b??[sup*] = 1. Then b[sup*] is given by

b[sup*] = max(O, min(1, b??[sup*])).

We then obtain the wealth achieved by the best constant rebalanced portfolio as

Multiple line equation(s) can not be represented in ASCII text.

If 0 < b[sup*] < 1, the wealth achieved can be written more explicitly as

Multiple line equation(s) can not be represented in ASCII text.

which simplifies to

Multiple line equation(s) can not be represented in ASCII text.

It is well known that for this model the no-arbitrage price P[subn] of any derivative security with payoff S[subn] at time n is given by

Multiple line equation(s) can not be represented in ASCII text.

where the expectation is taken with respect to Q, the so called equivalent martingale measure on asset price changes. The unique equivalent martingale measure for this market is a Bernoulli distribution on the sequence of "up" and "down" moves of the asset price with the probability of an "up" equal to P[subu] = (r - d)/(u - d) and the "down" probability equal to p[subd] = 1 - (r - d)/(u - d) = (u -r)/(u - d).

We note that for the case of 0 < b[sup*] < 1

Multiple line equation(s) can not be represented in ASCII text.

Therefore,

Multiple line equation(s) can not be represented in ASCII text.

which simplifies to

Multiple line equation(s) can not be represented in ASCII text.

The range of k such that 0 < b[sup*] < 1 is

Multiple line equation(s) can not be represented in ASCII text.

Thus

Multiple line equation(s) can not be represented in ASCII text.

It is useful to note that

Multiple line equation(s) can not be represented in ASCII text.

This implies that

Multiple line equation(s) can not be represented in ASCII text.

and

Multiple line equation(s) can not be represented in ASCII text.

Notice the similarities between these bounds and the expression for V[subn] = 1/H??[subn] given by (3). It is possible to choose r, u, and d so that p[subn] < 1/n and p[subu]((u + 1)/(r + 1)) > (n - 1)/n, in which case the value of the hindsight allocation option is at least H??[subn] - 2.

In summary, the no-arbitrage price H[subn] of the hindsight allocation is given by

Multiple line equation(s) can not be represented in ASCII text.

where the first summation comprises the bulk of the price for reasonable parameter values. The terms appearing in this sum are identical to those in the expression (3) for V[subn] = 1/H??[subn]. The number of such terms appearing in the sum depends on the parameter values. A Reimann sum approximation argument shows that for fixed parameter values H[subn] ~ csquare root of n, where the constant c depends only on the parameters.

<bold> 4.2. Geometric Brownian motion price. </bold> In this section, we give the price of the hindsight allocation option for the classical continuous time Black-Scholes market model with one stock and one bond. The stock price X[subt] follows a geometric Brownian motion and evolves according to the stochastic differential equation

dX[subt] = muX[subt]dt + sigmaX[subt]dB[subt],

where mu and sigma are constant, and B is a standard Brownian motion. Note that here X[subt] denotes a price, not a price-relative. The bond price beta[subt] obeys

dbeta[subt] = beta[subt]rdt

where r is constant and therefore

beta[subt] = e[suprt]beta[sub0].

Let S[subt](b) be the wealth obtained by investing one dollar at t = 0 in the constant rebalanced portfolio b = (b, 1 - b)[supt], where b is the proportion of wealth invested in the stock. Then S[subt](b) satisfies the stochastic differential equation

Multiple line equation(s) can not be represented in ASCII text.

which can be solved to give

Multiple line equation(s) can not be represented in ASCII text.

That this solves (32) can be verified directly using Ito's lemma (see Duffie 1996, Karatzas and Shreve 1991). Notice that, for fixed sigma[sup2] and r, the wealth S[subt](b) depends on the stock price path only through the final price X[subt].

The best constant rebalanced portfolio in hindsight at time T is obtained by maximizing the exponent of (33) for t = T under the constraint that 0 less than or equal to b less than or equal to 1. This results in

Multiple line equation(s) can not be represented in ASCII text.

The wealth achieved by the best constant rebalanced portfolio is then obtained by evaluating (33) at b = b[sup*][subT] resulting in

Multiple line equation(s) can not be represented in ASCII text.

From the martingale approach to options pricing, the no-arbitrage price at t = 0 of the hindsight allocation option with duration T is given by

Multiple line equation(s) can not be represented in ASCII text.

where Q is the equivalent martingale measure or the unique (in this case) probability measure under which X[subt]/beta[subt], is a martingale, and assuming that S[subT](b[sup*][subT]) is integrable under Q, which it is.

It is well known (see Duffie 1996) that under the equivalent martingale measure Q the stock price X[subt] obeys

dX[subt] = rX[subt]dt + sigmaX[subt]dB[subt].

This and Ito's lemma imply that under Q, the expression log(X[subT]/X[sub0]) appearing in the exponent of (33) is normally distributed with mean (r - (1/2) sigma[sup2])T and variance sigma[sup2]T. Therefore, the random variable

Multiple line equation(s) can not be represented in ASCII text.

is standard normal. It can be rewritten as

Multiple line equation(s) can not be represented in ASCII text.

so that, by equation (34),

Multiple line equation(s) can not be represented in ASCII text.

Equation (36) can be solved for X[subT]/X[sub0] resulting in

Multiple line equation(s) can not be represented in ASCII text.

The expectation (35) is then easily evaluated as

Multiple line equation(s) can not be represented in ASCII text.

The first expectation is clearly equal to 1/2, since Y is standard normal. The middle expectation is

Multiple line equation(s) can not be represented in ASCII text.

Finally, the third expectation is

Multiple line equation(s) can not be represented in ASCII text.

Thus (37) reduces to a surprisingly simple form. The no-arbitrage price H[sub0],[subT] of the hindsight allocation option is

Multiple line equation(s) can not be represented in ASCII text.

The price is affinely increasing in the volatility sigma and increases like the square root of the duration T. The dependence on duration matches the square root of n growth of the discrete-time upper bound H??[subn] and the binomial lattice price H[subn]. If the hindsight allocation option payoff is redefined to be S[sup*][subn] (x[supn]) -e[suprT] (the excess return of the best constant rebalanced portfolio beyond the return of the bond) then the price is simply

Multiple line equation(s) can not be represented in ASCII text.

This can be thought of as a premium for volatility.

<bold> 5. Conclusion. </bold> The worst sequence approach to the problem of achieving the best portfolio in hindsight leads to a favorable result: the max-min optimal portfolio strategy for m assets loses only ((m - 1)/2)(log n)/n in the rate of return in the worst case. This yields an asymptotically negligible difference in growth rate as the number of investment periods n grows to infinity. In practice we would expect even better performance, since real markets are less volatile than the max-min market identified here. This intuition is partially validated by the hindsight allocation pricing analysis for the binomial and geometric Wiener market models which indicates that the cost of achieving the best portfolio in hindsight depends monotonically on market volatility.

Acknowledgment.

This work was supported by NSF grant NCR-9205663, JSEP contract DAAH04-94-G-0058, and ARPA contract JFBI-94-218-2. Portions of this paper were presented at CIFER 96, COLT 96, IMS 96.

References

Blackwell, D. (1956a). Controlled random walks. In Proceedings of International Congress of Mathematics, vol. III, pages 336-338, Amsterdam, North Holland.

---- (1956b). An analog of the minimax theorem for vector payoffs. Pacific J, Mathe, 6.

Cover, T. M. (1991). Universal portfolios. Math. Finance 1(1) 1-29.

---- D. Gluss (1986). Empirical Bayes stock market portfolios. Adv. Appl. Math. 7 170-181.

---- E. Ordentlich (1996). Universal portfolios with side information. IEEE Trans. Info. Theory 42(2).

Cox, J., C. Huang (1992). A continuous time portfolio turnpike theorem. J. Economics Dynamics and Control 16 491-501.

Duffie, D. (1996). Dynamic Asset Pricing Theory, Second Edition. Princeton University Press, Princeton, New Jersey.

Huberman, G., S. Ross (1983). Portfolio turnpike theorem, risk aversion, and regularly varying functions. Econometrica 51.

Jamshidian, F. (1992). Asymptotically optimal portfolios. Math. Finance 2(2).

Karatzas, I., S. E. Shreve (1991). Brownian Motion and Stochastic Calculus. Graduate Texts in Mathematics. Springer-Verlag, second edition.

Karlin, S. (1996). Private communication.

Kl??ve, T. (1995). Bounds for the worst case probability of undetected error. IEEE Trans. Info. Theory 41(1).

Larson, D. C. (1986). Growth optimal trading strategies. Ph.D, thesis, Stanford University, Stanford, California.

Marshall, A. W., I. Olkin (1979). Inequalities: Theory of Majorization and Its Applications, volume 143 of Mathematics in Science and Engineering. Academic Press, London.

Massey, J. (1978). Coding techniques for digital networks. In Proceedings International Conference on Information Theory Systems, Berlin, Germany.

Merhav, N., M. Feder (1993). Universal schemes for sequential decision from individual data sequences. IEEE Trans. Info. Theory 39(4) 1280-1292.

Ordentlich, E. (1996). Universal investment and universal data compression. Ph.D. thesis, Stanford University, Stanford, California.

----, T. M. Cover (1996). On-line portfolio selection. In Proceedings of Ninth Conference on Computational Learning Theory, Desenzano del Garda, italy.

Rudin, W. (1976). Principles of Mathematical Analysis. McGraw-Hill, third edition.

Shtarkov, Yu. M. (1987). Universal sequential coding of single messages. Problems of Information Transmission 23(3), 3-17.

----, T. Tjalkens, F. M. Willems (1995). Multi-alphabet universal coding of memoryless sources. Problems of Information Transmission 31 114-127.

Szpankowski, W. (1995). On asymptotics of certain sums arising in coding theory. IEEE Trans. Info. Theory 41(6).

---- (1996). Some new sums arising in coding theory. Preprint.

By Erik Ordentlich, Hewlett-Packard Laboratories, 1501 Page Mill road 3U-4, Palo Alto, California 94304-1126 and Thomas M. Cover, Departments of Statistics and Electrical Engineering, Stanford University, Stanford, California 94305