Fast Universalization of Investment Strategies with Provably Good
Relative Returns

arXiv:cs/0204019v1 [] 10 Apr 2002

Karhan Akcoglu∗

Petros Drineas†

Ming-Yang Kao‡

February 1, 2008

Abstract
A universalization of a parameterized investment strategy is an online algorithm whose
average daily performance approaches that of the strategy operating with the optimal parameters
determined offline in hindsight. We present a general framework for universalizing investment
strategies and discuss conditions under which investment strategies are universalizable. We
present examples of common investment strategies that fit into our framework. The examples
include both trading strategies that decide positions in individual stocks, and portfolio strategies
that allocate wealth among multiple stocks. This work extends Cover’s universal portfolio work.
We also discuss the runtime efficiency of universalization algorithms. While a straightforward
implementation of our algorithms runs in time exponential in the number of parameters, we show
that the efficient universal portfolio computation technique of Kalai and Vempala involving the
sampling of log-concave functions can be generalized to other classes of investment strategies.

1

Introduction

An age-old question in finance deals with how to manage money on the stock market to obtain an
“acceptable” return on investment. An investment strategy is an online algorithm that attempts to
address this question by applying a given set of rules to determine how
capital. Typically,
S∞to invest
∗
i
an investment strategy is parameterized by a vector w ∈ R = i=1 R that dictates how the
strategy operates. The optimal parameters that maximize the strategy’s return are unknown when
the algorithm is run and the parameters are usually chosen quite arbitrarily. A universalization of
an investment strategy is an online algorithm based on the strategy whose average daily performance approaches that of the strategy operating with the optimal parameters determined offline
in hindsight.
Consider the constantly rebalanced portfolio (CRP) investment strategy universalized by Cover
[5] and the subject of several extensions and generalizations [3, 6, 11, 13, 15]. The CRP strategy
maintains a constant proportion of total wealth in each stock, where the proportions are dictated
∗

Department of Computer Science,
karhan.akcoglu@yale.edu. Supported in part
†
Department of Computer Science,
petros.drineas@yale.edu. Supported in part
‡
Department of Computer Science,
kao@cs.northwestern.edu. Supported in part

Yale University, New Haven, CT 06520, USA.
by NSF Grant CCR-9988376.
Yale University, New Haven, CT 06520, USA.
by NSF Grant CCR-9896165.
Northwestern University,
Evanston,
IL 60201,
by NSF Grant CCR-9988376.

1

Email:
Email:
Email:

