Thomas M. Cover, Joy A. Thomas. Elements of information theory

Подождите немного. Документ загружается.

16.5 INVESTMENT IN STATIONARY MARKETS 625

Proof: By stationarity, W

∗

, X

,...,X

n−1

) is nondecreasing in n.

Hence, it must have a limit, possibly inﬁnity. Since

∗

, X

,...,X

)



i=1

∗

, X

,...,X

i−1

), (16.63)

it follows by the theorem of the Ces

aro mean (Theorem 4.2.3) that the

left-hand side has the same limit as the limit of the terms on the right-hand

side. Hence, W

∗

∞

exists and

∗

∞

= lim

n→∞

∗

, X

,...,X

)

= lim

n→∞

∗

, X

,...,X

n−1

). 

(16.64)

We can now extend the asymptotic optimality property to stationary

markets. We have the following theorem.

Theorem 16.5.2 Consider an arbitrary stochastic process {X

}, X

∈

, conditionally log-optimal portfolios, b

∗

i−1

) and wealth S

∗

.LetS

be the wealth generated by any other causal portfolio strategy b

i−1

Then S

∗

is a positive supermartingale with respect to the sequence of

σ -ﬁelds generated by the past X

,...,X

. Consequently, there exists

a random variable V such that

∗

→ V with probability 1 (16.65)

EV ≤ 1 (16.66)

and



sup

∗

≥ t



≤

. (16.67)

Proof: S

∗

is a positive supermartingale because



n+1

)

∗

n+1

)





= E



n+1

)

∗t

n+1

∗

)





(16.68)

)

∗

)



n+1

∗t

n+1





(16.69)

≤

)

∗

)

, (16.70)

626 INFORMATION THEORY AND PORTFOLIO THEORY

by the Kuhn–Tucker condition on the conditionally log-optimal portfolio.

Thus, by the martingale convergence theorem, S

∗

has a limit, call it

V ,andEV ≤ E(S

∗

) = 1. Finally, the result for sup(S

∗

) follows

from Kolmogorov’s inequality for positive martingales.



We remark that (16.70) shows how strong the competitive optimality

of S

∗

is. Apparently, the probability is less than 1/10 that S

) will

ever be 10 times as large as S

∗

). For a stationary ergodic market, we

can extend the asymptotic equipartition property to prove the following

theorem.

Theorem 16.5.3 (AEP for the stock market) Let X

, X

,...,X

be a

stationary ergodic vector-valued stochastic process. Let S

∗

be the wealth

at time n for the conditionally log-optimal strategy, where

∗



i=1

∗t

, X

,...,X

i−1

. (16.71)

Then

log S

∗

→ W

∗

∞

with probability 1. (16.72)

Proof: The proof involves a generalization of the sandwich argument

[20] used to prove the AEP in Section 16.8. The details of the proof (in

Algoet and Cover [21]) are omitted.



Finally, we consider the example of the horse race once again. The

horse race is a special case of the stock market in which there are m

stocks corresponding to the m horses in the race. At the end of the race,

the value of the stock for horse i is either 0 or o

, the value of the odds

for horse i. Thus, X is nonzero only in the component corresponding to

the winning horse.

In this case, the log-optimal portfolio is proportional betting, known as

Kelly gambling (i.e., b

∗

= p

), and in the case of uniform fair odds (i.e.,

= m,foralli),

∗

= log m − H(X). (16.73)

When we have a sequence of correlated horse races, the optimal portfolio

is conditional proportional betting and the asymptotic growth rate is

∗

∞

= log m − H(X), (16.74)

16.6 COMPETITIVE OPTIMALITY OF THE LOG-OPTIMAL PORTFOLIO 627

where H(X) = lim

H(X

,...,X

) if the limit exists. Then Theo-

rem 16.5.3 asserts that

∗

= 2

∗

, (16.75)

in agreement with the results in chapter 6.

16.6 COMPETITIVE OPTIMALITY OF THE LOG-OPTIMAL

PORTFOLIO

We now ask whether the log-optimal portfolio outperforms alternative

portfolios at a given ﬁnite time n. As a direct consequence of the

Kuhn–Tucker conditions, we have

∗

≤ 1, (16.76)

and hence by Markov’s inequality,

Pr(S

>tS

∗

) ≤

. (16.77)

This result is similar to the result derived in Chapter 5 for the competitive

optimality of Shannon codes.

By considering examples, it can be seen that it is not possible to get

a better bound on the probability that S

∗

. Consider a stock market

with two stocks and two possible outcomes,

) =









