”THS Illlltlllllllllll c1 COO This is to certify that the dissertation entitled Exponentiated Gradient Portfolios in Continuous Trading presented by Alexander K. White has been accepted towards fulfillment of the requirements for Ph.D Statistics degree in Date December 7, 1999 MSU i: an Affirmative Action /Equal Opportunity Ilulirulion 042771 LIBRARY Michigan State University PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 11/00 www.mu EXPONENTIATED GRADIENT PORTFOLIOS IN CONTINUOUS TRADING By Alexander K. White A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Statistics and Probability 1999 Abstract Alexander K. White In a non-probabilistic setting, with discrete time trading, Helmbold et. a1. (1998) in- troduce the discrete exponentiated gradient (DEG) portfolio. They prove that under specified conditions it achieves nearly the same wealth as the best constant rebal- anced portfolio (bcrp) determined retrospectively from the actual market outcomes. For continuous time trading and a stochastic model, we prove that the DEG portfolio converges to the solution of a stochastic differential equation. Under specified condi- tions this continuous EG portfolio achieves an exponential growth greater than the bcrp, recovering a portion of the additional exponential growth from the best limit of piecewise constant. rebalanced portfolios. These results do not require any prior knowledge of market parameters. Pam Alejandra mi amor, mi alma y mi vida. iii ACKNOWLEDGEMENTS I would like to express my gratitude to my advisor Dr. LePage whose patience and optimism were essential to the completion of this work. I also owe sincere thanks to other members of my committee: Dr. Erickson with whom I shared a great teaching experience, Dr. Levental who taught me probability and introduced me to mathematical finance and stochastic integration and Dr. Frazier the best mathematics professor I have ever known. I would like thank the department as a whole which has given me such a great opportunity and much support through the years. Especially I want to mention Dr. Salehi who has always treated me as more than just a student, Cathy Sparks who makes everything work and Dr. Stapleton who brought me to MSU. Many thanks as well to Dr. Melfi for all his help especially with TeX and my statistics professor Dr. Ken]. I would be remiss if I did not mention the many fellow students who enlightened my stay at MSU. Srikanth Rajagopolan, Alexei Stepanov, Rudolf Blaiek and James Demopolos taught me more than I can say about mathematics and life. Finally I give thanks to my family: my wife Alejandra and daughter Isabel for all their patience and love, my mother Ursula for instilling in me the love of learning and finally my father Roger who told me to take Statistics because then I could always get a job. I only wish my father were here to see the finale. iv Contents List of Figures Introduction 1.1 Setting ................................... 1.2 Discrete Exponentiated Gradient .................... 2 Exponentiated Gradient 3 3.1 Cover’s Universal Portfolio ........................ 3.2 Targets ................................... 4 Example 5 Proofs of Ch. 2 Results 6 Final Remarks vi 14 22 22 26 36 41 62 List of Figures 1.1 The relative entropy function ...................... 8 1.2 Comparison of wealths using NYSE data ................ 13 vi Introduction A fundamental problem in finance is to choose an investment strategy which maxi- mizes wealth. Strategies that require the investor to peer into the future are seemingly unattainable. Cover (1991) proposes to target one such strategy namely the retro- spectively best constant rebalanced portfolio (bcrp). A constant rebalanced portfolio is an investment strategy which maintains a fixed proportion of total wealth in each asset. The retrospectively best of these constant rebalanced portfolios is the one which, for the actual market fluctuations experienced, would have earned the most money. This target varies with time, outperforming the best asset and the value line (geometric mean) index. In discrete time trading without transaction costs and with- out any probabilistic assumptions Cover constructs a “universal portfolio” depending only upon the past asset prices which, in the worst case, grows nearly as fast as this target, losing at most order log(n) in the. exponent, where n is the number of trading periods. Under specified regularity conditions, Jamshidian (1992) extends Cover’s results to continuous time. In the same discrete time context, Helmbold, Schapire, Singer and “’armuth (1998) present a simpler, more market responsive, algorithm which likewise at least achieves almost the same wealth as the best constant rebalanced portfolio, losing at most order \/r_2 in the exponent. This algorithm, here termed the discrete exponen- tiated gradient (DEG) portfolio, employs a multiplicative update derived using the framework introduced by Kivinen and Warmuth (1994) for a problem of linear pre- diction. A key feature is that the DEG portfolio depends only upon the current asset price relatives and the portfolio in the previous trading period (by price relative we mean the inter—period ratio of the price). The universal portfolio, by contrast, de- pends upon the entire past history and is highly computationally intensive. For the continuous time stochastic model usually employed in option pricing we prove that the DEG portfolio does indeed converge to the solution of a stochastic differential equation. This solution, which we call the EC portfolio, under specified conditions achieves at least nearly the same wealth as the bcrp for continuous time. Prior knowl- edge of market parameters is not required. Exploiting the time local nature of the EG portfolio we then examine the class of better time varying targets which are limits of piecewise constant rebalanced portfolios. Our formulas identify market conditions in which the latter earn substantially more than what the best constant portfolio would earn and the EC captures a portion of the exponent of this additional return. We examine market conditions which resoundingly illustrate this point. Chapter 1 develops the continuous time model for the market and the possible portfolios as well as the target strategies whose wealth we would like to approximately achieve. The DEG portfolio is defined and the key results from Helmbold et. al are presented in section 2 of Chapter 1 . All of our main results are presented without proof in Chapter 2. In section 1 of Chapter 3 we examine the universal portfolio and compare its behavior to the EG portfolio. In section 2 of Chapter 3 the behavior of targets and their corresponding wealths is investigated. Examples where the EG portfolio outperforms the bcrp and the universal portfolio are given in Chapter 4. Chapter 5 contains proofs of the main results. Finally, Chapter 6 summarizes these results and discusses possible extensions. Chapter 1 1 . 1 Setting Consider a financial market in which one bond, with price process 5, and d 2 1 stocks with price processes S = (51,52, ..., 5",)“ are traded continuously in the time interval 0 S t < 00, where * denotes matrix transpose. Unless otherwise specified, all processes will be defined for 0 g t < 00. The underlying source of uncertainty in the market is an m-dimensional standard Brownian Motion B 2 (81,82, ..., 8",)" defined on a complete probability space ((2,.7, P). We assume this space is rich enough to accommodate a random variable 5 independent of B. The term “adapted” will refer to the filtration {35 :0 g t < oo} 20({{§,B(s)} : 0 g s g t}UN) where N = {4 E .7: : P(A) : 0}. ‘1 f; The price processes of the assets evolve according to the equations (1,3 : ,Brdt, J (O) : 1 (1.1) and for 1 g i. g m as, = 5,- mt + Zen-dB,- , s,- (0) = 1, (1.2) 1:1 where the real valued interest rate r, the Rm-valued drift a and the m x m matrix valued volatility 0 are. all adapted processes. Let E : 0*0 be the covariance process. In order that (1.1) and (1.2) have well defined solutions, we require that almost surely for each T < 00 we have dt < 00. (1.3) T . m / (1m 23o: + 2..) . 0 i=1 At each moment in time a trader is allowed to shift resources between the various assets. An adapted process which defines the preportion of wealth in each stock is called a portfolio and is formally defined by Definition 1.1. An adapted portfolio is an adapted Rm-valaed process p which sat- isfies the integrability constraint T / (p‘Ep + |()a — rlm)*p| )(lt < 00 (1.4) 0 as. for each T > 0 where 1m = (1,...,1)* E R’". Let P (4) be the collection of all li' dl adapted portfolios taking values in A g IR“. Since for each portfolio p,- reprcsents the proportion of wealth in 8,, we define po = 1 — p"1m to be the proportion of wealth in the bond. Accordingly, when convenient, we refer to the bond as the. “0 th” stock. The wealth process, ll”, generated by a portfolio p evolves as m l i aw = W (pordt + 21),?) . (1.5) 1:1 i By Ito’s formula , dw 1(dW)2 (l log (ll ) I T — i ”,2 ,— 1 : por + p’p — §p*Ep] alt + p*odB b p— 1m 1 = “+— izii——*z L, 2;}? 21) p dt + p’dZ where Z = (Z1, ....,Z,,,) with Z,- = log(/3‘1S,~), i = 1, ...,m represents the vector of discounted stocks. The assumptions (1.3) and (1.4) insure that [3(t) > 0 for t 2 0 and that the semi-martingale, LIV“) in (1.6) below is a well defined process. Definition 1.2. The semi-martingale Ll'l'u’) given by t t t m t . 1 1 Lll(”)(t) 2/ rds+/ ])*dZ+ —/ E p,E,,d.9— —/ p‘Epds (1.6) 0 0 2 . 0 - 2 0 1:1 is the log wealth generated by the adapted portfolio p. We sometimes use the notation Llfis‘t) = LlV(t) — Lil/'(s). We wish to investi- 6 gate the behavior of special portfolios, in particular their ability to generate wealth in comparison to ideal (and impossible) investment strategies that may use future information. We shall refer to these ideal strategies (or their corresponding wealths) as targets. Definition 1.3. A R’” valued process, a, which for all t > 0 t t 1 t m 1 I. Lii"(“)(t): / ”1.5+ / ‘a*dZ+— / Zu,2,,-ds—— / a*2uds (1.7) 0 0 2 0 ,2, 2 0 is well defined andfinite as. is called a target. The process LlV(“) is called the target log wealth. Let T(.4) be the set of all targets taking values in A Q Rm. Any constant marimizing {LWM} is called a best constant rebalanced portfolio (bcrp). Not every Rm valued process is a target. It is well known that Brownian motion is not of bounded variation (and hence neither is Z) and the stochastic integral in (1.7) need not be defined for non-anticipating a. An example is given in Chapter 3. For targets of bounded variation, however, the stochastic integral on the rhs of (1.7) can be defined by “integration by parts” (see Propostion 3.7). Also in Chapter 3, the class of constant targets 70(4) 2 {a E T : at E a, for some a E A} and piecewise constant targets are examined. Let D", = {1: E R’" :23,- 2 0,221,517,- S 1} be the m dimensional simplex. we show for constant targets that argsupueDm {Lil/(“fl always exists but may not be unique. It is important to realize that these targets are continuously trading but are maintaining fixed proportions a,, 1 S i S m in the stocks 5,, 1 g i g Hi. Please note that since it is determined from the actual observed price process the Figure 1.1: The relative entropy function: d(u||v), (u,v) E (0,1)2. bcrp is not an adapted portfolio. In the next chapter we shall restrict our targets and (adapted) portfolios to the simplex Dm which prohibits borrowing and short—selling. By including the reciprocal of each stock in the model as well as a “margin” component we can, however, allow an investor to sell short and buy on margin in a limited sense. See Cover (1991). 1.2 Discrete Exponentiated Gradient The discrete exponentiated gradient portfolio developed by Helmbold, et. a1. is a modification of on-line learning strategies first used in regression. Given an initial value q (k) E Rm which represents the value of the portfolio to be used at time tk, V. Ill maximize: F (p) : nLll'Tp) ) — (1(1), (7%)) (1.8) Uk‘tk+1 where d is a penalty term for straying too far from the initial value and r] > 0 is a constant, which can be thought. to control the rate of response of the algorithm to changing market. fluctuations. They consider various choices for d but focus on the relative entropy defined for a, v E (0,1)m by d (a, v) : 2:011,- log (3). This corre- sponds to the Kullback-Leibler distance between two m + l-dimensional probability vectors. For m : 1 the graph of the relative entropy is presented in Figure (1.1). This graph reveals that d is relatively flat except at the boundaries. This observation trip) will prove useful for bounding terms involving d. Replacing Ll tan-+1 in (1.8) by a first order approximation Helmbold et. al. find a simple closed form solution to a modified version of (1.8). For a bounded stopping time S and a positive constant T > 0 let Part (S,T,A) : {tk,0 3 k S N} be a partition with non-random increments such that S = to 3 t1 3 < tN = 7' and mesh size A : sup {lk+1 — t,C : 0 g k g N — 1}. Definition 1.4. Let f E Dm be .75,- measarable and 7} > 0. The price relatives for the stocks are denoted X,- k : M13}; 2 1, ...,n andi : 1, ...m. and or the bond ‘SI(tA'—l) ' .. __ dlik) . . ,, .,../ , v , - , :. ,.. ,. , .,' .' ' .\0(A) — m. The (..rprrssion DEGM, E), Z.(:.. discrete (.J.])()7L(:.7Lll(ll£‘(l gradient, will dl denote the portfolio with (lilo) ’—‘ €~ (1.9) TIXz' (If) (1 (tk_1)‘ X (A?) + (10 (’k—1)X0(k) (hit) 2 (12(fk-1)(‘XP{ }l’;la tk S t < tk+1 wh ere ’ m 71X, ([1) } l" : i t CK * r k gr] (k) p {q(tk_1) X (k) + (10 (tk—l)1\0ikl 71X0 ([9) } (I (tic—1y X (k) + Goitk—1)X0(k) +(10 (tit) 9X1) { is a normalizer which ensures that q E D,,,. Although suppressed in the notation, the DEG portfolio depends on the choice of 77 and the trading times (1.0. the partition). To see how the DEG portfolio works notice that q (tk_1)* X (k) + (10 (tk_1) X0(k) is the wealth growth obtained over the interval [tk_1,tk) by managing the assets according to q (tk_1) at tk_1 and holding them until tk. The portfolio is then updated at time tk according to the ratio of the price relative X,(tk) to this wealth growth. If holding the ith stock would have made a lot money relative to what we just. made previously using q (tk_1) we increase the amount of money invested in the stock. The greediness parameter r} determines how sensitive our algorithm is to shifts in the price relatives. A key result from Helmbold et.al. is restated below. Let i = (X0,X*)* and 10 A» q 2 (q0,q*)*. By (1.3) the price relatives are positive. If we only trade at the time points tk the log wealth generated by the DEG is El log (q *(tk).X (t0). Theorem 1.1. (Helmbold, Schapire, Singer and Warmath, 1998) Let u. E Dm+1 be mink‘, .\',(t),.) constant and , mardeJUk) 2c>0. Forn>0, 7] Zlog (6*(tk) )3I( (tk )—) Zlog (C‘u .X(t (k)2) —W — 37):]; (1.10) k Furthermore, if q(t0) 2 (m + 1)—11m+1 and we set 7) 2 2c\/2log (m + l) /n then we have Zlog (crak) .\( (tk)—) Zlog(u*X (13)) 2 ——‘/27110g(m+ 1) (1.11) 20 k The left hand sides of (1.10) and (1.11) represent the difference in log wealth between the DEG and an arbitrary it constant target a through n trading periods. Therefore they have found a lower bound on the performance versus the non-adapted best constant rebalanced portfolio determined retrospectively from the observed price processes. We note for future reference that their bound, due to its dependence on the square root of the number of trading periods, must be modified if we are to extend this result, through rapid trading, to continuous trading. It is important to mention that in their work Helmbold, et. al. do not assume any probablistic model and prove that (1.10) and (1.11) hold generally for any sequence of positive price relatives satisfying the boundedness constraint. In a market with exponential growth and A 2 1, then it 2 T — S and by (1.11) the ratio of wealth generated by the DEG to the wealth 11 generated by the bcrp is of the order (W (7—5). Hence the DEG is capturing at least the first order exponential growth of the bcrp. From (1.11) we can see that a good choice of I] is of the. order 7) 2 (r — S) i. In Theorem 1.1 it. is assumed that the ratio of the maximum price relative to the minimum price relative is bounded. In their paper they are able to remove this assumption for a modified version of the DEG and an expression similar to (1.11) but weakening the bound to order (T — S)? These lower bounds for the DEG vs. the bcrp are weaker than Cover obtains for the universal portfolio vs. bcrp. We shall see, however, that the DEG, perhaps because it responds more readily to market fluctuations, can under specified condi- tions outperform the universal portfolio and even the bcrp, whereas a result from Jamshidian proves that the universal portfolio exhibits the same exponential growth rate as the bcrp. Helmbold et. al. performed experiments with the few specific ex- amples of actual data from the New York Stock Exchange accumulated over a 22 year periodwhich first appeared in Cover (1991). In these experiments the DEG portfo- lio outperformed the buy and hold strategy for the best stock and Cover’s universal portfolio and achieved only slightly less wealth than that achieved by the bcrp. See Figure (1.2) which is reproduced from their paper. 12 200~ BCRP —— EG --------- Universal ---------- 15° ' Best stock — _ 100 - {'5'»: ‘ 1 r” - if! i , fiffifl 1:13,. 50 '- £53., ':‘:':' \‘ q /‘ 5': 3... Hr" 90;. ,Wtfia. 4‘” .\ WWW-~wgh.“ My: "‘ o .- cl 0 1000 2000 3000 4000 5000 Figure 1.2: Comparison of wealths achieved by the best constant rebalanced portfolio, the DEG portfolio, and the universal portfolio. The market consists of Commercial Metals and Kin Ark. The wealth achieved by the EG portfolio is close to the wealth of the bcrp and exceeds that achieved by the universal portfolio. 13 {Til Chapter 2 Exponentiated Gradient For clarity of exposition no proofs of the results are presented in this chapter. Proofs of all results may be found in Chapter five. It is not a-priori clear that the DEG portfolio has a continuous limit or that the limit will exhibit the same good properties as the discrete portfolio. In particular one looming difficulty, which we must overcome, is the presence of \fli in the right hand side of (1.10) which makes it appear that the bound blows up. In this chapter we manage to extend the DEG portfolio to continuous time trading and present results describing the wealth achieved in comparison with constant targets and limits of piecewise constant targets. We now establish the continuous version of the DEG by letting the mesh size A —> 0. Before we can find the continuous limit of the DEG we need the following: Theorem 2.1. Suppose [Ar and E are 7-] adapted processes which satisfy (1.3), S is a bounded stopping time and{ E R’" is .75 measurable. Let 7) be an adapted 1R+ 14 valued process such that for each t > 0 t m. / [Mrl + Z (In/1.2:] + 022,0] (13 < 00 (2.1) . 0 i21 almost surely. There crisis a unique strong solution {a'(S,t),t 2 S} E R’" to the following stochastic differential equation 1 do, I UdZi + T] E23,,- _ Elf-((14 dt (2.2) with initial 0' (S, 0) 2 E and where f : Rm ——> Dm is given by m —1 f,(a) 2 ea (14—23(20)) , i21,...,m. (2.3) j=l Using the process a we define an adapted portfolio which continuously updates. Definition 2.1. Let oz(S, t) be the solution to the stochastic diflerential equation (2.2) with initial condition a(S, S) 2 E 6 7:5 and 77 > O as in Theorem 2.1. The Dm valued process 7r(t), t > S, defined by m —1 7r,- 2 8‘” 1+ E ea] , i 2 1, ...,m 1:1 is called an ezponentiated gradient with learning parameter process 77 with starting time S (or EG(7).S)) portfolio. The corres )ondin amount invested in the bond is 7T 2 1 + I": 801' —1. Since log 5 2 a,- we see that the EG portfolio places more money in the ith stock where 770 15 the discounted stock value, Z,- increases. Theorem 2.2. Suppose that r is a positive constant, S, T are bounded stopping times with O < T — S g T and I] > 0 is constant. Under the conditions of Theorem 2.1 the DEG(I)) portfolio q converges uniformly in probability to the EG(n) portfolio 7t and the Lil“) converges uniformly in probability to LIV”) on the interval [5, T]. Although in Theorem 2.2 we see that the 7T is the limit of q, we cannot use Theorem 1.1 to evaluate the performance of it since the bound in (1.10) increases with the number of trades n. which tends to 00 as the mesh size is decreased. The following continuous time counterpart of Theorem 1.1 resolves this question. In effect trading rapidly (i.e. over small increments) involves price relatives close to one and produces an identity, rather than lower bound, in the limit when we keep track of all terms. Stochastic calculus facilitates the bookkeeping. Theorem 2.3. Let 7) > 0 be constant. For any bounded stopping times S and T with 0 < T — S g T and any non short-selling constant target it 6 7-0 (Dm) the EG(77,S} portfolio 7r satisfies .. 1 'T . T Lil/[grin—LI-i’[(s.l1.) : — / (rt—u.) E(7r—u)dt+fl / n‘Eirdt ’ 2 S 2 S (2.4) 77 T m d(UHTFCTD-a’r('U«l|7T(S)) l Zr 2,,dt + i=1 77 Comparing (2.4) to (1.10) we see some similarities and many differences. First. of all (2.4) is an identity which retains and gives meaning to terms discarded in (1.10). 16 d(u||7r(S) The two negative terms of( 2. 4) )are ——ngTZl_"17r,-E,~,dt and ),only the second of which appears in (1.10). Using the fact that 7r 6 D", we can see that the term —1 [3271173Endt is the counterpart of— —;"2 in (1.10) . The intuition here is that both terms measure the total variation in stock prices over time. The positive terms 5 15W — 2(7r —— u) dt and —"H—;(—)—) of (2.4) are large if u is distant from 7r. This may seem paradoxical but, as we shall learn, the EC can do well against non-constant targets where the bcrp does poorlv. B37 noting that (l(u|| m) g log(m + 1) we (1+1) get Corollary 2.4. Let S = 0, M > 0 and TM 2 inf{t > O : maxifot 2,,- ds = A1}. Choose 7] = (lg—13i- then the EGM, (l) portfolio 7r with 7r(0)— — T—nilflm satisfies 1 T , Ll"(1[52) — LIVE”; 2 5/ (7r - u) 2(7r — u) )—dt \/2log(m+1)m1l1 s for each constant target u. And sup ”g{ fol 2’": 7r 2,, dt + (“HUN“) )————-—)} S \/2 log (m +1)ml\/I. (2.5) 77 The stopping TM is a measurable function of the paths of the stock price process (see Lemma 5.2.) Hence for a specified level of variation M, and the above choice of n, the contribution of the negative terms to (2.4) up to stopping time TM is no greater than square root of the variation. In a reasonable market the wealth of the bcrp exhibits exponential growth on the order of the variation (see Proposition 3.3 and the following discussion, for details). 17 As in the discrete case the EC portfolio is at least capturing the first order exponential growth (if there is any) of the bcrp. This idea is made more precise in the following corollary. Corollary 2.5. Let s = 0, M > 0 and TM _—. inf{t > 0 max,- 1;; EMS: M}. Choose 1] = ”W then the EG/I], 0) portfolio 7r with 7r(( )) : (fl—1:171," satis- fies (u ) [97111) >0 LlfllllST-u) LW"r Ln (" l [W (Art) (2.6) Ill whenever Ll'l'[(s.i)) : 0(maxi I; 2?,- (1.9). In Theorem 2.3 and 2.5 we employ a constant learning parameter and compare with a constant target. In the following generalizations of Theorem 2.3 we allow both to vary over time. First we define a very general class of targets. Definition 2.2. A target u E T is called piecewise constant if there exist a finite sequence uk 6 R'", k : 1,...,N and a (possibly adapted) partition S = to 3 t1 g - S tN : r such that N—l Ht 2 2 uk {lk S t S tk+1}. [(20 Let 7”" (A) be the set of all piecewise constant targets taking values in A g R’" and let TWA {—116 7'( (4) 311,6 7'”"(.4) 3a,, —>u._LIrl"l”") —>,, Lit-111)} 18 where the convergence is uniform in probability. To compare performance against piecewise constant targets we generalize Corol— lary 2.5. Suppose u E 77’“ is a piecewise target with one jump at stopping time T > S. For t > T, using Theorem 2.3 on the two subintervals (S, T) and [T,t) we have almost surely it 1 t 1. t HITS?) — Ll’lfsi) : —/ (7r— v) Z(7r—u)ds+ 2/ n‘erds " " 2 s 2 s T m > d A t t —d T— T _2/ 2mm, ) (u( )ll7r( )) 2 3 i-l 7) +d (u. Hr (2o) -— d (u (5) Hit (5)) 77 Comparing with (2.4) we see an additional term involving the difference in the relative ' entropy at. the jump point. Hence using the inequality (1(qu) g maxosigm {— log(v,)} we can generalize Corollary (2.5) to the case where we allow the target to have a finite number of jumps. Corollary 2.6. Let u E 77’“ be a piecewise target with n jumps. Let S = 0, AI > 0 and TM = inf {t > 0 : max,- [52,,(13 = 111}. Choose 7) = m—QAT then the EC{7},0) 1 I m 1m SGLZSfiCb portfolio it with 7r(0) . ... 1 T . LI/Iv’fiotg) — Llr’lflojl) 2 2 / (7r — u) 2 (7r — u) dt ‘ 0 ' I! — Té—(l+nI\”+log(m+1)) where K = max,- SUPo ' 4 — ' D ' m ' Tl , interior of m i.e. for a t _ 0 at E 1 — {u E m . 2,2111,- < 1,11,- > 0}. zen u E T(D,,,), i.e. up to time t the process a generates finite wealth. And for I} > O 20 constant and the EG/n) portfolio we have '1‘ r _l V 3 l m T ui A (1‘11; — Tl ((l((l(TlllH (Tl) _ ( (11(S)H7T(S)) _ 215 [10g (2;) — (1,] (In) . The final result of the chapter gives conditions under which the EC portfolio can perform as well as smooth targets. As we have seen above the key restriction is that the portfolio must. stay away from the boundary. Theorem 2.9. Let u be as in Theorem 2.8 with [000 d|u| : K. Let S = 0, ll! > 0, C > 0 and log(fl) 7T0 t Tm”) : inf {t > 0 : max/ Eli-d3 = Mormax I 0 l =6} Choose 7) = 2 W then the EC(I},0) portfolio 7r with 7r(0) 2 ml,“ satisfies 1 T ,7 T —/ (7r — u)" 2 (7r — u) dt + —/ 7r‘27rdt 0 2 0 3,1477) _ ”4“) L L [0,71 Mn) 2 [0‘77 Mel) IV (2.9) mlW —2 l ' 1 .111 — K . \/og (m + )m c \/4log(m +1) 21 Chapter 3 3.1 Cover’s Universal Portfolio Cover’s universal portfolio, introduced in 1991, uses an averaging method to pick the portfolio. The portfolio vector used at time t is the past performance weighted average of all constant portfolios. Cover and Ordentlich (1996) introduce the notion of side information and generalize Cover’s algorithm by using the Dirichlet(%, ..., %) and the Dirichlet(1,...,1) priors over the set of all portfolio vectors, i.e. f0... pil/Vipl (t) (M Ai f a I) ( ) f0," w/(p) (t) (M i=1,...,m (3.1) where /\ is one of the Dirichlet priors mentioned above. In discrete time trading, Cover and Ordentlich prove that under no assumptions on the price relative vec— tor (except non negativity) the Dirichlet(%, ..., %) weighted universal portfolio, in the worst possible case, grows nearly as fast as the bcrp losing at most 525’ log(n) in the exponent where n is the number of trading days and m is the number of stocks. Using a recursion scheme they can compute the portfolio on-line with storage requirements 22 growing like n’"‘1. Employing the model (1.1) and (1.2), Jamshidian (1992) extends Cover’s original portfolio to continuous time. He assumes that the following limits exist E [[5 Eds] V00 2 lim 2 ————-, 1/ : 11m t—mo , t—+oo (3.2) and sets poo = V°° + %Zf,-°. Under these conditions there exists an asymptotically optimal constant portfolio p°° which is determined by 1 poo : argmaxpEDm {If‘MOO _ Epmzjoop} , (3.3) Stock i is said to be asymptotically active if pi” > 0 and a market is asymptotically active if all assets are. Jamshidian’s main result is Theorem 3.1. (Jamshidian) If the market is asymptotically active then m 2 log(t) + C . 1 Lit/(ma) — LWW) ~ log(m!) + i log([ZOOD where Lllr’(’3)(t) is the wealth generated by (3.1), Ll’l”l is wealth generated by the bcrp, |E°°| is the determinant of the asymptotic covariance, C > 0 is a constant independent oft and 230° and the notation X(t) ~ Y(t) means X(t)/Y(t) converges to 1 in probability. Jamshidian proved a similar result in the case where the market is asymptotically k—inactive ( pr : O for k of the m stocks) in which case the bound on the rhs is of the 23 order flf—k— log(t). The bound achieved in Theorem 3.1 is superior to the one we obtain in Theorem 2.3 for the EC portfolio. Just as in discrete time, in comparison with the wealth generated by the bcrp, Cover’s algorithm loses at most. on the order 1271 log(t) in the exponent while the exponentiated gradient method loses at most on the order of log(m)\/t. However, as seen in Corollary 2.6 and Theorem 2.9, the exponentiated portfolio can perform well versus better non constant targets where Cover’s algorithm tracks the bcrp. Furthermore the EC portfolio is far simpler computationally than the universal portfolio]. The following proposition gives conditions under which the EC portfolio will out- perform the universal portfolio. From (2.4) we see that EG portfolio will exhibit especially good growth whenever 7r differs from the bcrp sufficiently so that the term %f (7r — vul)* )3 (7r — ul) dt is large, e.g. on the order of max, f2,,;dt. One expects this to occur in cases where the drift coefficients oscillate. See the example presented in Chapter 4. Proposition 3.1. If ant) > 0 for alli = 1, ...,m then ‘ 1 t :t t Lw,<;3, — Luff?” = — / (7r —u*) >3 (r—ul)dt+ 3 / 7r*27rdt .. ,. . , 2 S 2 S _g [tire-Zach + d (UTHF (T)) _ d (“in7r (5)) 5 i=1 77 t / Eds 0 where Ct : log(ffh exp {— “I”? } d1?) 3 1’23 log(7) with A, = Zi(Dm — til). 2 1 — log(m!) + Elog( ) — Ct 1Although it is adapted, given the computational requirements for discrete time especially for large m. a continuous implementation of (3.1) may not be feasible. 24 For n and TM are as in Corollary (2.4) and (l < c < I suppose that , r ‘l/ (7,— — ul)‘ 2 (7r — ul) ds — \/max/ Earls = 0ft") 2 0 ' 0 as t —> 00 and the market is active for all time t > S. Then for AI sufficiently large '(N) , .r( ‘) - c. S , '1 in Proof. In the proof of (3.1) Jamshidian compares the log wealth obtained by (3.1) and a)f as . '(m ,r(u*) _ , 1 Lll (t) — LII (t) — log(m!) — §10g( t / Eds 0 The first result follows by combining the above with Theorem 2.3. The second result ) + Ct. (3.4) is a direct consequence of Corollary 2.4. D The relation (3.4) demonstrates that under rather general market conditions the universal portfolio obtains the same asymptotic exponential growth rate of the bcrp but never better, even in cases where the bcrp does not perform so well. In fact in an active market where the variation tends to infinity, the wealth generated by bcrp is asymptotically infinitely greater than that of the universal portfolio. In Chapter 4 we present an example of a market with oscillatory drifts where the EC portfolio decidedly outperforms both the. bcrp and the universal portfolio. 3.2 Targets In chapter 2 Theorems (2.3) and (2.7) relate the wealth acheived by the EC portfolio to that of the bcrp and limits of piecewise bcrp respectively. In this chapter we examine the wealth generated by such targets. We exhibit examples of reasonable markets where the wealth achieved is quite large. A simple example of rebalancing To appreciate the power of constant rebalancing consider a simple two asset model presented in Helmbold, Schapire, Singer and Warmuth (1998). There is one risky asset or Stock whose value is halved on “down” days and doubled on “up” days. And one risk-free asset with zero growth rate. Suppose the relative returns of the stock 2, %, 2, ..., %, 2 and the relative returns of are a random permutation of the sequence 5, the bond are 1, l, ..., 1. If given a dollar, an investor buys the stock and holds on to it. the wealth for entire period can at best double. However, if the investor constantly rebalances to one-half of the total wealth each day in each asset, then on the “down” 3 c n = 5' On the ‘up days the relative wealth decreases by a factor of % X 1 + % x % 1 days the. relative wealth grows by 5 x 1 + % x 2 = %. Thus pairing an “up” day and a “down” day the investor’s wealth grows by a factor of 43 x g :: g. Hence without any prior knowledge of the ordering of the {s and 2’s (or even which asset is the n . bond) the wealth after 2n days grows by a factor of (g) . Therefore, even 111 a flat or oscillatory market, constant. rebalancing can be used to achieve exponential growth. 26 The BCRP Let 9,-(t) = Z,(t) + [0’ Suds for i = 1,771 and t 2 0. By (1.6) the log wealth growth 1 2 obtained by constant :)ortfolio vector u E R’" over the interval s r is ( uadratic in . 3 T 1 T LII-'63) : / rdt + u‘d — 2M (/ Zdt) u (3.5) and is maximized by any a satisfying T -1 n = (/ Edt) 0 where (f3T Zdt)~1 is a. generalized inverse of j: Edt. The log wealth growth produced by such a u is r T -1 Ll’lv'(“i) (T) = / rdt + éf)’ (/ Zdt) 9. If the covariance matrix f; Zdt is non-singular we denote the (unrestricted) retro- spective best constant target by val. We now restrict to the simplex Dm. The bcrp is for the interval [5 r] 1 m T 1 T v1 : argsupueom u‘Z + ~2- 2:114" / Ziidt — in“ (/ Zdt) u (3.6) i=1 ' s S The wealth achieved by "ait clearly exceeds the arithmetic mean, the geometric. mean and the maximum of the assets in the market. For the following definition we use the 27 interpretation that the bond is stock 0 and consider bcrp over the interval [0, t). Definition 3.1. Let (1.1(t) be the bcrp. A stock i is active at time t if of(t) > 0. A stock is asymptotically active if lim inf, of(t) > 0. A market is (asymptotically) active if all stocks are (asymptotically) active. A market is (asymptotically) k-inactive if exactly k stocks are (asymptotically) inactive. The following proposition from Jamshidian describes aI in terms of market activity. Proposition 3.2. (Jamshidian,1992) Assume fot Eds is invertible. At time t Z 0 o A market is active if and only if of(t) > 0 for each i. In which case a1 : al. 0 Define the m — k vector it“) to be the solution of "l t Z 211(k) [/ 211(13] =0}, k+1§j§m. 0 l=k+1 The market is k-inactive if and if afk) > O for k + 1 g j S m and then In particular in the m = 1 case vi = 0 V ul /\ 1. Using Proposition 3.2 we can find a. lower bound for the wealth generated by the bcrp. 28 Proposition 3.3. Suppose the market is k-inactive for k < 772.. Let /\ : (A1, A2, ..., A771)!“ . . -t . be the eigenvector process of the covariance )0 Eds with /\1 2 A2 - -- 2 Am. The log wealth generated by at is bounded below by t t 1 LII/"(n ) (t) Z / rds + 5A,nu.i*ui. 0 Proof. Suppose Am : 0 then the result trivially holds since it1 beats the bond. Assume "l t . . . /\,,., > 0. Let A 2 (f0 Eijds) be the covariance submatrlx corresponding to iJ:k+1 stocks k+1, ..., m and define the m—k vector u = (uch, ..., ufn)*. Then by Proposition 3.2 the log wealth is the quadratic form -t 1 Ll/l7("I)(t) = /rdt+§u*Au 0 t t 1 1 2 / rdt + /\,,,—u*u = / rdt + Am—ufmf 0 2 0 2 where the inequality follows from the basic result about quadratic forms and the last equality follows from the fact that the market is k-inactive. El From Proposition 3.3 we see that if the interest. rate r is non-negative, and limt Am //\1 > e for some 6 > 0 then LII/’0”) (t) will grow exponentially on the order of A1. 29 Targets in Two Asset Market In this section we further examine the nature of targets restricting ourselves to the m = 1 case. To avoid issues of degeneracy, we assume throughout that o > 0 00 " . . for almost. all t and that f0 ozdt = 00 almost surely. Define the stopping tlme . T ‘ . . . T(s) :: inf {r > 0 : f0 ozdt > s}. By our assumptions on o, T 1s 1-1 and onto With T 2~ _ ‘ T(s) _ . . . s(T) 2 f0 0 dt, hence B, 2 f0 (NIB, 0 g s < 00 IS a Brownlan motion (see Karatzas and Shreve pg 174). Proposition 3.4. Let [000 ogdt : 00 almost surely. The stock is asymptotically active if and only if I. lim inf I” (H — T) (18 .t , HOG )0 aids almost surely. Proof. In this case the bcrp is t —1 -t t of = 0V (/ ogdt) (/ (u — r)ds +/ odB) /\ 1. .0 0 0 By the law of the iterated logarithm t lim (/ o2dt) t—>0 0 So lim infui > 0 if and only if lim inf, 11);} > 0. 1:1 0 0 8 -—l t / odB = lim s‘lBs —~> 0. .0 8—900 30 The next proposition shows that if ,u < r the bcrp wealth is essentially equal to the bond. Proposition 3.5. If almost surely p, < r, fox 02dt = 00 and [J rds = 00 then uI —> 0 and Luv/'(“ho —_,———— —; 1 f0 rds almost surely as t —> 00. Proof. By proposition 3.4 uI —> 0. Since u1 must be in [0,1] the corresponding log wealth is bounded above and below by -t t. t t / rds S Ll’l*'(”i)(t) g / rds + (2/ 02ds) (/ odB) 0 0 0 . 0 I I —1 2 I g o o o — ~r But. for s : 10TH) ozdr, (for aids) (f; odB) 18 equal in distrlbutlon to (s) 1B: —-1 2 . -1 2 which follows a X2 distribution. Hence (ft; 02ds) (f0! odB) is finite almost surely and its distribution does not depend on t. Therefore (2 fo'a2ats)_1 (fo‘ odB)2 [Qt rds —~>0 almost. surely as t ——> 00. E] The following proposition shows that. piecewise constant targets can generate very large wealth. In the proof we exhibit. a sequence of piecewise constant targets whose wealth tends to infinity. The argument takes advantage of the unbounded variation 31 of Brownian motion. Proposition 3.6. Firt > 0. if)! 2 r 2 0 then sup {Ll'l"”(t) : u E 7"” (D,,,)} 2 00. ‘f 2t S . . . Proof. Let .«V > 0 and A : 1"}?!— and conslder the random part1t10n {tk = T(k_\) : k = 0, 1, N} where T is the time change given above. The bcrp over the. interval [tk_1, tk] is if. . ‘1 tk tk a; z: 0 V / ozdt / (,Li — r) dt +/ odB /\1 tic—1 tk—l tk_1 and hence on the event uI : 1 the log wealth generated is (“3) [k 1 fl: . tk Lil’mfm) : / ,udt— 2/ ozdt+/ odB tk—l tk—i lk—i 1 tk hr 2 —"—/ U2dt +/ OdB 2 tic—1 tk—i 1 ~ where 33,. : BM — B(k_1)._\ are Brownian motion differences and the inequality follows from the assumptions on ,a. On the event uI < l the log wealth is (at) ‘k 1 2 ‘k . Lulttfhtk) : / rdt + 5 (at) / ozdt Z 0. t 1 tIc—l Since ,a is non-negative ABk > A implies that u: > 1. So if we knit together the bcrp‘s. define a. piecewise constant. portfolio by u : vi on [tk_1,tk), k = 1. N we 32 obtain a log wealth of at least N - 1 - LII-'(“l(t) 2 Z [213,c — 33[ (5.8,. > A} k:1 “ A7 2 2A3. (413,. > A} — t/2. k:1 Finally ABk {313k > A} are. iid with expected value: E [Age {Age > A}[ = /00 fix“ (~33)drr A , :1: where the inequality follows from Taylor’s formula. Hence by the law of large numbers . . 1 ~ A8,. 1 llman—l— AB >1 >——. 1 VA: k{ A }T \/27r But N‘lfi : i; —+ 0 almost surely hence ZABk {93% > 1} ——> 00 as A ——> 0. Therefore limAaO Ll'l"(“l(t) = 00 almost. surely. [:1 From the previous proposition we see that there exist limits of piecewise constant targets which produce infinite wealth in finite time and hence are not targets. The problem is that if we view the bcrp as a function oft it is not continuous at I). For example if we assume ,a = r and o = 1 then the bcrp is u[ = O V t—lBt /\ 1 and by 33 the law of the iterated higarithm we get lim sup u} = 1 and lim infu,— — 0. t——>0 ” tat) In the following proposition we prove that smooth processes are targets (i.e. do not produce infinite wealth in finite time). Proposition 3.7. Any process with the paths of bounded variation is a target. Proof. We must show that it generates at most finite wealth at each time 0 g t < 00. Fix t > 0, let {tkm : 0 g k g n} be a sequence of partitions of [0, t] with mesh size converging to 0. Define the 1.)iecewise constant target un : u(tk,,,) on [tk_1;n, tkm) for 0 g k S n. From (1.7) the log wealth kzn LL‘,’(Un) : f0 rds—l—kth (”utk." )/ t(k— l):n +21 1(tk.,,) )[tlm odB ttk— l):n 1 tkm ‘ (p, — r) dt — —u2(tk,n)/ ozdt 2 (k l) n By (1.3) the first term on the right hand side is finite. From (1.3) we have that the . . t t . . . time integrals f0 (u — r) dt and f0 02dt are continuous and have bounded variatlon and we have assumed that u is bounded. Hence the second term above converges almost surely to the difference of finite integrals fot u (p. — r) )dt — — ifo u2 o2dt as n ——> 0. By 34 summation by parts we obtain n .(km 72—] tkzn t ulfkm.) / (NIB : Z (NIB (u,(tk;,,) — u(fk_1:,l)) +21.(t_)/ odB kZl ' "(k—l):n k:l - 0 0 11-71 —u(1‘—)/ (NIB 0 I s it ——> //odBda+u(t—)/ (NIB .0 0 0 where the convergence follows since u is of bounded variation and the stochastic integral is continuous. El Chapter 4 Example We consider markets where with probability arbitrarily close to 1 the EC portfolio outperforms the bcrp and Cover’s universal portfolio by order of t in the exponent, and where each earns order t in the exponent. The idea of the example is simple. Take a drift value so that the best piecewise constant target. for one half of the interval is very near one and for the other half is very near zero. So the best constant for the entire interval is near In this oscillatory market we expect 7r to track the l 2. piecewise constant target and so the f (7r — %)202dt term in (2.4) is large. On the other hand the universal portfolio will perform approximately as well as the bcrp, which is earning less in this market. Definition 4.1. For m = 1, we call the qnadruplet (r,,u.,o2,T) Model 1 if r = 0, o > 0 is deterministic constant and o2 forOSt 1 — 3(1) (—CE\/T) with c = o /\ g and where (I) is the (r'zmiulative distribution function for the standard normal distribution. Proof. The piecewise constant target which takes the best constant value over each of the interval [0, T] is given by 0V1+2—§—./2]/\1 for0§t<§ L U u: _ 23—3,... . 0V_(_7‘(TT_’/_-l]/\1f0r%£t$T ()n the other hand. the best. constant target over the entire interval [0, T] is /\1. 1 3. 120V _ _L n [2+0T So for large T we see that u is nearly one on the first. half of the interval and zero on the second half while u1 is essentially i' 37 From Tl‘ieorem 2.3 with 7] : T“i and 7r((‘)) 2 % we get. 4-.) '(u) 1 {IV/2 2 2 -11 t 2 Lil [Of/2) — Lll [or/2) : §/ (7r — u) (7 dt — T '2—2— / 7r(1— 7r)o 0 .0 +Ti (d(u(o)||7r(T/‘2)) — (l(u(())||1/2)) 1 T/2 . l 5/ (7r — u)202dt — KT? (4-1) 0 IV where K = (% + lot/(2)). Applying the general expression for log wealth (1.6) to our special model we get (2!) (7r) 1 2 W2 2 772 ”2 2 Ll’l'wjfl) — LulUKI‘fl) :2 5a (0)]O 0 dt +/0 (E— -— 7r) 0 dt T/2 — / nodB 0 1 T/2 ' . T/2 : —/ (7r — u)zozdt —/ 7r (1 — u.) 02dt 0 0 ‘2 T/‘2 — / nodB 0 Hence on the event A’ = {Br/2 > —T60 and [OT/2 nodB < g} T/2 T , '(u) r(7r) , 2 2 2 Lil [Of/.2) — LH [0,T/2) 2 5/ (7r — u.) 0 dt — —2—eo . 0 Hence by (4.1) on A' we have "7‘2 . . T . 1 / (7r — u)202dt < 3602 + KT? 0 Now we compare with 7.11. Let A" = {Br 3 \floT} then on the event. A : .4' D A" 38 we have. T” .. . 1 "”2 1 . . 1 '17? 1 ,_ . / (7r — '11:)“0 (It 2 — / (1 — —)202dt — —/ (— — nifazdt 0 0 9 2 0 2 (QM--A ‘2, .. 1 .7/2 ‘ . 1 772 . 4 _§ / (u — 1)202(1t — 5/ (7r — u)202dt . o 0 1— 8 (f + (2) .2 K 1 > T — —T5. 4.2 - 16 a 2 ( ) Using Theorem 2.3 once more but with the best constant target on the interval [0, T] ‘2 +T% nw> — d||1/2)> T021—8(€+62) 16 1.11"”) —LII'("I) — l/T(n—ui)202dt— ”ll/Tn(1—7r)02dt ,. or) _ O . , 2 0 , , — Kgri (4.3) IV , _' ' 3| 2 . . . . . on A’fl A" and where 112 = (% + —0—§(-l). Slnce the market 18 active by Proposmon (3.1) we have ' 7T .' i . 7r . ‘ 1 Law.) — Lu [(3) 2 LHT‘0}) — L11 [‘O’j’fl + 5 log(ToQ) — C7. 1 — 8 ,+ 2 1 :r '2 _ f; ‘ )Toz—KgTi +§log(—:—). It remains to show the bound on the probalnlity of A. Clearly P(BT/2 > —eoT) : ohm/27) P(BT<\/F.0T) : @(ox/ET) 39 and by a time change argument T/2 2 P ( / mdB < 1T) . 0 4 IV 'I"/‘2 e .T/z ‘ ( P / 7r0dB<—/ fizazdt .0 2 0 T : (I) -— . [:1 Hence for T sufficiently large with probability close to 1, the EC portfolio is outper- forming the bcrp and the universal portfolio by on the order of T in the exponent. 4O Chapter 5 Proofs of Ch. 2 Results We now present the proofs of the results contained in Chapter 2. For the reader’s convenience the theorems are restated and previously displayed expressions retain their original numbering. Theorem (2.1). Suppose u, r and Z are .7} adapted processes which satisfy (1.3), S is a bounded stopping time and E E R’" is 7:5 measurable. Let 7} be an adapted R+ valued process such that for each t > 0 t m / [Inrl + Z (MHz-l + 02221)] ds < 00 (2.1) 0 i:l almost surely. There exists a unique strong solution {a (S,t),t 2 S} E R’" to the following stochastic differential equation 1 do,- = lel + 7] b2” — Elf (0)] (it (2.2) 41 with initial (1 (S, 0) : 5 and where f : R’” —+ Dm is given by . t t . . _ V ‘ 7 i ' " § 3 ‘ ‘ ‘ 7) \ V‘ ' . ' Proof. By our assumptions (2.1) the piousscs f0 ndZ and f0 naiuds are semi-martlngales. From [heorem \".3.7 on page 197 of Protter (1990), to show existence and uniqueness it is enough that f is Lipschitz. For a E Rm, the partial derivatives are given by 312(0) 62‘“ (1+ 2k?“ eak) . Z: . 2 :3 i a 1 —' i a (901 (1+ercn:1eak) f( )( f( )) and (5.1) an) _ weakly» __ - .. aaj (1+Zzz:leak)2 f1( )f3( l for i 75 j. The derivatives are continuous and bounded in absolute value by 1. Hence f is Lipschitz. In fact ||f(a) — f(b)|| S mHa — b“ for a, b E Rm. Cl Before we prove Theorem 2.2 we require the following lemma which gives condi- tions on the integrand for convergence of a stochastic integral. Lemma 5.1. Let 0 satisfy (1.3) and g”) be a sequence of IR” valued processes such that gfnl(t) are bounded and continuous and converge uniformly to 0 in probability. Then 't. ("lodB conver es uniformly on compacts to zero in probability, i.e. for each . 0 (I g t>0 811p Ofsgt / g(")UdBl| —> 0 . 0 42 in probability. Proof. Let TM :— inf{t : maxi-jot Eil-dt Z .11}. By (1.3) TM —> 00 almost surely as M —> 00. If we can establish the result for the stepped process fOMT‘" gl”)odB then we obtain the desired result upon letting M —> 00. Therefore we assume that maxi f0DO Eiidt g M. First assume gfn) converges uniformly almost surely. By Doob’s inequality 2 t 00 m 2 E [sup/ gfnlgdB] S E / :9Emziidt] 0 0 . t - 2 S E mM sup (1201)] _ m which converges to O by the Bounded Convergence Theorem. So supt fat g(")odB con- verges to O in probability. Now suppose gm) only converges in probability uniformly. Then for every subsequence nk. glnklconverges to zero in probability uniformly. For each of these subsequences there is another subsequence nk, for which the convergence is almost sure. From what we have shown supt jot 9("kllodB converges to 0 almost surely. Hence supt fot g(")odB converges to O in probability. D Theorem (2.2). Suppose that r is a positive constant, S,T are bounded stopping times with 0 < T — S _<_ r and 77 > 0 is constant. Under the conditions of Theorem 2.1 the DEan) portfolio q converges in probability uniformly to the EG(7}) portfolio 7r and the Ll’l’m) converges in probability uniformly to Lil/”(Fl on the interval [5, T]. Proof: Let a be the solution to the SDE (2.2). f be as in Theorem 2.1, and S < T be be stopping times bounded above by the constant T > 0. Recall that the DEG 43 portfolio is given by (Ilia) : £3 77X,- (A) (1 (lit—1)]. X (k) + (10 (tk_1)X0(A*) me) = q.(t,._1>oxp{ }l"):latkSt2,~, ds. 1 " i j - r - 2* . . . and g] ) and g]- J) are defined piecewise by .(i) i) . (i .q. (r) = gf (Z‘,q)—gfl<0.o time) = .99" (mm — of”) (mg) for tk_1 < t S tk, 1 g A‘ g n, and 1 g i,j,§ m. Notice, the resemblance of the expression above for a, and (2.2). “'0 now show that in probability: lim sup {|(i(t) — a(t)| : S g t g T} = 0 (5.4) A—>0 Proof of (5.4) The result follows in two steps. In the first step we prove that the remainder term R converges to O. For this step we employ a second moment argument involving Ito’s isometry. In (1.3) we have not assumed the existence of any moments of the stochastic integrals, however, we circumvent this obstacle with a localization argument. In the second step we use the method of successive approximations to prove that the integrals on the rhs of (5.3) converge to 0. Define the stopping time t m TM : inf t > 0:111ax|Z,(t)|: Al or / Ir] + Z (le‘l + 2,2,) ds : AI ' 0 i=1 By (1.3) lim TM 2 00 almost surely as M ——> 00. Thus if we can establish the result for the stopped process o'(t /\ Tu) —- a(t /\ TM) (i.e. under a boundedness assumption) then we obtain the desired result. upon letting A] —> 00. We may assume therefore 46 that max,- IZ(t ()I and IOII III I + 2::,(,I/1 I + S,,~)] (1.9 are bounded by 11/ > 0. First we show that SUPsgrgT IIR(t )II —> 0 111 p1obabilitv. In terms of the Brownian integral we l1 ave, 22/9] U,(lB+i/,J, ((f1,—r)—%Z,,(s)t. 132‘; /. 95'1’22'2‘ 1 i j '1 By the triangle inequality and using (a. + b)2 S 2((12 + b2) 2 E sup IR,(t)II 53th < 2E ft, — '7') if”) Izijl (18 m t 2 +2E sup / 0 dB b 0. Hence 111 probabilitv S‘1l)sgrnglR((1)Il2 —+ 0. We now use the method of successive approximations to prove that the integrals on the rhs of (5.3) converge to (1. Since f is Lipschitz there exists K > 0 such that ||f(y) - f(1')|| S Klly - Ill, :1, y 6 Rm. Define a sequence of stopping times To = S and T, = inf{t > T,_1 : f7; IIZII ds} = (2Ix'\/ih)_1 where IIEII : #215]. 2,2]. is the matrix norm. By the Cauchy-Schwartz inequality 1 1 /||E||d8 S m/ m.‘<.1X|Ez-jld8 O 0 3] ‘ 1 1 S m/ 535,213,.(13 0 t t m\// 2,,ds/ ijds. 0 0 Hence by (1.3) then T, —> 00 as l —> 00 and there exists an L random but finite such I/\ that TL > T. Define a sequence of R1" valued processes by , t 1 t I';(J)(t—':) €+7}/(121+U2/Ziid.9+/Stzif(y(] 1))(15, SStST (5.5) S' S 48 for 27 = 1. m , j = 1, 2, and with Y”) = (1.. Define 110-”:511,{Hrmm—1"U“”(1)||:1",_1gig T1}. Then from the definition of R DUJ) : sup IIYU) (t) _ GUIII 71—13677 = sup “mu—MRI)“ TI—iS‘STl 3 max sup IIR(t)-R(Tt—1)II T1493?) which is independent of( and converges to zero in probability as A —-) 0 since L is finite and we have shown IIR(t)II converges uniformly to 0. By the definition of D, the Lipschitz property and the vector inequality IIrII S 1/m. maxi I;r,-I, :2: E R’" we have t D(j,l) ___ sup / EU (Yo-11) _f()»(j—2)))ds TI—iStSTI - TI—l t S fiD‘j‘L’IK sun / llzllds Tl—lS‘STI '1‘1—1 1 ('_1[ 1 11 <: .—l)] ’)‘< —fl)(’). _ 2 — 2] The final inequalities follow from the definition of the random partition formed by the stopping times T, and by induction. Knitting together over the partition yields: sgt :10. By taking limits in (5. 5) it follows that the sequence of processes 3}”) converge uniformly to (it with probability one. Thus sup {Ho (1) — o ")( (II {S_ < t < T}} 2 11111 SUP {II} (J)( UNI} t J S 0 be constant. For any bounded stopping times S and T with 0 < T — S S 7 and any non short-selling constant target 11 E 7'0 (Dm) the EG(7},S) portfolio 77 satisfies 1 T 5 . T Lli'gzr) —~LW( s ')r) =—/ (71' — u) 2(71 — u.) dt + 7—2/ n’Zert [”7 I 2 s 2 S —§[ 252 21 WW ))-d(u||7r(S)). 7] Proof. The proof follows by applying Ito’s formula to the relative entropy function (1. First we use the definition of (1. since u is constant we have d (up (711 — (1(un (511 "I _ y. “(1 _ _ “_i _ (1 771(7) — log (7101“) —Zm [log (“0) lg(W0(T))i 110 m 5 ul- 5 71.- (S) "10g (10(5)) + Z; [log (70) -10.; (Wash _ . 770 (S) .. 1 , _ . log (750 (T)) — u. ((1 (T) (1 (S)) : l1((1' (T)) — h ((1 (S)) — 11* (a (T) — (1(5)) where h : Rm —1 IR is given by Ma) 2 log(l + 2216‘“). Relating to f used in the definition of 71 and using (5.1) we. calculate the partial derivatives as: (7h ((1) ea" hi ((1) 2 Ba,- : 1 + 2:1 e01- : f‘(a‘)’ _ 32/1((1) _ hij (a) -— 0050a.) - —fl(a')fj(a‘)9 02/1 ((1) (111(0) 2 02a" -—- f1(a)(1- 13(0))- Coniparing with the definition of the EC (7), S) portfolio we recognize that h,- (a) = 71,-, h.”- (71) = —71nrj and hi,- ((1) = 7n (1 — 71,). So by Ito’s formula '1' 752 '1‘ "2 T m h ((.1(T)) : 11((1(S)) +/ 717111 — —/ 71‘271dt+ —/ Z min-(it. Recalling the differential for (1: (10,-: ndZ, + I] IS — 2,71] (It, we get 11‘ 2 (1(11II71(T)) — (1(11II71 (S)) .7 '1‘ 771 : (71 — 11))(111— —/ST 71 271(lt + —/s 71 Eadt 1.. 7 . Z? .. 5 7] * : 11/1 (71 — '11.) (12 + —/ST 71 — u), Emit — 77/T (71 — a) 271(1t 5 2 Z( - S [)2 T __2_ 5 71*271111 + —/ST 271,211,111 : 7]~’(LH [5"))_ _L11.7[(;:Zl,)) — 51/511“ — 11) Z (71 — '11.)(1t 2 T 2 T m 7} 77 —— 71*271111 + — 71,Z,,dt. 2 . 2 . E} where the final equality follows from the general expression for the log wealth (1.6). With rearrangement of the terms and division by 77 we obtain the result. Cl Lemma 5.2. TM = inf {t 2 0 : max,- fot 2,,- = 1V} is a stopping time with respect to Q; =0{S(s) :0 g s S t}. Proof. We show that max,- fot 2,,ds is 9, adapted. For each partition of the interval [0. t] the following sum is clearly g, measurable k ‘tk 1 2 ti: 1 £1: : Z / (11,-— —Z,,) (It + 2: / (11, — —Z,~,) (It/ 0,-dB k 171—1 2 k tk-l 2 11—1 2 £7: + Z / 0,111; k tk—l Z Il"8(sz‘(fk)) " log(S,(tk_1))I2 : Z I]: (Hi -‘;’Ziz (it +/ 101113 k t1.— Since the time integral has bounded variation and the Brownian integral is continuous the first two terms converge to 0 almost surely as the mesh size of the partition converges to 0. By Theorem 1.5.8 011 page 32 of Karatzas and Shreve, the third 'tA 2 t )‘ ‘ . ' '.)‘ \‘ v.. ' . ‘ ' '. . .' ' '." term 2k Um.” o,(lB] couxcrg O and TM : inf {t > 0 : maxifol Ends : .M}. Choose 7) = $7 then the EG(7),0) portfolio 71 with 71(0) : (71—:11,“ satisfies ( 1 ( > 1 T LNW) —L111;[O.’.t) 2 5 f0 (”-1”) 2(71-11)dt 2 (1+ 71K + log(m +1)) where K = maxis111j10nw (11m. tk 0 almost surely satisfying the same property. For a fixed A let S : to 3 t1 3 g tN = T be a partition such that uA is constant on each subinterval [tk_1, tk). Create the corresponding step function approximation of 7] by 7);“ : 7111. for tk g t < tk+1. Let 71 be the EC portfolio using the varying learning parameter process 7] and initial value 7110 = f (a(t0)) . Define 71A interatively such that 713 = f((1(t0)), and over the interval [tk, tk+1) it is the EC portfolio with initial value 71 (1k) and constant learning parameter ‘77tk- By Theorem 2.3 MOT) «1(“Al 1 T A A * A A 1- Lll'wj.) - Ll’lmT) : i s (71 — u ) E (71 — u )(lt (0.8) 1 T A A * A 1 T m A A — ’ i I Z i dt — — f I En It r.9 +2/S I1 (71 l 71 2/3 121:7? ‘1. t (9 ) (1(“tk+ll|7rfi+l) dlu'tkllfltA.) + E - —‘ - 56 Now let A —> 0. By definition uA —-> u and Lil/1”” —~> Lil/(“L We now prove that 71A converges to 71. Let t TM = inf {t > 0 : max/ Ell-ids = 111}. l 0 By (1.3) limTM : 00- almost surely as 111 —> 00. Thus if we can establish the result for the stopped process 71A(t /\ TM) and 71(t /\ TM) then we obtain the desired result upon letting M —+ 00. We may assume therefore that maxi fot Ends and the process 7) are bounded by the same AI > 0. Let (1(t; 7)A)i :2 log (g) then 0 77A — 7)) de' + /t (77A — 77) [1211‘ — 21f (0)] d3 5 GNU-01(1) = [S 2 (, , [S neg. (f (01A) _ f (1.1)) ds. l: (7]A '_ 77) (122' + f; (7}A _ 77) B211 — 21f (01)] ds Let b(t) = max. . By the right continuity of 7] and Lemma 5.1, b(t) converges to 0 uniformly in probability. Let K be the Lipschitz constant for f, since 7) and 212i are bounded we have £012,111 (0A) — f ((1)) (ls 3 KM2 ls ||ae(s) _ a(s)llds. For the norm of the difference then ‘0 9-1 I HM) — (1(1))? = 21-13(1) — (1'.-(1))? g Elke) “1112/ “an s—)c1(s)||ds]2 i=1 3 2771.b2(t) + 211'21114777,(T — S)/ ”(13(3) — (1(s)||2ds s where the last inequality follows since (.1: + y)2 S 251:2 4— 2:112 and from Jensen’s in- equality. Let 7 = 21171114 m(T —— S) then by Gronwall’s inequality 1 “(9(1) — (1(1) )||2 < 27nb2(t )+ y/ 2771b2(s s)exp {'1( (t— s)}ds. 0 Hence s11p0§tST ||(1A(t) — (1(1)”2 —-> O uniformly in probability. Since f is uniformly continuous we also have 311903th ||71A(t) — 71(t)||2 —> O uniformly in probability. Us- ing Lemma 5.1 as in the proof of Theorem 2.2 we can show that L1'V(“A) — LWl”) converges to 0 as well. Hence the 1118 of (5.8) converges to the rhs of (2.7). Since uA and 71A converge to u and 71 respectively we have that the first 3 terms on the rhs of (5.8) converge to the corresponding integrals in (2.7). Hence Z dlutkfiuillflf—EH) _ (“Uh-llflii) k 771-1+1 mic must converge in probabillty. We, formally denote thls 11m1t as fg (Nit. E] Lemma (2.8). Let u be a continuous process of bounded variation taking values in the interior of D", i 6. fm allt > 0 u) E 4- — {116 Dm: 2:: 111.,- < 1.11.,- > 0}. Then 58 u. E T(D,,,), i.e. up to time t the process 11 generates finite wealth. And for 77 > 0 constant and the Ean) portfolio we have 31‘ m T u. /S 1111,: 11—1 d(u.(T)ll71(T)) — d(i1(5)ll71(5)) -— 2/ [log (E) — 11,]1111 i:l 5 Proof. Consider the expression on the right hand side of (1.7). By the assumed smoothness the time integrals are finite for each t. Since u has bounded variation we can interpret the stochastic integral by “integration by parts” as t t / u“dZ : UTZT — / Z*dlt 0 0 where the rhs is well defined since the semi-martingale Z is continuous. Hence u is a target. Since 77 is constant the sum (2.8) can be decomposed as 77‘1 times 2 [d (”an ”TM-+1) 1 “Mullfiull = (“UT—H771) - d(u5||715) k _Zld ('ulk limit) _d(u’tk—1ll7rtk)l' The partial derivatives of d(u)|v) are ,(ullv) : log (El—i) — log (3). i “'0 ("0 The above partial derivatives are continuous functions of 11 away from the boundary of Dm. Since 11 is continuous and restricted to the interior of D,,,, on [8, T] it is uniformly 59 bounded away from the boundary of D,,,. Recall that. almost surely (1,- : log (it) is uniformly continuous on [5, T]. So 2: [(l(u1,.ll711,,) -d(u.1,._,I|711,.)] : Z/tk [log (:42: )— (1,(tk)] du, k 1,,_ 1 1 0 I: almost surely as the mesh size A —> O by uniform continuity of (1,. [:1 Theorem (2.9). Let u be as in Theorem 2.8 with fooo d|u| = K. Let S = 0, A! > 0, c > 0 and log(T—i) 7T0 -1 T0111) : inf {t > 0 : max/ Bids 2 Mormax 0 2 l :0} Choose 7]— — 2V log—mt]- then the EG(7},()) portfolio 71 with 71(0) 2 (771151“, satisfies LW“r [0’T(M.c)) _ 2 —Ll*V(") > 1/T (71 — u)* E (71 — u) dt + Q /T 71*271dt [0T(1‘11)) 0 2 0 mM ——2 l ' . 1 ' 1M — ..K . \/og(m+ )m c \/4log(m+1) P7oof. As before we use that d('(n—u|) m) _<_ log(m + 1) and note that m+l)1 0 > /Z [log (20)]1111,— Zu, log (11,-) 2 —log(m+ 1). i: O 60 hence fOT 2:1 [log (770)](1114 Z — log(m + 1). By the definition of the stopping time '1) M.c) m / Z [0,. (flldul— g M - 0 i:1 and 1 T m §/0 E71321] (it < 1"]. The result follows using the choice of 77 with Theorem 2.7 and Lemma 2.8. C] 61 Chapter 6 Final Remarks In Chapter 2 we were able to extend the DEG portfolio to continuous trading and obtain a lower bound in performance versus the bcrp and larger targets with a finite number of jumps and with bounded variation. These results give conditions under which the EC portfolio can achieve nearly the same exponential growth as these larger targets. At least in markets where it stays away from the boundary, the EC portfolio can track targets which are not constant but do not vary too much. An important feature of these results, as opposed to those obtained by Helmbold et.al. for the DEG portfolio, is the development of an identity containing positive terms that are large if the EC portfolio is distant from the bcrp. In Chapter 4 we have presented examples of simple oscillatory drift markets where the EC portfolio outperforms the universal portfolio and the bcrp with probability arbitrarily close to 1. A second important feature of the EC portfolio is that since it can be straight-forwardly updated on-line it is much easier to calculate than the universal portfolio. Further examination of the behavior and properties of the solution to (2.2), the- 62 oretically or via simulation, is necessary to further delineate the market conditions under which the improved performance of the EG portfolio may hold. The presence of learning parameter I] in the EC algorithm can viewed as a boon or bane. On the one hand, the investor is allowed flexibility to control risk by choosing 7) large or small. We see that choosing a good 7) can be done by setting a level of future variation out to which the investor wants protection. One can remove this dependence by considering a doubling scheme where the portfolio is run over longer and longer epochs reinitializing each time. With Theorem (2.7), we have laid the groundwork to choose 7} adaptively and perhaps obtain better bounds. Cover and Ordentlich (1996) and Helmbold et. al. working with discrete trading introduce the concept of side information. In addition to the market stock prices the investor is privy to extra information upon which to base the investment strategy. For positive integer J they define an adapted random process Y, taking values on {1,2, ..., J}. Then they partition according the value of Y and run J copies of the algorithm. Through examples of stock data, Helmbold et. al. exhibit simple forms of side information which can greatly increase the wealth obtained by the DEG and universal portfolios. In the continuous case we can also run J copies, however, when the process Y returns to state i there is no guarantee the stock price is the same as when it last left state i. Hence, in order to extend the results for EG portfolio to side information, we would need to modify the proofs to account for possible jumps in the stock prices. As (10 Cover and Helmbold et. al., we assume that there are no transaction costs. For rebalanced portfolios in continuous time we must continuously buy and sell to 63 maintain the desired pi'Oportion of wealth in each asset. One approach to solving this difficult problem may be to modify (1.8) to include a penalty for over trading. 64 Bibliography [1] T.M. Cover. (1991) Universal Portfolios. h’lathernatical Finance, 1, 1-29. [2] T.M. Cover and E. Ordentlich. (1996) Universal portfolios with side information. IEEE Transactions on Information Theory, 2 (2). [3] DP. Helmbold, RE. Schapire, Y. Singer, M.K. VVarmuth (1998). On-Line Port- folio Selection Using Multiplicative Updates, Mathematical Finance, 8 325-347. [4] F. Jamshidian. (1992) Asymptotically Optimal Portfolios, Mathematical Finance, 2:2 131 - 150. [5] I. Karatzas. (1991) Lectures on the Mathematics of Finance, CRM Monograph Series, Vol. 8, American Mathematical Society. [6] I. Karatzas and SE. Shreve. (1991) Brownian Motion and Stochastic Calculus, Second Edition, Springer Verlag, New York. [7] J. Kivinen and M.K. Warmuth. (1994) Exponentiated gradient versus gradient descent for linear predictors, Technical Report UCSC-CRL-94—16, University of Califirnia, Santa Cruz, Computer Research Laboratory. [8] E. Ordentlich and T.M. Cover. (1998) The cost of acheiving the best portfolio in hindsight. Mathematics of Operations Research. 23, 960-982. [9] P. Protter. (1990) Stochastic Integration and Differential Equations, Springer - Verlag, Berlin. HICHIGQN srnrs UNIV. LIBRRRIES [ll[l[[l[l[ll[l[[[llllllllllll][[[llllllllll 31293020747980