by the parameters given to the strategy. In a stock market with m stocks, the parameter space for
the CRP strategy is
m
X
wi = 1},
Wm = {w ∈ [0, 1]m |
i=1

Rm

the set of vectors in
whose components are between 0 and 1 and add up to 1. Given a portfolio
vector w = (w1 , . . . , wm ) ∈ Wm , wi tells us the proportion of wealth to invest in stock i, for
1 ≤ i ≤ m. At the beginning of each day, the holdings are rebalanced, i.e., money is taken out of
some stocks and put into others, so that the desired proportions are maintained in each stock. As
an example of the robustness of the CRP strategy, consider the following market with two stocks
[11, 15]. The price of one stock remains constant, while the other stock doubles and halves in price
on alternate days. Investing in a single stock will at most double our money. With a CRP( 21 , 12 )
strategy, our wealth will increase exponentially, by a factor of ( 21 ·1+ 21 ·2)×( 12 ·1+ 21 · 12 ) = 32 × 43 = 98
every two days.
Cover developed an investment strategy that effectively distributes wealth uniformly over all
portfolio vectors w ∈ Wm on the first day and executes the CRP strategy with daily rebalancing
according to each w on the (infinitesimally small) proportion of wealth initially allocated to each
w. Cover showed that the average daily log-performance 1 of such a strategy approaches that of the
CRP strategy operating with the optimal, return-maximizing parameters chosen with hindsight.
This paper generalizes previous results and introduces a framework that allows universalizations
of other parameterized investment strategies. As we see in Section 2, investment strategies fall under
two categories; trading strategies operate on a single stock and dictate when to buy and short2 the
stock; portfolio strategies, such as CRP, operate on the stock market as a whole and dictate how
to allocate wealth among multiple stocks. We present several examples of common trading and
portfolio strategies that can be universalized in our framework. We discuss our universalization
framework in Section 3. The proofs of our results are very general and, as with previous universal
portfolio results, we make no assumptions on the underlying distribution of the stock prices; our
results are applicable for all sequences of stock returns and market conditions. The running times
of universalization algorithms are, in general, exponential in the number of parameters used by the
underlying investment strategy. Kalai and Vempala [13] presented an efficient implementation of
the CRP algorithm that runs in time polynomial in the number of parameters. In Section 4, we
present general conditions on investment strategies under which the universalization algorithm can
be efficiently implemented. We also give some investment strategies that satisfy these conditions.
Section 5 concludes with directions for further research.

2

Types of Investment Strategies

Suppose we would like to distribute our wealth among m stocks3 . Investment strategies are general
classes of rules that dictate how to invest capital. At time t > 0, a strategy S takes as input an
environment vector Et and a parameter vector w, and returns an investment description St (w)
1

The average daily log-performance is the average of the logarithms of the factors by which our wealth changes
on a daily basis. This notion is discussed further in Section 3.1.
2
A short position in a stock, discussed in Section 2.1, allows us to earn a profit when the stock declines in value.
3
We use the term “stocks” in order to keep our terminology consistent with previous work, but we actually mean
a broader range of investment instruments, including both long and short positions in stocks.

2

specifying how to allocate our capital at time t. The environment vector Et contains historic
market information, including stock price history, trading volumes, etc.; the parameter vector
w is independent of Et and specifies exactly how the strategy S should operate; the investment
description St (w) = (St1 (w), . . . , Stm (w)) is a vector specifying the proportion of wealth to put
in each stock, where we put a fraction Sti (w) of our holdings in stock i, for 1 ≤ i ≤ m. For
example, CRP is an investment strategy; coupled with a portfolio vector w it tells us to “rebalance
our portfolio on a daily basis according to w”; its investment description, CRPt (w) = w, is
independent of the market environment Et .
There are two types of investment strategies. Trading strategies tell us whether we should take
a long (bet that the stock price will rise) or a short (bet that the stock price will fall) position on a
given stock. Portfolio strategies tell us how to distribute our wealth among various stocks. Trading
strategies are denoted by T , and portfolio strategies are denoted by P . We use S to denote either
kind of strategy. For k ≥ 2, let
Wk = {w = (w1 , . . . , wk ) ∈ [0, 1]k |

k
X

wi = 1}.

(1)

i=1

Remark 1 Wk is a (k − 1)-dimensional simplex in Rk . The investment strategies that we describe
below are parameterized by vectors in Wkℓ = Wk × · · · × Wk (ℓ times) for some k ≥ 2 and ℓ ≥ 1.
We may write w ∈ Wkℓ in the form w = (w1 , . . . , wℓ ), where wι = (wι1 , . . . , wιk ) for 1 ≤ ι ≤ ℓ.

2.1

Trading Strategies

Suppose that our market contains a single stock. We have m = 2 potential investments: either a
long position or short position in the stock. To take a long position, we buy shares in hopes that
the share price will rise. We close a long position by selling the shares. The money we use to buy
the shares is our investment in the long position; the value of the investment is the money we get
when we close the position. If we let pt denote the stock price at the beginning of day t, the value
of our investment will change by a factor of xt = pt+1
pt from day t to t + 1.
To take a short position, we borrow shares from our broker and sell them on the market in hopes
that the share price will fall. We close a short position by buying the shares back and returning
them to our broker. As collateral for the borrowed shares, our broker has a margin requirement: a
fraction α of the value of the borrowed shares must be deposited in a margin account. Should the
price of the security rise sufficiently, the collateral in our margin account will not be enough, and
the broker will issue a margin call, requiring us to deposit more collateral. The margin requirement
is our investment in the short position; the value of the investment is the money we get when we
close the position.
Lemma 1 Let the margin requirement for a short position be α ∈ (0, 1]. Suppose that a short
position is opened on day t and that the price of the underlying stock changes by a factor of
xt = pt+1
pt < 1 + α during the day. Then the value of our investment in the short position changes
t
by a factor of x′t = 1 + 1−x
α during the day.
Proof: Suppose that we have $v to deposit in the margin account. Using this as our investment
in the short position, we can sell $v/α worth of shares. Combining the proceeds of the stock sale
3

with our margin account balance, we will have a total of v + v/α dollars. At the end of the day, it
will cost xt v/α dollars to buy the shares back, and we will be left with v + αv − xt αv dollars, which
is positive since xt < 1 + α. Thus, our investment of $v in the short position has changed by a
t
factor of 1 + 1−x
α , as claimed.
Should the price of the underlying stock change by a factor greater than 1 + α, we will lose
more money than we initially put in. We will assume that the margin requirement α is sufficiently
large that the daily price change of the stock is always less than 1 + α.
Remark 2 This assumption can be eliminated by purchasing a call option on the stock with some
strike price p < (1 + α)pt . Should the stock price get too high, the call allows us to purchase the
stock back for $p. Though its price detracts from the performance of our short trading strategy,
the call protects us from potentially unlimited losses due to rising stock price.
If a short position is held for several days, assume that it is rebalanced at the beginning of each
day: either part of the short is closed (if xt > 1) or additional shares are shorted (if xt < 1) so that
the collateral in the margin account is exactly an α fraction of the value of the shorted shares. This
t
ensures that the value of a short position changes by a factor, x′t = 1 + 1−x
α , each day. Treating
short positions in this way, they can simply be viewed as any other stock, so trading strategies are
effectively investment strategies that decide between two potential investments: a long or a short
position in a given stock. The investment description of a trading strategy T is Tt = (Tt1 , Tt2 ),
where Tt1 and Tt2 are the fraction of wealth to put in a long and short position respectively.
Remark 3 Let D = Tt1 −Tt2 /α be the net long position of the investment description. In practice,
if D > 0, investors should put a D fraction of their money in the long position and a 1 − D fraction
in cash; if D < 0, investors should invest D in the short position and 1 − D in cash; if D = 0,
investors should avoid the stock completely and keep all their money in cash. From a practical
standpoint, it is desirable for the trading strategy to be decisive, i.e. |D| = 1, so that our allocation
of money to the stock is always fully invested in the stock (either as a long or a short position).
We show in Section 3 that investment strategies that are continuous in their parameter spaces are
universalizable. Though decisive trading strategies T are discontinuous, the can be approximated
by continuous startegies whose investment descriptions converge almost everywhere to Tt as t → ∞
(see, for example, (3) below).
We now describe some commonly used and researched trading strategies [4, 10, 17, 18] and show
how they can be parameterized.
MA[k]: Moving Average Cross-over with k-day Memory. In traditional applications [10]
of this rule, we compare the current stock price with the moving average over, say, the previous
200 days: if the price is above the moving average, we take a long position, otherwise we take a
short position. Some generalizations of this rule have been made, where we compare a fast moving
average (over, for example, the past five to 20 days) with a slow moving average (over the past
50 to 200 days). We generalize this rule further. Given day t ≥ 0, let vt = (vt1 , . . . , vtk ) be the
price-history vector over the previous k days, where vtj is the stock price on day t − j. Assume
that the stock prices have been normalized such that 0 < vtj ≤ 1. Let (wF , wS ) ∈ Wk2 (where
Wk is defined in (1)) be the weights to compute the fast moving and slow moving averages, so
these averages on day t are given by wF · vt and wS · vt respectively. Since the prices have been
4

normalized to the interval (0, 1], −1 ≤ (wF − wS ) · vt ≤ 1. Let g : [−1, 1] → [0, 1] be the long/short
allocation function. The idea is that g((wF − wS ) · vt ) represents the proportion of wealth that we
invest in a long position. The full investment description for the MA = MA[k] trading strategy is

MAt (wF , wS ) = g((wF − wS ) · vt ), 1 − g((wF − wS ) · vt .

Note that the dimension of the parameter space for MA[k] is 2(k − 1) since each of wF and wS are
taken from (k − 1)-dimensional spaces. Possible functions for g include
(
0 if x < 0
(step function);
(2)
gs (x) =
1 otherwise


if x < − 1t
0
(linear step approximation);
(3)
g(t) (x) = 2t (x + 1t ) if − 1t ≤ x ≤ 1t


1
1
if t < x
and the line

gℓ (x) =

x+1
2

(4)

that intersects gs (x) at the extreme points x = ±1 of its domain. Note that g(t) (x) is parameterized
by the day t during which it is called and that it converges to gs (x) on [−1, 1] \ {0} as t increases.
Remark 4 The long/short allocation function used in traditional applications of this rule is the
step function gs (·). As we see in Section 3, in order for an investment strategy to be universalizable,
its allocation function must be continuous, necessitating the continuous approximation g(t) (·). The
linear approximation gℓ (·) can be used with the results of Section 4, to allow for efficient computation
of the universalization algorithm.
SR[k]: Support and Resistance Breakout with k-day Memory. Discussed as early as
Wyckoff [18] in 1910, this strategy uses the idea that the stock price trades in a range bounded
by support and resistance levels. Should the price fall below the support level, the idea is that
it will continue to fall and a short position should be taken in the stock. Similarly, should the
price rise above the resistance level, the idea is that it will continue to rise and a long position
should be taken in the stock. If the stock price remains between the support and resistance levels,
the idea is that it will continue to trade in this range in an unpredictable pattern and the stock
should be avoided. Support and resistance levels are defined quite arbitrarily in practice, usually
the minimum and maximum prices over the past k days, where k is usually taken to be 50, 150,
or 200 [4]. To generalize this rule, given day t ≥ 0, let vt = (v t1 , . . . , v tk ) and vt = (v t1 , . . . , v tk )
be the minimum and maximum price histories, where v tj and v tj are the minimum and maximum
prices over the previous j days, normalized so that they are in the range (0, 1]. Let w ∈ Wk be
the weights to compute the support and resistance levels, so these levels on day t are given by
st = w · vt and rt = w · vt respectively.
Lemma 2 The support level is bounded above by the resistance level: st ≤ rt .

5

Proof: This follows from the fact that for all 1 ≤ j ≤ k, v tj ≤ v tj .

The long/short allocation function will be denoted by h : {(x, y) ∈ [−1, 1]2 | x ≤ y} → [0, 1].
Let pt be the current stock price (normalized to (0, 1] along with vt and vt ). The idea is that
h(pt − rt , pt − st ) tells us the proportion of wealth that we invest in a long position. The full
investment description for the SR = SR[k] trading strategy is

SRt (w) = h(pt − rt , pt − st ), 1 − h(pt − rt , pt − st ) .
The value of h need only be defined on {(x, y) ∈ [−1, 1]2 | x ≤ y} since, by Lemma 2, st ≤ rt . A
possible function for h is

if x ≤ y ≤ 0

0
1
(step function),
(5)
hs (x, y) = α+1 if x < 0 < y


1
if y ≥ x ≥ 0

1
α
1
long, 1 − α+1
= α+1
short is equivalent to having no position
where the investment allocation α+1
xt
α
t
in the stock, since the return from such an allocation is α+1 + (1+ 1−x
α ) α+1 = 1. Other possibilities
include a continuous approximation h(t) (x, y) to hs (x, y) with maximum slope at most 1t (defined
similarly to g(t) (x)) (6), or the plane

hp (x, y) =

(x + 1)α
y+1
+
2(α + 1) 2(α + 1)

(7)

that intersects hs (x, y) at the extreme points (x, y) = (−1, −1), (−1, 1), and (1, 1) of its domain.

2.2

Portfolio Strategies

Portfolio strategies are investment strategies that distribute wealth among m stocks. The investment
description of a portfolio strategy P is Pt = (Pt1 , . . . , Ptm ), where 0 ≤ Pti ≤ 1 and
Pm
i=1 Pti = 1. We put a fraction Pti of our wealth in stock i at time t.

CRP: Constantly Rebalanced Portfolio [5]. The parameter space for the CRP strategy is
W = Wm . The investment description is CRPt (w) = w: at the beginning of each day, we invest a
wi proportion of our wealth in stock i.
CRP-S: Constantly Rebalanced Portfolio with Side Information. Cover and Ordentlich
[6] consider a generalization of CRP. Rather than rebalancing our holdings according to a single
portfolio vector w ∈ Wm every day, we have k vectors w1 , . . . , wk ∈ Wm and a side information
state yt ∈ {1, . . . , k} that classifies each day t into one of k possible categories; on day t we rebalance
our holdings according to wyt . By partitioning the time interval into k subsequences corresponding
to each of the k side information states and running k instances of the universalization algorithm
(one instance for each state), Cover and Ordentlich show that the average daily return approaches
that of the underlying strategy operating with k optimal parameters, w1∗ , . . . , wk∗ ∈ Wm , where wj∗
is used on days t when the side information state is yt = j. We generalize this further by allowing
portions of our wealth to be rebalanced according to several of the wj every day. Suppose that

6

the side information is encapsulated in some vector v ∈ Rℓ , for some ℓ. This vector can contain
information about specific stocks, such as historic performance and company fundamentals, or
macro-economic indicators such
Let f = (f1 , . . . , fk ) : Rℓ → [0, 1]k
Pkas inflation and unemployment.
ℓ
k
be some function satisfying
j=1 fj (v) = 1 for all v ∈ R . The parameter space is Wm ; the
Pk
investment description is CRP-St (w1 , . . . , wk ) = j=1 fj (vt )wj , where vt is the indicator vector
for day t. Under such a scheme, we have the flexibility of splitting our wealth among multiple
sets of portfolios w1 , . . . , wk on any given day, rather than being forced to choose a single one.
For example, assume that v is a k-dimensional vector, with each vi corresponding to portfolio wi .
Define f : Rk → [0, 1]k by fi (vt ) = P kvti , so that our allocation is biased towards portfolios
ι=1 vtι

corresponding to higher indicators while still maintaining a position in the others.

IA[k]: k-Way Indicator Aggregation. For each day t ≥ 0, suppose that each stock i has a set
of k indicators vti = (vti1 , . . . , vtik ), where each vtij ∈ (0, 1] and, for 1 ≤ j ≤ k, vt1j , . . . , vtmj have
been normalized such that there is at least one i such that vtij = 1. Examples of possible indicators
include historic stock performance and trading volumes, and company fundamentals. Our goal is
to aggregate the indicators for each stock to get a measure of the stock’s attractiveness and put a
greater proportion of our wealth in stocks that are more attractive. We will aggregate the indicators
by taking their weighted average, where the weights will be determined by the parameters. The
parameter space is W = Wk and the investment description is

w·vtm
t1
Pm
,
.
.
.
,
.
IAt (w) = P mw·vw·v
w·v
ti
ti
i=1

3
3.1

i=1

Universalization of Investment Strategies
Universalization Defined

In a typical stock market, wealth grows geometrically. On day t ≥ 0, let xt be the return vector for
day t, the vector of factors by which stock prices change on day t. The return vector corresponding
t
to a trading strategy on a single stock is (xt , 1 + 1−x
α ), where xt is the factor by which the price of
1−xt
the stock changes and 1 + α is the factor by which our investment in a short position changes,
as described in Lemma 1; the return vector corresponding to a portfolio strategy is (xt1 , . . . , xtm ),
where xti is the factor by which the price of stock i changes, where 1 ≤ i ≤ m. Henceforth, we do
not make a distinction between return vectors corresponding to trading and portfolio strategies;
we assume that xt is appropriately defined to correspond to the investment strategy in question.
For an investment strategy S with parameter vector w, the return of S(w) during the t-th day—
the factor byPwhich our wealth changes on the t-th day when invested according to S(w)—is
St (w) · xt = m
i=1 Sti (w) · xti (recall that St (w) is the investment description of S(w) for day t,
which is a vector
Qn−1specifying the proportion of wealth to put in each stock). Given time n > 0, let
Rn (S(w)) = t=0 St (w) · xt be the cumulative return of S(w) up to time n; we may write Rn (w)
in place of Rn (S(w)) if S is obvious from context. We analyze the performance of S in terms of
the normalized log-return Ln (w) = Ln (S(w)) = n1 log Rn (w) of the wealth achieved.
For investment strategy S, let wn∗ = arg maxw∈R∗ Rn (S(w)) be the parameters that maximize

7

the return of S up to day n.4 An investment strategy U universalizes (or is universal for ) S if5
Ln (U ) = Ln (S(wn∗ )) − o(1)
for all environment vectors En . That is, U is universal for S if the average daily log-return of U
approaches the optimal average daily log-return of S as the length n of the time horizon grows,
regardless of stock price sequences.

3.2

General Techniques for Universalization

Given an investment strategy S, let W be the parameter space for S and let µ be the uniform
measure over W. Our universalization algorithm for S, U(S), is a generalization of Cover’s original
result [5]. The investment description Ut (S) for the universalization of S on day t > 0 is a weighted
average of the St (w) over w ∈ W, with greater weight given to parameters w that have performed
better in the past (i.e. Rt (w) is larger). Formally, the investment description is
R
R
St (w)Rt (S(w))dµ(w)
S
(w)R
(w)dµ(w)
t
t
= WR
,
(8)
Ut (S) = W R
W Rt (w)dµ(w)
W Rt (S(w))dµ(w)
where we take R0 (w) = 1 for all w ∈ W.6

Remark 5 The definition of universalization can be expanded to include measures other than µ,
but we consider only µ in our results.
Lemma 3 ([3, 6]) The cumulative n-day return of U(S) is
Z

Rn (w)dµ(w) = E Rn (w) ,
Rn (U(S)) =
W

the µ-weighted average of the cumulative returns of the investment strategies {S(w) | w ∈ W}.
Proof: The return of U(S) on day t is Ut (S) · xt , where xt is the return vector for day t. The
cumulative n-day return of U(S) is
R
n−1
n−1
Y
Y
W RSt (w)Rt (w)dµ(w)
· xt
Ut (S) · xt =
Rn (U(S)) =
W Rt (w)dµ(w)
t=0
t=0
R
R
n−1
n−1
Y
Y
R (w)dµ(w)
W (StR(w) · xt )Rt (w)dµ(w)
W
R t+1
=
=
.
W Rt (w)dµ(w)
W Rt (w)dµ(w)
t=0
t=0

The result follows from the fact that this product telescopes.

Rather than directly universalizing a given investment strategy S, we instead focus on a modified
version of S that puts a nonzero fraction of wealth in each of the m stocks. Define the investment
strategy S̄ by
ε
ε
)St (w) +
S̄t (w) = (1 −
2
2(t + 1)
2m(t + 1)2
4

As mentioned above, wn∗ can only be computed with hindsight.
Unlike previously discussed investment strategies, the behavior of U is fully defined without an additional parameter vector w.
6
Cover’s algorithm is a special case of this, replacing St (w) with w.
5

8

for t ≥ 0 and some fixed 0 < ε < 1. Rather than universalizing S, we instead universalize S̄.
Lemma 4 tells us that we do not lose much by doing this.
Lemma 4 For all n ≥ 0, (1) Rn (U(S̄)) ≥ (1 − ε)Rn (U(S)) and (2) Ln (U(S̄)) = Ln (U(S)) −
(3) If U(S) is a universalization of S, then U(S̄) is a universalization of S as well.

o(n)
n .

Proof:
Statements (2) and (3) follow directly
(1) follows from the
Qn−1 from (1). Statement
Qn−1
ε
fact that for all w ∈ W, Rn (S̄(w)) =
S̄
(w)
·
x
≥
(1
−
)St (w) · xt ≥
t
t=0 t
t=0
2(t+1)2
Pn−1 ε
(1 − t=0 2(t+1)2 )Rn (S(w)) ≥ (1 − ε)Rn (S(w)).
Remark 6 Henceforth, we assume that suitable modifications have been made to S to ensure that
ε
Sti (w) ≥ 2m(t+1)
2 for all 1 ≤ i ≤ m and t ≥ 0.
Theorem 5 Given an investment strategy S, let W = Wkℓ (for some k ≥ 2 and ℓ ≥ 1) be its
parameter space. For 1 ≤ i ≤ m, 1 ≤ ι ≤ ℓ and 1 ≤ j ≤ k, assume that there is a constant c such
ti (w)
≤ c(t + 1) for all w ∈ W. Then U(S) is a universalization of S.
that ∂S∂w
ιj
To prove Theorem 5, we first prove some preliminary results.
Lemma 6 For nonnegative vector a and strictly positive vectors b and x,
min
i

ai
ai
a·x
≤ max .
≤
i
bi
b·x
bi

Proof: Assume that the components of a and b are strictly positive. Otherwise, the lemma holds
trivially. Let imax = arg maxi abii and imin = arg mini abii , so that
ai
ai
bi
ai
≤
≤ max ⇔
bi
bimax
aimax
bimax

and

ai
ai
ai
bi
≥ min ⇔
≥
.
bi
bimin
aimin
bimin

Then
aimin (ximin +
bimin (ximin +
⇒

ai
i6=imin aimin xi )
P
bi
xi )
i6=imin bi

P

=

a·x
b·x

≤

a·x
b·x

min

aimin
bimin

=
≤

aimax (ximax +
bimax (ximax +
aimax
.
bimax

ai
i6=imax aimax xi )
P
bi
xi )
i6=imax bi

P

max

Our next two results are related to the (k − 1)-dimensional volumes of some subsets of Rk .
Lemma 7 The (k√− 1)-dimensional volume of the simplex Wk = {w ∈ [0, 1]k |
k
.
defined in (1), is (k−1)!

9

Pk

i=1 wi

= 1},

Proof: By induction on k, it can be shown that the k-dimensional volume of the solid Wk (s) =
P
k
{w | ki=1 wi ≤ s} is sk! . Written in terms of the length r of the line segment passing between the
√
1 k k2
origin and ( ks , . . . , ks ) ∈ Rk , the volume is k!
r k since s = r k. Upon differentiation with respect
√ k−1
k
1
1
r k−1 k 2 = (k−1)!
to r, (k−1)!
ks , we arrive at the (k − 1)-dimensional volume of the simplex
Pk
Wk (s) = {w | i=1 wi = s}. Setting s = 1 yields the desired result.
Lemma 8 The (k − 1)-dimensional volume of a (k − 1)-dimensional ball of radius ρ embedded in
k−1

Wk is

π 2 ρk−1
,
Γ( k−1
+1)
2

where
Γ(ℓ) = (ℓ − 1)!

√
and Γ(ℓ + 21 ) = (ℓ − 12 )(ℓ − 32 ) · · · ( 12 ) π.

Proof: This result is proven in Folland [8, Corollary 2.56].
Proof of Theorem 5: ¿From Lemma 3, the return of U(S) is the average of the cumulative returns
of the investment strategies {S(w) | w ∈ W}. Let w∗ = arg maxw∈W Rn (S(w)) be the parameters
that maximize the return of S. We show that there is a set B of nonzero volume around w∗ such
that for w ∈ B, the return Rn (w) is close to the optimal return Rn (w∗ ). We then show that the
contribution to the average return from B is sufficiently large to ensure universalizability. We begin
by bounding the magnitude of the gradient vector ∇Rn (w). From Remark 6 and our assumption
in the statement of the theorem, for all w, t, i, ι, and j
∂Sti (w)
∂wιj

Sti (w)

≤ c′ m(t + 1)3 ,

where c′ = 2c
. Using this fact and Lemma 6, the partial derivative of the return function Rn (w) =
εQ
n−1
Rn (S(w)) = t=0
rt (S(w)) with respect to parameter wιj is
∂Rn (w)
∂wιj

≤ Rn (w)
≤ Rn (w)

∂(St (w)·xt )
n−1
X
∂wιj
t=0
n−1
X
t=0

St (w) · xt

≤ Rn (w)

n−1
X
t=0

∂Sti (w)
i=1
∂wιj
Pm
i=1 Sti (w)

Pm

c′ m(t + 1)3 ≤ c′ Rn (w)mn4

· xti

· xti

and
√
|∇Rn (w)| ≤ c′ Rn (w)mn4 kℓ.

(9)

We would like to take our set B to be some d-dimensional ball around w∗ ; unfortunately, if w∗ is
on (or close to) an edge of W, the reasoning introduced at the beginning of this proof is not valid.
We instead perturb w∗ to a point w̃ that is at least
ρ=

γ
c′ mn4 k2 ℓ

away from all edges, where 0 < γ < 1 is a constant, and such that Rn (w̃) is close to Rn (w∗ ).
∗ , . . . , w∗ ) and w∗ =
To illustrate the perturbation, let w∗ = (w1∗ , . . . , wℓ∗ ) where wι∗ = (wι1
ιk
ιk
10

Pk−1 ∗
1 − i=1
wιi for 1 ≤ ι ≤ ℓ. We perturb each wι∗ in the same way. Let w̃ι0 = wι∗ . For 1 ≤ j ≤ k,
given w̃ιj−1 , define w̃ιj as follows. Let jmax be the index of the maximum coordinate of w̃ιj−1 . If
j−1
j
j
j−1
j
− ρ and leave all other coordinates unchanged.
= w̃ιj
0 ≤ w̃ιj
< ρ, define w̃ιj
= w̃ιj
+ ρ, w̃ιj
max
max
j
j−1
Otherwise, let w̃j0 = w̃j0 . The final perturbation is w̃ = (w̃1 , . . . , w̃ℓ ), where w̃ι = w̃ιk . By
∗ − w̃ | ≤ kρ for all ι and j.
construction, w̃ ∈ W, w̃ is at least ρ away from the edges of W and |wιj
ιj
We bound

Rn (w∗ )
Rn (w̃)

by the multivariate mean value theorem and the Cauchy-Schwartz inequality:

Rn (w̃) = Rn (w∗ ) + Rn (w̃) − Rn (w∗ )

≥ Rn (w∗ ) − |∇Rn (w′ ) · (w̃ − w∗ )|

(for some w′ between w̃ and w∗ )
√
√
≥ Rn (w∗ ) − |∇Rn (w′ )| · |w̃ − w∗ | ≥ Rn (w∗ ) − c′ Rn (w′ )mn4 kℓ · kρ kℓ
√
√
≥ Rn (w∗ ) − c′ Rn (w∗ )mn4 kℓ · kρ kℓ ≥ Rn (w∗ )(1 − γ).

For 0 ≤ ι ≤ ℓ let Cι = {wι ∈ Rk | |w̃ι − wι | ≤ ρ}. From the construction of w̃, Bι = Cι ∩ Wk is
a (k − 1)-dimensional ball of radius ρ. Let w̃ι∗ = arg maxw∈Bι Rn (w) and let w̃∗ = (w̃1∗ , . . . , w̃ℓ∗ )
be the profit maximizing parameters in B = B1 × · · · × Bℓ . For w ∈ B,
Rn (w) = Rn (w̃∗ ) + Rn (w) − Rn (w̃∗ )

≥ Rn (w̃∗ ) − |∇Rn (w′ )| · |w̃∗ − w| (for some w′ between w̃∗ and w)
√
√
≥ Rn (w̃∗ ) − c′ Rn (w̃∗ )mn4 kℓ · 2ρ ℓ ≥ Rn (w̃∗ )(1 − γ)

≥ Rn (w∗ )(1 − 2γ).
By Lemma 3
Z

Rn (S(w))dµ(w) ≥
R
∗ R B dw
≥ (1 − 2γ)Rn (w )
W dw

Rn (U(S)) =

W

Z

∗

B

Rn (w)dµ(w) ≥ (1 − 2γ)Rn (w )

k−1

= (1 − 2γ)Rn (w∗ )

π 2 ρk−1 (k − 1)!
· √
Γ( k−1
k
2 + 1)

!ℓ

Z

dµ(w)
B

(from Lemmas 7 and 8)

= Rn (w∗ )Λ(γ, m, k, ℓ)n−4kℓ
where Λ is some constant depending on γ, m, k, and ℓ. Therefore,
Ln (w∗ ) − Ln (U(S)) ≤

log Λ(γ, m, k, ℓ)
log n
o(n)
+ 4kℓ
=
,
n
n
n

(10)

as claimed.
Remark 7 The techniques used in the proof of Theorem 5 can be generalized to other investment
strategies with bounded parameter spaces W that are not necessarily of the form Wkℓ .

11

3.3

Increasing the Number of Parameters with Time

The reader may notice from the proof of Theorem 5 that an investment strategy S may be universalizable even if the dimensions of its parameter space W grow with time. In fact, even if the
dimension of the parameter space (the coefficient of logn n in (10)) is O( φ(n)nlog n ), where φ(n) is a
monotone increasing function, the strategy is still universalizable. This introduces an interesting
possibility for investment strategies whose parameter spaces grow with time as more information
becomes available. As a simple example, consider dynamic universalization, which allows us to
track a higher-return benchmark than basic universalization. Partition the time interval I = [0, n)
into ψ = O( φ(n)nlog n ) subintervals I1 , . . . , Iψ and let wI∗ j be the parameters that optimize the return during Ij . In I1 , we run the universalization algorithm given by (8) over the basic parameter
space W of S. In I2 , we run the algorithm over W × W; to compute the investment description for
a day t ∈ I2 using (8), we compute the return Rt (w1 , w2 ) as the product of the returns we would
have earned in I1 using w1 and what we would have earned up to day t in I2 using w2 . We proceed
similarly in intervals I3 through Iψ . This will allow us to track the strategy that uses the optimal
parameters wI∗ j corresponding to each Ij . Such a strategy is useful in environments where optimal
investment styles (and the optimal investment strategy parameters that go with them) change with
time.

3.4

Applications to Trading Strategies

By proving an upper bound on
versalizable.

∂Tti (w)
∂wj

for our trading strategies T , we show that they are uni-

Theorem 9 The moving average cross-over trading strategy, MA[k], is universalizable for the
long/short allocation functions g(t) (x) and gℓ (x) defined in (3) and (4) respectively.
Proof: The parameters for MA[k] are of the form wF = (wF 1 , . . . , wF (k−1) , 1−wF 1 −· · ·−wF (k−1) )
and wS = (wS1 , . . . , wS(k−1) , 1 − wS1 − · · · − wS(k−1) ). Using the long/short allocation function
g(t) (x) defined in (3), the partial derivative of the investment description with respect to a parameter
wF j (or similarly wSj ) is
∂g((wF − wS ) · vt )
t
t
∂MAti (wF , wS )
=
≤ · (vtj − vtk ) ≤
∂wF j
∂wF j
2
2
where 1 ≤ j < k and i ∈ {1, 2}. Similarly, we can show that using the long/short allocation
(wF ,wS )
function gℓ (x) defined in (4), ∂MAti∂w
≤ 12 .
Fj
Theorem 10 The support and resistance breakout trading strategy, SR[k], is universalizable for
the long/short allocation functions h(t) (x, y) and hp (x, y) defined in (6) and (7) respectively.
Proof: We arrive at the result by differentiating the long/short allocation functions h(t) (x, y) and
hp (x, y) with respect to an arbitrary parameter wj and showing that the partial derivative is O(t),
as in the proof of Theorem 9.

12

3.5

Applications to Portfolio Strategies

Theorem 11 The constantly rebalanced portfolio, CRP, and CRP with side information, CRP-S,
portfolio strategies are universalizable.
Proof: The partial derivatives of CRPti and CRP-Sti with respect to an arbitrary parameter wj
are at most 1.
Theorem 12 The k-way indicator aggregation portfolio strategy, IA[k], is universalizable.
P
P
Proof: First, we show that m
w · vtℓ ≥ k1 for all t. Since kj=1 wj = 1, there exists j0 such
ℓ=1
P
Pm
1 Pm
1
that wj0 ≥ k1 . Then m
ℓ=1 w · vtℓ ≥
ℓ=1 wj0 · vtℓj0 ≥ k
ℓ=1 vtℓj0 ≥ k since the {vtℓj0 }1≤ℓ≤m have
been normalized such that there is at least one ℓ0 such that vtℓ0 j0 = 1.
ti (w)
Now, let S = IA[k]. By Theorem 5, we need only show that ∂S∂w
= O(t), for 1 ≤ j ≤ k − 1.
j
w·vti
P
For t ≥ 0 and 1 ≤ i ≤ m recall that Sti (w) = m w·v . Then, for 1 ≤ j ≤ k − 1, since
tℓ
ℓ=1
w = (w1 , . . . , wk−1 , 1 − (w1 + · · · + wk−1 )),
∂Sti (w)
∂wj

=

ℓ=1

≤
as we wanted to show.

4
4.1

m
X
vtij − vtik
w · vti
Pm
·
(vtℓj − vtℓk )
− Pm
( ℓ=1 w · vtℓ )2
ℓ=1 w · vtℓ

m
1
Pm
≤ k + mk2 ,
+ Pm
2
(
w
·
v
)
w
·
v
tℓ
tℓ
ℓ=1
ℓ=1

Fast Computation of Universal Investment Strategies
Approximation by Sampling

The running time of the universalization algorithm depends on the time to compute the integral
in (8). A straightforward evaluation of it takes time exponential in the number of parameters.
Following Kalai and Vempala [13], we propose to approximate it by sampling the parameters
according to a biased distribution, giving greater weight to better performing parameters. Define
the measure ζt on W by
Rt (S(w))
dζt (w) = R
dµ(w).
W Rt (S(w))dµ(w)

Lemma 13 ([13]) The investment description Ut (S) for universalization is the average of St (w)
with respect to the ζt measure.
Proof: The average of St (w) with respect to ζt is
Z
St (w)dζt (w)
Ew∈(W,ζt ) (St (w)) =
W
Z
Rt (S(w))
St (w) R
=
dµ(w) = Ut (S),
R
W
W t (S(w))dµ(w)
13

where the final equality follows from (8).
In Section 4.2, we show that for certain strategies we can efficiently sample from a distribution
ζ̄t that is “close” to ζt , i.e. given γt > 0, we generate samples from ζ̄t in O(log γ1t ) time and such
that
Z
ζt (w) − ζ̄t (w) dµ(w) ≤ γt .
(11)
W

2

ε
Assume for now that we can sample from ζ̄t , with γt = 4m(t+1)
4 , where ε is the constant appearing
R
in Remark 6. Let Ūt (S) = W St (w)dζ̄t (w) be the corresponding approximation to U(S). Lemma 14
tells us that we do not lose much by sampling from ζ̄t .

Lemma 14 For all n ≥ 0, (1) Rn (Ū(S)) ≥ (1 − ε)Rn (U(S)) and (2) if U(S) is a universalization
of S, then Ū(S) is a universalization of S as well.
Proof: Statement (2) follows directly from (1). To see (1), we need only show that the fraction of
ε
wealth we put in each stock i on day t under Ū(S) is within a 1 − 2(t+1)
2 factor of the corresponding
ε
amount under U(S), i.e. Ūti (S) ≥ (1 − 2(t+1)2 )Uti (S) for 0 ≤ t < n and 1 ≤ i ≤ m. For w ∈ W, let
R
ε2
γt (w) = |ζ̄t (w) − ζt (w)|, so that W γt (w)dw = γt ≤ 4m(t+1)
4 . We have
Z
Z
Sti (w)(ζt (w) − γt (w))dµ(w)
Sti (w)ζ̄t (w)dµ(w) ≥
Ūti (S) =
W
W
Z
Sti (w)γt (w)dµ(w) ≥ Uti (S) − γt
(since Sti (w) ≤ 1)
= Uti (S) −
≥ (1 −

W
ε
)Uti (S)
2(t+1)2

(since Uti (S) ≥ minw S(w) ≥

ε
2m(t+1)2

and γt ≤

ε2
),
4m(t+1)4

as we wanted to show.
By sampling from ζ̄t , we use a generalization of the Chernoff bound to get an approximation
ε
Ũ(S) to Ū(S) such that with high probability Ũti (S) ≥ (1 − 2(t+1)
2 )Ūti (S) for 0 ≤ t < n and
1 ≤ i ≤ m. Using an argument similar to that in the proof of Lemma 14, we see that if Ū(S) is a
universalization of S, then such a Ũ(S) is a universalization P
of S as well. Choose w1 , . . . , wNt ∈ W
t
at random according to distribution ζ̄t and let Ũti (S) = N1t N
i=1 Sti (wi ). Lemma 15 discusses the
number of samples Nt required to get a sufficiently good approximation to Ūt (S).
2

8

2

log 2m(t+1)
samples to compute Ũt (S), where ε
Lemma 15 Given 0 < δ < 1 use Nt ≥ 8m (t+1)
δ
ε4
ε
is the constant appearing in Remark 6. With probability 1 − δ, Ũti (S) ≥ (1 − 2(t+1)
2 )Ūti (S) for all
1 ≤ i ≤ m and t ≥ 0.
Proof: Hoeffding [12] proves a general
0≤
P version of the Chernoff bound. For random variables
−2N α2 µ2 .
Xi ≤ 1 with E(Xi ) = µ and X̃ = N1 N
X
the
bound
states
that
Pr(
X̃
≤
(1
−
α)µ)
≤
e
i=1 i
ε
In our case, we would like Ũti ≥ (1 − 2(t+1)
2 )Ūti . As this must hold for 1 ≤ i ≤ m and t ≥ 0 with

δ
ε
total probability 1 − δ, we require Pr(Ũti ≤ (1 − 2(t+1)
2 )Ūti ) ≤ 2m(t+1)2 for each i and t. From our
ε
assumption stated in Remark 6, µ = Ūti ≥ 2m(t+1)
2 and the desired probability bound is achieved

with Nt ≥

8m2 (t+1)8
ε4

log

2m(t+1)2
δ

samples.

14

4.2

Efficient Sampling

We now discuss how to sample from W = Wkℓ = Wk × ·√· · × Wk according to distribution ζt (·) ∝
Rt (·) = Rt (S(·)). W is a convex set of diameter d = 2ℓ. We focus on a discretization of the
sampling problem. Choose an orthogonal coordinate system on each Wk and partition it into
hypercubes of side length δt , where δt is a constant chosen below. Let Ω be the set of centers of
cubes that intersect W and choose the partition such that the coordinates of w ∈ Ω are multiples
of δt . For w ∈ Ω, let C(w) be the cube with center w. We show how to choose w ∈ Ω with
probability “close to”
Rt (w)
πt (w) = P
.
w∈Ω Rt (w)
In particular, we sample from a distribution π̃t that satisfies
X
ε2
|πt (w) − π̃t (w)| ≤ γt =
.
4m(t + 1)4

(12)

w∈Ω

Note that this is a discretization of (11). We will also have that for each w ∈ Ω,
π̃t (w)
≤ 2.
πt (w)

(13)

We would like to choose δt sufficiently small that Rt is “nearly constant” over C(w) i.e. there is a
small constant ν > 0 such that
(1 + ν)−1 Rt (w) ≤ Rt (w′ ) ≤ (1 + ν)Rt (w)

(14)

for all w′ ∈ C(w). Such a δt can be chosen for investment strategies S that have bounded derivative,
as we see in Lemma 16.
Lemma 16 Suppose that investment strategy S satisfies the condition for universalizability given
ν
ti (w)
′
≤ ct. Given ν > 0, let δt = δt (ν) = 3c′ mt
in Theorem 5, i.e. ∂S∂w
4 kℓ , where c is defined in the
j

′ | ≤ δ (ν) for all 1 ≤ i ≤ ℓ and 1 ≤ j ≤ k,
proof of Theorem 5. For w, w′ ∈ W such that |wij − wij
t
−1
′
(1 + ν) Rt (w) ≤ Rt (w ) ≤ (1 + ν)Rt (w).
√
Proof: Note that |w − w′ | ≤ δt kℓ. Let w∗ be the parameters that maximize the return on the
line between w and w′ . By the multivariate mean value theorem and the bound for |∇Rt | given
in (9),

Rt (w∗ ) = Rt (w) + Rt (w∗ ) − Rt (w)

≤ Rt (w) + |∇Rt (wm )| · |w − w∗ | (for some wm between w∗ and w)
√
√
ν
≤ Rt (w) + c′ Rt (wm )mn4 kℓ · δt kℓ ≤ Rt (w) + Rt (w∗ )
3
ν
ν
′
∗
⇒ Rt (w) ≥ Rt (w )(1 − ) ≥ Rt (w )(1 − )
3
3
′
so that Rt (w ) ≤ (1 + ν)Rt (w). By similar reasoning,
Rt (w′ ) = Rt (w∗ ) + Rt (w′ ) − Rt (w∗ )

≥ Rt (w∗ ) − |∇Rt (wm )| · |w′ − w∗ | (for some wm between w∗ and w′ )
ν
ν
≥ Rt (w∗ )(1 − ) ≥ Rt (w)(1 − ) ≥ Rt (w)(1 + ν)−1 ,
3
3
15

completing the proof.
We use a Metropolis algorithm [14] to sample from π̃t . We generate a random walk on Ω
according to a Markov chain whose stationary distribution is πt . Begin by selecting a point w0 ∈ Ω
according to either π̃t−1 or π̃t−2 ;7 Remark 8 explains how to do this.
Remark 8 We can select a point according to π̃t−1 by “saving” our samples that were generated
2
2 8
at time t − 1. By Lemma 15, we would have generated Nt−1 ≥ 8mε4 t log 2mt
samples at time
δ
2

8

2

samples necessary at time t.
log 2m(t+1)
t − 1, which is not enough to generate the Nt ≥ 8m (t+1)
δ
ε4
Instead, we can “save” samples that were generated at times t − 1 and t − 2. For sufficiently large
t, Nt ≤ Nt−1 + Nt−2 and our initial point w0 would be picked according to either π̃t−1 or π̃t−2 . As
we see in the proof of Lemma 22, this distinction is not important.
If wτ is the position of our random walk at time τ ≥ 0, we pick its position at time τ + 1 as
follows. Note that wτ has 2(k − 1)ℓ neighbors, two along each axis in the Cartesian product of ℓ
(k − 1)-dimensional spaces. Let w be a neighbor of wτ , selected uniformly at random. If w ∈ Ω,
set
(
(w)
)
w with probability p = min(1, RRtt(w
τ)
wτ +1 =
wτ with probability 1 − p.
If w 6∈ Ω, let wτ +1 = wτ . It is well-known that the stationary distribution of this random walk is
πt . We must determine how many steps of the walk are necessary before the distribution has gotten
sufficiently close to stationary. Let pτ be the distribution attained after τ steps of the random walk.
That is, pτ (w) is the probability of being at w after τ steps.
Remark 9 A distinction should be made between t and τ . We use t to refer to the time step in
our universalization algorithm. We use τ to refer to “sub” time steps used in the Markov chain to
sample from πt . When t is clear from context, we may drop it from the subscripts in our notation.
Applegate and Kannan [2] show that if the desired distribution πt is proportional to a logconcave function F (i.e. log F is concave) the Markov chain is rapidly mixing, reaches its steady
state in polynomial time. Frieze and Kannan [9] give an improved upper bound on the mixing time
using Logarithmic Sobolev inequalities [7].
√
Theorem 17 (Theorem 1 of [9]) Assume the diameter d of W satisfies d ≥ δt kℓ and that the
target distribution π is proportional to a log-concave function. There is an absolute constant κ > 0
such that
!2
X
κτ δt2
M πe kℓd2
1
+
,
(15)
≤ e− kℓd2 log
|π(w) − pτ (w)|
2
π∗
κδt2
w∈Ω

0 (w)
0 (w)
where π∗ = minw∈Ω π(w), M = maxw∈Ω pπ(w)
log pπ(w)
, p0 (·) is the initial distribution on Ω,
P
πe = w∈Ωe π(w), and Ωe = {w ∈ Ω | Vol(C(w) ∩ W) < Vol(C(w))} (the “e” in the subscripts of
πe and Ωe stands for “edge”).
7

Ideally, we would like to begin with a point selected according to π̃t−1 , but, as discussed in Remark 8, this is not
always possible.

16

In the random walk described above, if wτ is on an edge of Ω, so it has many neighbors outside
Ω, the walk may get “stuck” at wτ for a long time, as seen in the “πe ” term of Theorem 17. We
must ensure that the random walk has low probability of reaching such edge points. We do this by
applying a “damping function” to Rt that becomes exponentially small near the edges of W. For
1 ≤ i ≤ ℓ, 1 ≤ j ≤ k, and w = (w1 , . . . , wℓ ) = ((w11 , . . . , w1k ), . . . , (wℓ1 , . . . , wℓk )) ∈ W let
fij (w) = eΓ min(−σ+wij ,0) ,

(16)

where σ > 0 and Γ > 2 are constants that we choose below, and let
Ft (w) = Rt (w)

k
ℓ Y
Y

fij (w).

i=1 j=1

Lemma 18 Ft is log-concave if and only if Rt is log-concave.8
Proof: This follows from the fact that log-concave functions are closed under multiplication and
the fact that log fij (w) = Γ min(−σ + wij , 0), which is concave.
Choose σ = k1 δt ( γ2t ), where δt (·) is defined in Lemma 16 and γt is defined in (12). Let ζF ∝ Ft
be the probability measure proportional to Ft . We need to show that for our purposes, sampling
from RζF is not much different than sampling from ζt . By Lemma 14, we can do this by showing
that W |ζt (w) − ζF (w)|dw ≤ γt , which we do in Lemma 19.

Remark 10 Before continuing, we show how W can be scaled, which will be useful in future proofs.
Take p = ( k1 , . . . , k1 ) ∈ Wk ; given χ ∈ (−1, 1), let
w(χ) = (1 + χ)(w − p) + p

and let

(χ)

Wk

= {w(χ) | w ∈ Wk }

be a scaled version of Wk about p, where the scaling factor is 1 + χ. To extend this scaling to
(χ)
(χ)
W = Wkℓ , given w = (w1 , . . . , wℓ ) ∈ W, let w(χ) = (w1 , . . . , wℓ ) and let
W(χ) = {w(χ) | w ∈ W}.
A fact we use is that for 1 ≤ i ≤ ℓ, 1 ≤ j ≤ k, and w = (w1 , . . . , wℓ ) ∈ W
1
1
(χ)
|wij − wij | = |(1 + χ)(wij − ) + − wij | ≤ |χ|.
k
k
Lemma 19
8

R

W |ζt (w)

− ζF (w)|dw ≤ γt .

We characterize investment strategies for which Rt is log-concave in Theorem 26

17

Proof: Let W′ = W(−kσ) be the “scaled-in” version of W, as defined in Remark 10. By Lemma 16,
1
′ | ≤ kσ = δ ( γt ) for all i and j, R (w′ ) ≥
since |wij − wij
γ Rt (w) and
t
t 2
1+ t
2

Z

W′

Rt (w)dw ≥

1
1 + γ2t

Z

W

Rt (w)dw.

(17)

Let Weq = {w ∈ W | Ft (w) = Rt (w)} be the subset of W where Ft (·) and Rt (·) are equal; W′ ⊂ Weq
′ ≥ σ for all i and j. Let W = {w ∈ W | ζ (w) ≥ ζ (w)} be the
since, by construction of w′ , wij
+
F
t
subset of W where ζF (·) is at least ζt (·) and let W− = W − W+ . We bound
Z
Z
Z
(ζt (w) − ζF (w))dw
(ζF (w) − ζt (w))dw +
|ζF (w) − ζt (w)|dw =
by bounding

R

W−

W+

W

W− (ζt

Z

− ζF ), which also gives a bound for

W+

Since Ft ≤ Rt ,

R

W Ft

(ζF − ζt ) =
≤

R

W Rt



1−

Z

ζF

W−

and ζF (w) =

W+ and W− ⊂ W − W′ . We have
Z

W−

(ζt (w) − ζF (w))dw ≤

Z





− 1−

F
R t (w)
W Ft

≥

Z

ζt (w)dw =

R

γt
1
,
γt ≤
1+ 2
2

W+ (ζF

ζt
W−

R
R t (w)
W Rt

W−W′

≤ 1−

R



− ζt ), since
=

Z

W−

(ζt − ζF ).

= ζt (w) for w ∈ Weq ; thus W′ ⊂ Weq ⊂

′
W−W
R

Rt (w)dw

W Rt (w)dw

R
′ Rt (w)dw
= 1 − RW
W Rt (w)dw

where the second-last inequality follows from (17). This completes the proof.
Henceforth, we are concerned with sampling from W with probability proportional to Ft (·). We
use the Metropolis algorithm described above, replacing Rt (·) with Ft (·); we must refine our grid
spacing δt so that (14) is satisfied by Ft ; let δt′ be the new grid spacing.
Lemma 20 Suppose that the conditions of Lemma 16 are satisfied. Given ν > 0, let δt′ (ν) = δt′ =
ν
ν
′
′
′
3Γc′ mt4 kℓ = δt ( Γ ), where Γ appears in (16). For w, w ∈ W such that |wij − wij | ≤ δt (ν) for all
1 ≤ i ≤ ℓ and 1 ≤ j ≤ k, (1 + ν)−1 Ft (w) ≤ Ft (w′ ) ≤ (1 + ν)Ft (w).
Proof: By Lemma 16, Rt (w) and Rt (w′ ) differ by at most a factor 1+ Γν . For each i and j, fij (w)
Q Q
Q Q
′
and fij (w′ ) differ by at most a factor eΓδt (ν) and hence ℓi=1 kj=1 fij (w) and ℓi=1 kj=1 fij (w′ )
′

ν

differ by at most a factor ekℓΓδt (ν) = e 3c′ mt4 . Hence, for Γ ≥ 2 and sufficiently large t, Ft (w) and
Ft (w′ ) differ by at most a factor 1 + ν.
We are now ready to use Theorem 17 to select τ so that the resulting distribution pτ satisfies
(12) (Theorem 24) and (13) (Theorem 25), with pτ in place of π̃t and Ft in place of Rt . We begin
with some preliminary lemmas.
Lemma 21 There is a constant β > 0 such that log
defined in Remark 6.
18

1
π∗

2

≤ kℓΓσ + kℓ log δβ′ + t log 2mt
ε , where ε is
t

Proof: Take β such that the number of points in Ω is at most ( δβ′ )(k−1)·ℓ . For w1 , w2 ∈ Ω, the
t
ratio of single-day returns on day t′ using w1 and w2 is
ε
St′ (w1 ) · xt′
≥
′
St′ (w2 ) · xt′
2m(t + 1)2
by Remark 6 and Lemma 6. The ratio of the cumulative returns up to day t is
Rt (w1 )  ε t
≥
,
Rt (w2 )
2mt2
t
δt′ (k−1)ℓ
ε
≥
(
. Factoring in the maximum dampening effect of the fij ,
and thus P Rt (w)
)
2
β
2mt
w∈Ω Rt (w)

′
2
t
δ
1
ε
π∗ ≥ e−kℓΓσ ( βt )(k−1)ℓ 2mt2 and log π∗ ≤ kℓΓσ + kℓ log δβ′ + t log 2mt
ε .
t

Lemma 22 M ≤ 4



2m(t+1)2
ε

2

2

.
log 2m(t+1)
ε

Proof: As stated in Remark 8, the initial distribution is either p0 = π̃t−1 or π̃t−2 . It turns out
(w)
≤ 2 by (13) and
that the worst case happens when p0 = π̃t−2 . For all w ∈ Ω, π̃πt−2
t−2 (w)
P
Ft (w)
Ft−2 (w)
πt−2 (w)
= P
· w∈Ω
πt (w)
Ft (w)
w∈Ω Ft−2 (w)
′
Ft−2 (w) Ft (w )
Ft (w)
≤
·
(by Lemma 6, where w′ = arg max
)
′
w∈Ω Ft−2 (w)
Ft (w) Ft−2 (w )
Rt−2 (w) Rt (w′ )
=
·
(since the {fij (·)}i,j remain constant with time)
Rt (w) Rt−2 (w′ )

2
2m(t + 1)2
(St (w′ ) · xt )(St−1 (w′ ) · xt−1 )
,
≤
=
(St (w) · xt )(St−1 (w) · xt−1 )
ε
where the final inequality follows from the discussion in the proof of Lemma 21. This proves the
(w)
(w) πt−2(w)
result since π̃πt−2
= π̃πt−2
.
t (w)
t−2(w) πt (w)
Lemma 23 πe ≤ (1 + ν)4 (1 + γ2t )e−Γσ , where ν appears in the definition of δt′ in Lemma 20, γt
appears in (12), and Γ and σ appear in (16).
Proof: Extend our δt′ -hypercube partition of W to the hyperplane containing W and let Ψ be the
set of centers of the hypercubes in this extended partition. For K ⊂ Rkℓ , let ΨK be the set of grid
points w ∈ Ψ such that C(w) ∩ K 6= ∅, so that Ω = ΨW . By Lemma 20, for K ⊂ W,
Z
X
X
1
Ft (w)dw ≤ (1 + ν)
Ft (w)Vol(C(w) ∩ K).
(18)
Ft (w)Vol(C(w) ∩ K) ≤
1+ν
K
w∈ΨK

w∈ΨK

Using the notation of Lemma 19, let W′ = W(−kσ) be a “scaled-in” version of W; we showed in
Lemma 19 that for w ∈ W′ , Ft (w) = Rt (w) and that
Z
Z
Z
1
Rt (w)dw ≥
Ft (w)dw =
Rt (w)dw.
(19)
1 + γ2t W
W′
W′
19

′

Let W′′ = W(δt (ν)) be a “scaled-out” version of W and extend the domains of Ft (·) and Rt (·) to
W′′ by defining Ft (w′′ ) = Ft (w̄′′ ) and Rt (w′′ ) = Rt (w̄′′ ) for w′′ ∈ W′′ − W, where w̄′′ is the point
where the line between w′′ and pℓ = (p, . . . , p) ∈ W intersects the boundary of W. By Lemma 20
and the construction of the extension of Rt , Rt (w′′ ) ≤ (1 + ν)Rt (w) and
Z
Z
Rt (w)dw.
(20)
Rt (w)dw ≤ (1 + ν)
W′′

W′′ ,

W

W′′

By construction of
C(w) ⊂
for w ∈ Ωe ; from the definition of Ft and the choice of δt′ ,
−Γσ
Ft (w) ≤ (1 + ν)e
Rt (w) for w ∈ Ωe . Using these facts,
P
P
(k−1)ℓ
(1 + ν)e−Γσ w∈Ωe Rt (w)
δt
w∈Ωe Ft (w)
P
≤ (k−1)ℓ ·
πe = P
δt
w∈Ω Ft (w)
w∈Ω Ft (w)
P
′′
w∈ΨW′′ Vol(C(w) ∩ W )Rt (w)
(k−1)ℓ
−Γσ P
≤ (1 + ν)e
)
(since Vol(C(w)) = δt
w∈ΨW Vol(C(w) ∩ W)Ft (w)
R
−Γσ (1 + ν) R W′′ Rt (w)dw
≤ (1 + ν)e
(by (18))
1
(1+ν) W Ft (w)dw
R
γt
′′ Rt (w)dw
≤ (1 + ν)4 (1 + )e−Γσ (by (19) and (20)).
≤ (1 + ν)3 e−Γσ RW
2
W′ Ft (w)dw

Remark 11 We simplify notation below by using O∗ (·) notation, which ignores logarithmic and
constant terms. For our purposes, f (·) = O∗ (g(·)) if there exists a constant C ≥ 0 such that f (·) =
ν
ε2
∗
O(g(·) log C (kℓmt/ε)). The values derived above in this notation are γt = O∗ ( mt
4 ), δt = O ( mt4 kℓ ),
2
2
4
σ = O∗ ( m2 εt8 k2 ℓ ), δt′ = O∗ ( Γmtν4 kℓ ), log π1∗ = O∗ (kℓΓσ + t), M = O∗ ( mε2t ), and πe = O∗ (e−Γσ ).
2 t8 k 2 ℓ
ε2

Theorem 24 Letting Γ = O∗ ( σ1 ) = O∗ ( m
7 ℓ6 m6 t24
satisfies (12) after τ = O∗ ( k κν
) steps.
2 ε4

), the random walk reaches a distribution π̃ that

Proof: We show how to bound the right-side of (15), where the grid spacing δt has been replaced
2
, can be made exponentially small in Γ by choosing Γ = O∗ ( σ1 ). The
by δt′ . The second term, M πκδe kℓd
′2
t

−

value of τ stated in the theorem is large enough to make the first term, e
small in τ .

2
κτ δt′
kℓd2

log

1
π∗ ,

exponentially

Theorem 25 Suppose that the distribution pτ0 obtained after τ0 steps satisfies
X
|π(w) − pτ0 (w)| ≤ γt .
w∈Ω

After

τ0′

≥

τ0

τ0 −log

1
−log γ1
π∗
t

log

1
π∗

= O∗ (τ0 (kℓ + t)) steps, the resulting distribution pτ0′ satisfies
max
w∈Ω

pτ0′ (w)
π(w)

which implies (13).
20

− 1 ≤ 1,

1
2

pτ (w)
π(w) − 1 so
1
1
λ log π∗ , then

ˆ ) = maxw∈Ω
|π(w) − pτ (w)| and d(τ

that d(τ0 ) ≤ 21 γt .
ˆ ) ≤ 1, where
d(τ
Aldous and Fill prove [1, Equations (5) and (6)] that if τ ≥
π∗ = minw∈Ω πt (w) is as defined in the statement of Theorem 17 and λ is the second-largest
eigenvalue of the steady-state transition matrix P of πt .
Proof:

Let d(τ ) =

P

w∈Ω

τ0 −log

1

−log

1

log

1

+log

π∗
γt
π∗
= 1−
To prove the bound on τ0′ , we show that λ ≥
τ0
τ0
appealing to a result from Sinclair [16, Proposition 1 (i)], which states that

τ0 ≤

log

1
π∗

+ log γ1t

1−λ

1
γt

. We do this by

.9

Solving for λ yields the bound for τ0′ . The O∗ (·) bound comes from the fact that Γσ = O∗ (1) and
that log γ1t and log π1∗ are low-order terms relative to the τ0 obtained in Theorem 24.

4.3

Application to Investment Strategies

The efficient sampling techniques of this section are applicable to investment strategies S whose
return functions Rn (S(·)) are log-concave. Theorem 26 and Corollary 27 characterize such functions.
2

S
= 0.
Theorem 26 Given investment strategy S, suppose that for all parameters wi and wj , ∂w∂i ∂w
j
Then Rt (w) = Rt (S(w)) is log-concave.
Qn−1
Proof: Let rt (w) = St (w) · xt , so that Rn (w) = t=0
rt (w). Since log-concave functions are
closed under multiplication, we need only show that rt (w) is log-concave. The gradient vector of
1 ∂rt (w)
log rt (w) has i-th element ∂ log∂wrti(w) = rt (w)
∂wi and the matrix of second derivatives has (i, j)-th
element
1 ∂ 2 rt (w)
1 ∂rt (w) ∂rt (w)
1 ∂rt (w) ∂rt (w)
+
=−
−
rt (w)2 ∂wi
∂wj
rt (w) ∂wi ∂wj
rt (w)2 ∂wi
∂wj
2 (w)
P
∂ 2 Stι (w)
since ∂∂writ∂w
= m
ι=1 ∂wi ∂wj · xtι = 0 by assumption. The matrix of second derivatives is negative
j
semidefinite, implying that log rt (w) is a concave function.

Corollary 27 Universalizations of the following investment strategies can be computed using the
sampling techniques of this section.
1. The trading strategies MA[k] and SR[k] with long/short allocation functions gℓ (x) and hp (x, y)
respectively; and
2. The portfolio strategies CRP and CRP-S.
Proof: The result follows from a straightforward differentiation of the investment descriptions of
these strategies.
9

Strictly speaking, this result pertains to λmax , the second-largest absolute value of the eigenvalues of P , but as
Sinclair discusses [16, Page 355] the smallest eigenvalue is unimportant, as P can be modified so that all eigenvalues
are positive without affecting mixing times beyond a constant factor.

21

5

Further Research

We have introduced in this paper a general framework for universalizing parameterized investment
strategies. It would be interesting to see whether the proof of Theorem 5 can be optimized so that
existing universal portfolio proofs for CRP [3, 5, 6] are a special case of Theorem 5. These proofs
not only prove that Ln (U(CRP)) converges to Ln (CRP(wn∗ )), but also prove a bound on the rate
of convergence,


n+m−1
Rn (CRP(wn∗ ))
≤
≤ (n + 1)m−1 .
m−1
Rn (U(CRP))
It would also be interesting to study other trading and portfolio strategies that fit in our universalization framework and to see how our universalization algorithms perform in empirical tests.

References
[1] D. Aldous and J. A. Fill. Advanced L2 techniques for bounding mixing times. In Reversible
Markov Chains and Random Walks on Graphs. 1999. Unpublished monograph. Available at
http://stat-www.berkeley.edu/users/aldous/book.html.
[2] D. Applegate and R. Kannan. Sampling and integration of near log-concave functions. In
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 156–163,
1991.
[3] A. Blum and A. Kalai. Universal portfolios with and without transaction costs. Machine
Learning, 35(3):193–205, 1999.
[4] W. Brock, J. Lakonishok, and B. LeBaron. Simple technical trading rules and the stochastic
properties of stock returns. Journal of Finance, 47(5):1731–1764, 1992.
[5] T. M. Cover. Universal portfolios. Mathematical Finance, 1(1):1–29, Jan. 1991.
[6] T. M. Cover and E. Ordentlich. Universal portfolios with side information. IEEE Transactions
on Information Theory, 42(2):348–363, March 1996.
[7] P. Diaconis and L. Saloff-Coste. Logarithmic Sobolev inequalities for finite Markov chains.
Annals of Applied Probability, 6:695–750, 1996.
[8] G. B. Folland. Real Analysis: Modern Techniques and their Applications. John Wiley & Sons,
New York, 1984.
[9] A. Frieze and R. Kannan. Log-Sobolev inequalities and sampling from log-concave distributions. Annals of Applied Probability, 9:14–26, 1999.
[10] H. M. Gartley. Profits in the Stock Market. Lambert Gann Publishing Company, Pomeroy,
WA, 1935.
[11] D. P. Helmbold, R. E. Schapire, Y. Singer, and M. K. Warmuth. On-line portfolio selection
using multiplicative updates. Mathematical Finance, 8(4):325–347, 1998.

22

[12] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the
American Statistical Association, 58:13–30, March 1963.
[13] A. Kalai and S. Vempala. Efficient algorithms for universal portfolios. In Proceedings of the
41st Annual IEEE Symposium on Foundations of Computer Science, pages 486–491, 2000.
[14] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equation
of state calculation by fast computing machines. Journal of Chemical Physics, 21:1087–1092,
1953.
[15] E. Ordentlich and T. M. Cover. Online portfolio selection. In Proceedings of the 9th Annual
Conference on Computational Learning Theory, pages 310–313, 1996.
[16] A. Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow.
Combinatorics, Probability and Computing, 1:351–370, 1992.
[17] R. Sullivan, A. Timmermann, and H. White. Data-snooping, technical trading rules and the
bootstrap. Journal of Finance, 54:1647–1692, 1999.
[18] R. Wyckoff. Studies in Tape Reading. Fraser Publishing Company, Burlington, VT, 1910.

23