1 − 



with probability 1 −,

(1, 0) with probability .

(16.78)

In this market the log-optimal portfolio invests all the wealth in the ﬁrst

stock. [It is easy to verify that b = (1, 0) satisﬁes the Kuhn–Tucker con-

ditions.] However, an investor who puts all his wealth in the second stock

earns more money with probability 1 − . Hence, it is not true that with

high probability the log-optimal investor will do better than any other

investor.

The problem with trying to prove that the log-optimal investor does

best with a probability of at least

is that there exist examples like the

one above, where it is possible to beat the log-optimal investor by a

small amount most of the time. We can get around this by allowing each

investor an additional fair randomization, which has the effect of reducing

the effect of small differences in the wealth.

628 INFORMATION THEORY AND PORTFOLIO THEORY

Theorem 16.6.1 (Competitive optimality) Let S

∗

be the wealth at the

end of one period of investment in a stock market X with the log-optimal

portfolio, and let S be the wealth induced by any other portfolio. Let U

∗

a random variable independent of X uniformly distributed on [0, 2], and

let V be any other random variable independent of X and U

∗

with V ≥ 0

and EV = 1.Then

Pr(V S ≥ U

∗

) ≤

. (16.79)

Remark Here U

∗

and V correspond to initial “fair” randomizations of

the initial wealth. This exchange of initial wealth S

= 1 for “fair” wealth

∗

can be achieved in practice by placing a fair bet. The effect of the

fair randomization is to randomize small differences, so that only the

signiﬁcant deviations of the ratio S/S

∗

affect the probability of winning.

Proof: We have

Pr(V S ≥ U

∗

) = Pr



∗

≥ U

∗



(16.80)

= Pr(W ≥ U

∗

), (16.81)

where W =

∗

is a non-negative-valued random variable with mean

EW = E(V )E



∗



≤ 1 (16.82)

by the independence of V from X and the Kuhn–Tucker conditions. Let

F be the distribution function of W .ThensinceU

∗

is uniform on [0, 2],

Pr(W ≥ U

∗

) =



Pr(W > w)f

∗

(w) dw (16.83)



Pr(W > w)

dw (16.84)



1 − F(w)

dw (16.85)

≤



∞

1 − F(w)

dw (16.86)

EW (16.87)

≤

, (16.88)

16.7 UNIVERSAL PORTFOLIOS 629

using the easily proved fact (by integrating by parts) that

EW =



∞

(1 − F(w))dw (16.89)

for a positive random variable W . Hence, we have

Pr(V S ≥ U

∗

) = Pr(W ≥ U

∗

) ≤

 (16.90)

Theorem 16.6.1 provides a short-term justiﬁcation for the use of the

log-optimal portfolio. If the investor’s only objective is to be ahead of his

opponent at the end of the day in the stock market, and if fair randomiza-

tion is allowed, Theorem 16.6.1 says that the investor should exchange his

wealth for a uniform [0, 2] wealth and then invest using the log-optimal

portfolio. This is the game-theoretic solution to the problem of gambling

competitively in the stock market.

16.7 UNIVERSAL PORTFOLIOS

The development of the log-optimal portfolio strategy in Section 16.1

relies on the assumption that we know the distribution of the stock vectors

and can therefore calculate the optimal portfolio b

∗

. In practice, though,

we often do not know the distribution. In this section we describe a causal

portfolio that performs well on individual sequences. Thus, we make no

statistical assumptions about the market sequence. We assume that the

stock market can be represented by a sequence of vectors x

, x

,...∈ R

where x

is the price relative for stock j on day i and x

is the vector

of price relatives for all stocks on day i. We begin with a ﬁnite-horizon

problem, where we have n vectors x

,...,x

. We later extend the results

to the inﬁnite-horizon case.

Given this sequence of stock market outcomes, what is the best we

can do? A realistic target is the growth achieved by the best constant

rebalanced portfolio strategy in hindsight (i.e., the best constant rebal-

anced portfolio on the known sequence of stock market vectors). Note

that constant rebalanced portfolios are optimal against i.i.d. stock mar-

ket sequences with known distribution, so that this set of portfolios is

reasonably natural.

Let us assume that we have a number of mutual funds, each of which

follows a constant rebalanced portfolio strategy chosen in advance. Our

objective is to perform as well as the best of these funds. In this section

we show that we can do almost as well as the best constant rebalanced

630 INFORMATION THEORY AND PORTFOLIO THEORY

portfolio without advance knowledge of the distribution of the stock

market vectors.

One approach is to distribute the wealth among a continuum of fund

managers, each of which follows a different constantly rebalanced portfo-

lio strategy. Since one of the managers will do exponentially better than

the others, the total wealth after n days will be dominated by the largest

term. We will show that we can achieve a performance of the best fund

manager within a factor of n

m−1

. This is the essence of the argument for

the inﬁnite-horizon universal portfolio strategy.

A second approach to this problem is as a game against a malicious

opponent or nature who is allowed to choose the sequence of stock

market vectors. We deﬁne a causal (nonanticipating) portfolio strategy

i−1

,...,x

) that depends only on the past values of the stock market

sequence. Then nature, with knowledge of the strategy

i−1

), chooses a

sequence of vectors x

to make the strategy perform as poorly as possible

relative to the best constantly rebalanced portfolio for that stock sequence.

Let b

∗

) be the best constantly rebalanced portfolio for a stock market

sequence x

. Note that b

∗

) depends only on the empirical distribution

of the sequence, not on the order in which the vectors occur. At the end

of n days, a constantly rebalanced portfolio b achieves wealth:

(b, x

) =



i=1

, (16.91)

and the best constant portfolio b

∗

) achieves a wealth

∗

) = max



i=1

, (16.92)

whereas the nonanticipating portfolio

i−1

) strategy achieves

) =



i=1

i−1

. (16.93)

Our objective is to ﬁnd a nonanticipating portfolio strategy

b(·) = (

),...,

i−1

)) that does well in the worst case in terms of the ratio

to S

∗

. We will ﬁnd the optimal universal strategy and show that this

strategy for each stock sequence achieves wealth

that is within a factor

≈ n

−

m−1

of the wealth S

∗

achieved by the best constantly rebalanced

portfolio on that sequence. This strategy depends on n, the horizon of

16.7 UNIVERSAL PORTFOLIOS 631

the game. Later we describe some horizon-free results that have the same

worst-case asymptotic performance as that of the ﬁnite-horizon game.

16.7.1 Finite-Horizon Universal Portfolios

We begin by analyzing a stock market of n periods, where n is known

in advance, and attempt to ﬁnd a portfolio strategy that does well against

all possible sequences of n stock market vectors. The main result can be

stated in the following theorem.

Theorem 16.7.1 For a stock market sequence x

= x

,...,x

, x

∈

of length n with m assets, let S

∗

) be the wealth achieved by the

optimal constantly rebalanced portfolio on x

, and let

) be the wealth

achieved by any causal portfolio strategy

(·) on x

;then

max

(·)

min

,...,x

)

∗

)

= V

, (16.94)

where





+···+n



,...,n



−nH (

,...,

)



−1

. (16.95)

Using Stirling’s approximation, we can show that V

is on the order

of n

−

m−1

, and therefore the growth rate for the universal portfolio on

the worst sequence differs from the growth rate of the best constantly

rebalanced portfolio on that sequence by at most a polynomial factor.

The logarithm of the ratio of growth of wealth of the universal portfolio

b to the growth of wealth of the best constant portfolio behaves like

the redundancy of a universal source code. (See Shtarkov [496], where

log V

appears as the minimax individual sequence redundancy in data

compression.)

We ﬁrst illustrate the main results by means of an example for n = 1.

Consider the case of two stocks and a single day. Let the stock vector for

the day be x = (x

).Ifx

, the best portfolio is one that puts all

its money on stock 1, and if x

, the best portfolio puts all its money

on stock 2. (If x

= x

, all portfolios are equivalent.)

Now assume that we must choose a portfolio in advance and our oppo-

nent can choose the stock market sequence after we have chosen our

portfolio to make us do as badly as possible relative to the best portfolio.

Given our portfolio, the opponent can ensure that we do as badly as pos-

sible by making the stock on which we have put more weight equal to 0

and the other stock equal to 1. Our best strategy is therefore to put equal

632 INFORMATION THEORY AND PORTFOLIO THEORY

weight on both stocks, and with this, we will achieve a growth factor at

least equal to half the growth factor of the best stock, and hence we will

achieve at least half the gain of the best constantly rebalanced portfolio.

It is not hard to calculate that V

= 2whenn = 1andm = 2inequation

(16.94).

However, this result seems misleading, since it appears to suggest that

for n days, we would use a constant uniform portfolio, putting half our

money on each stock every day. If our opponent then chose the stock

sequence so that only the ﬁrst stock was 1 (and the other was 0) every

day, this uniform strategy would achieve a wealth of 1/2

, and we would

achieve a wealth only within a factor of 2

of the best constant portfolio,

which puts all the money on the ﬁrst stock for all time.

The result of the theorem shows that we can do signiﬁcantly better.

The main part of the argument is to reduce a sequence of stock vectors to

the extreme cases where only one of the stocks is nonzero for each day.

If we can ensure that we do well on such sequences, we can guarantee

that we do well on any sequence of stock vectors, and achieve the bounds

of the theorem.

Before we prove the theorem, we need the following lemma.

Lemma 16.7.1 For p

,...,p

≥ 0 and q

,...,q

≥ 0,



i=1



i=1

≥ min

. (16.96)

Proof: Let I denote the index i that minimizes the right-hand side in

(16.96). Assume that p

> 0(ifp

= 0, the lemma is trivially true). Also,

if q

= 0, both sides of (16.96) are inﬁnite (all the other q

’s must also

be zero), and again the inequality holds. Therefore, we can also assume

that q

> 0. Then



i=1



i=1

1 +



i=I

)

1 +



i=I

)

≥

(16.97)

because

≥

−→

≥

(16.98)

for all i.



First consider the case when n = 1. The wealth at the end of the ﬁrst

day is

(x) =

x, (16.99)

(x) = b

x (16.100)

16.7 UNIVERSAL PORTFOLIOS 633

and

(x)



≥ min





. (16.101)

We wish to ﬁnd max

min

b,x

. Nature should choose x = e

,wheree

the ith basis vector with 1 in the component i that minimizes

∗

,andthe

investor should choose

b to maximize this minimum. This is achieved by

choosing

b = (

,...,

The important point to realize is that

)



i=1



i=1

(16.102)

can also be rewritten in the form of a ratio of terms

)



, (16.103)

where

b, b, x



∈ R

.Herethem

components of the constantly rebal-

anced portfolios b are all of the product form b

···b

.Onewishes

to ﬁnd a universal

b that is uniformly close to the b’s corresponding to

constantly rebalanced portfolios.

We can now prove the main theorem (Theorem 16.7.1).

Proof of Theorem 16.7.1: We will prove the theorem for m = 2. The

proof extends in a straightforward fashion to the case m>2. Denote the

stocks by 1 and 2. The key idea is to express the wealth at time n,

) =



i=1

, (16.104)

which is a product of sums, into a sum of products. Each term in the sum

corresponds to a sequence of stock price relatives for stock 1 or stock

2 times the proportion b

or b

that the strategy places on stock 1 or

stock2attimei. We can therefore view the wealth S

as a sum over

all 2

possible n-sequences of 1’s and 2’s of the product of the portfolio

proportions times the stock price relatives:

) =



∈{1,2}



i=1



∈{1,2}



i=1



i=1

. (16.105)

634 INFORMATION THEORY AND PORTFOLIO THEORY

If we let w(j

) denote the product



i=1

, the total fraction of wealth

invested in the sequence j

,andlet

x(j

) =



i=1

(16.106)

be the corresponding return for this sequence, we can write

) =



∈{1,2}

w(j

)x(j

). (16.107)

Similar expressions apply to both the best constantly rebalanced portfolio

and the universal portfolio strategy. Thus, we have

)

∗

)



∈{1,2}

ˆw(j

)x(j

)



∈{1,2}

∗

)x(j

)

, (16.108)

where ˆw

is the amount of wealth placed on the sequence j

by the

universal nonanticipating strategy, and w

∗

) is the amount placed by the

best constant rebalanced portfolio strategy. Now applying Lemma 16.7.1,

we have

)

∗

)

≥ min

ˆw(j

)x(j

)

∗

)x(j

)

= min

ˆw(j

)

∗

)

. (16.109)

Thus, the problem of maximizing the performance ratio

∗

is reduced

to ensuring that the proportion of money bet on a sequence of stocks by

the universal portfolio is uniformly close to the proportion bet by b

∗

.As

might be obvious by now, this formulation of S

reduces the n-period

stock market to a special case of a single-period stock market—there are

stocks, one invests w(j

) in stock j

and receives a return x(j

) for

stock j

, and the total wealth S



w(j

)x(j

We ﬁrst calculate the weight w

∗

) associated with the best constant

rebalanced portfolio b

∗

. We observe that a constantly rebalanced portfolio

b results in

w(j

) =



i=1

= b

(1 − b)

n−k

, (16.110)

where k is the number of times 1 appears in the sequence j

. Thus, w(j

)

depends only on k, the number of 1’s in j

. Fixing attention on j

,we