text:
# Fast Universalization of Investment Strategies with Provably Good Relative Returns

## 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 to invest capital. Typically, an investment strategy is parameterized by a vector $`𝐰^{}=_{i=1}^{\mathrm{}}^i`$ 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  and the subject of several extensions and generalizations . The CRP strategy maintains a constant proportion of total wealth in each stock, where the proportions are dictated by the parameters given to the strategy. In a stock market with $`m`$ stocks, the parameter space for the CRP strategy is

$$𝒲_m=\{𝐰[0,1]^m|\underset{i=1}{\overset{m}{}}w_i=1\},$$

the set of vectors in $`^m`$ whose components are between $`0`$ and $`1`$ and add up to $`1`$. Given a *portfolio vector* $`𝐰=(w_1,\mathrm{},w_m)𝒲_m`$, $`w_i`$ tells us the proportion of wealth to invest in stock $`i`$, for $`1im`$. 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 . 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 $`\text{CRP}(\frac{1}{2},\frac{1}{2})`$ strategy, our wealth will increase exponentially, by a factor of $`(\frac{1}{2}1+\frac{1}{2}2)\times (\frac{1}{2}1+\frac{1}{2}\frac{1}{2})=\frac{3}{2}\times \frac{3}{4}=\frac{9}{8}`$ every two days.

Cover developed an investment strategy that effectively distributes wealth uniformly over all portfolio vectors $`𝐰𝒲_m`$ on the first day and executes the CRP strategy with daily rebalancing according to each $`𝐰`$ on the (infinitesimally small) proportion of wealth initially allocated to each $`𝐰`$. Cover showed that the *average daily log-performance*111The 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. 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 short222A short position in a stock, discussed in Section 2.1, allows us to earn a profit when the stock declines in value. 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  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`$ stocks333We 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.. *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* $`_t`$ and a *parameter vector* $`𝐰`$, and returns an *investment description* $`S_t(𝐰)`$ specifying how to allocate our capital at time $`t`$. The environment vector $`_t`$ contains historic market information, including stock price history, trading volumes, etc.; the parameter vector $`𝐰`$ is independent of $`_t`$ and specifies exactly how the strategy $`S`$ should operate; the investment description $`S_t(𝐰)=(S_{t1}(𝐰),\mathrm{},S_{tm}(𝐰))`$ is a vector specifying the proportion of wealth to put in each stock, where we put a fraction $`S_{ti}(𝐰)`$ of our holdings in stock $`i`$, for $`1im`$. For example, CRP is an investment strategy; coupled with a portfolio vector $`𝐰`$ it tells us to “rebalance our portfolio on a daily basis according to $`𝐰`$”; its investment description, $`\text{CRP}_t(𝐰)=𝐰`$, is independent of the market environment $`_t`$.

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 $`k2`$, let

$$𝒲_k=\{𝐰=(w_1,\mathrm{},w_k)[0,1]^k|\underset{i=1}{\overset{k}{}}w_i=1\}.$$
(1)
###### Remark 1

$`𝒲_k`$ is a $`(k1)`$-dimensional simplex in $`^k`$. The investment strategies that we describe below are parameterized by vectors in $`𝒲_k^{\mathrm{}}=𝒲_k\times \mathrm{}\times 𝒲_k`$ ($`\mathrm{}`$ times) for some $`k2`$ and $`\mathrm{}1`$. We may write $`𝐰𝒲_k^{\mathrm{}}`$ in the form $`𝐰=(𝐰_1,\mathrm{},𝐰_{\mathrm{}})`$, where $`𝐰_\iota =(w_{\iota 1},\mathrm{},w_{\iota k})`$ for $`1\iota \mathrm{}`$.

### 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 $`p_t`$ denote the stock price at the beginning of day $`t`$, the value of our investment will change by a factor of $`x_t=\frac{p_{t+1}}{p_t}`$ 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 $`\alpha `$ 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 $`\alpha (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 $`x_t=\frac{p_{t+1}}{p_t}<1+\alpha `$ during the day. Then the value of our investment in the short position changes by a factor of $`x_t^{}=1+\frac{1x_t}{\alpha }`$ 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/\alpha `$ worth of shares. Combining the proceeds of the stock sale with our margin account balance, we will have a total of $`v+v/\alpha `$ dollars. At the end of the day, it will cost $`x_tv/\alpha `$ dollars to buy the shares back, and we will be left with $`v+\frac{v}{\alpha }x_t\frac{v}{\alpha }`$ dollars, which is positive since $`x_t<1+\alpha `$. Thus, our investment of $$`v`$ in the short position has changed by a factor of $`1+\frac{1x_t}{\alpha }`$, as claimed. ∎

Should the price of the underlying stock change by a factor greater than $`1+\alpha `$, we will lose more money than we initially put in. We will assume that the margin requirement $`\alpha `$ is sufficiently large that the daily price change of the stock is always less than $`1+\alpha `$.

###### Remark 2

This assumption can be eliminated by purchasing a *call option* on the stock with some strike price $`p<(1+\alpha )p_t`$. 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 $`x_t>1`$) or additional shares are shorted (if $`x_t<1`$) so that the collateral in the margin account is exactly an $`\alpha `$ fraction of the value of the shorted shares. This ensures that the value of a short position changes by a factor, $`x_t^{}=1+\frac{1x_t}{\alpha }`$, 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 $`T_t=(T_{t1},T_{t2})`$, where $`T_{t1}`$ and $`T_{t2}`$ are the fraction of wealth to put in a long and short position respectively.

###### Remark 3

Let $`D=T_{t1}T_{t2}/\alpha `$ 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 $`1D`$ fraction in cash; if $`D<0`$, investors should invest $`D`$ in the short position and $`1D`$ 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 $`T_t`$ as $`t\mathrm{}`$ (see, for example, (3) below).

We now describe some commonly used and researched trading strategies  and show how they can be parameterized.

#### $`\text{MA}[k]`$: Moving Average Cross-over with $`k`$-day Memory.

In traditional applications  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 $`t0`$, let $`𝐯_t=(v_{t1},\mathrm{},v_{tk})`$ be the *price-history vector* over the previous $`k`$ days, where $`v_{tj}`$ is the stock price on day $`tj`$. Assume that the stock prices have been normalized such that $`0<v_{tj}1`$. Let $`(𝐰_F,𝐰_S)𝒲_k^2`$ (where $`𝒲_k`$ 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 $`𝐰_F𝐯_t`$ and $`𝐰_S𝐯_t`$ respectively. Since the prices have been normalized to the interval $`(0,1]`$, $`1(𝐰_F𝐰_S)𝐯_t1`$. Let $`g:[1,1][0,1]`$ be the *long/short allocation function*. The idea is that $`g((𝐰_F𝐰_S)𝐯_t)`$ represents the proportion of wealth that we invest in a long position. The full investment description for the $`\text{MA}=\text{MA}[k]`$ trading strategy is

$$\text{MA}_t(𝐰_F,𝐰_S)=(g((𝐰_F𝐰_S)𝐯_t),1g((𝐰_F𝐰_S)𝐯_t).$$

Note that the dimension of the parameter space for $`\text{MA}[k]`$ is $`2(k1)`$ since each of $`𝐰_F`$ and $`𝐰_S`$ are taken from $`(k1)`$-dimensional spaces. Possible functions for $`g`$ include

$`g_s(x)`$ $`=\{\begin{array}{cc}0\hfill & \text{if }x<0\hfill \\ 1\hfill & \text{otherwise}\hfill \end{array}`$ (step function); (2)
$`g_{(t)}(x)`$ $`=\{\begin{array}{cc}0\hfill & \text{if }x<\frac{1}{t}\hfill \\ \frac{t}{2}(x+\frac{1}{t})\hfill & \text{if }\frac{1}{t}x\frac{1}{t}\hfill \\ 1\hfill & \text{if }\frac{1}{t}<x\hfill \end{array}`$ (linear step approximation); (3)
and the line

$$g_{\mathrm{}}(x)=\frac{x+1}{2}$$
(4)
that intersects $`g_s(x)`$ at the extreme points $`x=\pm 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 $`g_s(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 $`g_s()`$. 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_{\mathrm{}}()`$ can be used with the results of Section 4, to allow for efficient computation of the universalization algorithm.

#### $`\text{SR}[k]`$: Support and Resistance Breakout with $`k`$-day Memory.

Discussed as early as Wyckoff  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 . To generalize this rule, given day $`t0`$, let $`\underset{¯}{𝐯}_t=(\underset{¯}{v}_{t1},\mathrm{},\underset{¯}{v}_{tk})`$ and $`\overline{𝐯}_t=(\overline{v}_{t1},\mathrm{},\overline{v}_{tk})`$ be the minimum and maximum price histories, where $`\underset{¯}{v}_{tj}`$ and $`\overline{v}_{tj}`$ are the minimum and maximum prices over the previous $`j`$ days, normalized so that they are in the range $`(0,1]`$. Let $`𝐰𝒲_k`$ be the weights to compute the support and resistance levels, so these levels on day $`t`$ are given by $`s_t=𝐰\underset{¯}{𝐯}_t`$ and $`r_t=𝐰\overline{𝐯}_t`$ respectively.

###### Lemma 2

The support level is bounded above by the resistance level: $`s_tr_t`$.

###### Proof.

This follows from the fact that for all $`1jk`$, $`\underset{¯}{v}_{tj}\overline{v}_{tj}`$. ∎

The long/short allocation function will be denoted by $`h:\{(x,y)[1,1]^2|xy\}[0,1]`$. Let $`p_t`$ be the current stock price (normalized to $`(0,1]`$ along with $`\underset{¯}{𝐯}_t`$ and $`\overline{𝐯}_t`$). The idea is that $`h(p_tr_t,p_ts_t)`$ tells us the proportion of wealth that we invest in a long position. The full investment description for the $`\text{SR}=\text{SR}[k]`$ trading strategy is

$$\text{SR}_t(𝐰)=(h(p_tr_t,p_ts_t),1h(p_tr_t,p_ts_t)).$$

The value of $`h`$ need only be defined on $`\{(x,y)[1,1]^2|xy\}`$ since, by Lemma 2, $`s_tr_t`$. A possible function for $`h`$ is

$$h_s(x,y)=\{\begin{array}{cc}0\hfill & \text{if }xy0\hfill \\ \frac{1}{\alpha +1}\hfill & \text{if }x<0<y\hfill \\ 1\hfill & \text{if }yx0\hfill \end{array}\text{(step function),}$$
(5)
where the investment allocation $`\frac{1}{\alpha +1}`$ long, $`1\frac{1}{\alpha +1}=\frac{\alpha }{\alpha +1}`$ short is equivalent to having no position in the stock, since the return from such an allocation is $`\frac{x_t}{\alpha +1}+(1+\frac{1x_t}{\alpha })\frac{\alpha }{\alpha +1}=1`$. Other possibilities include a continuous approximation $`h_{(t)}(x,y)`$ to $`h_s(x,y)`$ with maximum slope at most $`\frac{1}{t}`$ (defined similarly to $`g_{(t)}(x)`$) (6), or the plane

$$h_p(x,y)=\frac{(x+1)\alpha }{2(\alpha +1)}+\frac{y+1}{2(\alpha +1)}$$
(7)
that intersects $`h_s(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 $`P_t=(P_{t1},\mathrm{},P_{tm})`$, where $`0P_{ti}1`$ and $`_{i=1}^mP_{ti}=1`$. We put a fraction $`P_{ti}`$ of our wealth in stock $`i`$ at time $`t`$.

#### CRP: Constantly Rebalanced Portfolio .

The parameter space for the CRP strategy is $`𝕎=𝒲_m`$. The investment description is $`\text{CRP}_t(𝐰)=𝐰`$: at the beginning of each day, we invest a $`w_i`$ proportion of our wealth in stock $`i`$.

#### CRP-S: Constantly Rebalanced Portfolio with Side Information.

Cover and Ordentlich  consider a generalization of CRP. Rather than rebalancing our holdings according to a single portfolio vector $`𝐰𝒲_m`$ every day, we have $`k`$ vectors $`𝐰_1,\mathrm{},𝐰_k𝒲_m`$ and a side information state $`y_t\{1,\mathrm{},k\}`$ that classifies each day $`t`$ into one of $`k`$ possible categories; on day $`t`$ we rebalance our holdings according to $`𝐰_{y_t}`$. 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, $`𝐰_1^{},\mathrm{},𝐰_k^{}𝒲_m`$, where $`𝐰_j^{}`$ is used on days $`t`$ when the side information state is $`y_t=j`$. We generalize this further by allowing portions of our wealth to be rebalanced according to several of the $`𝐰_j`$ every day. Suppose that the side information is encapsulated in some vector $`𝐯^{\mathrm{}}`$, for some $`\mathrm{}`$. This vector can contain information about specific stocks, such as historic performance and company fundamentals, or macro-economic indicators such as inflation and unemployment. Let $`𝐟=(f_1,\mathrm{},f_k):^{\mathrm{}}[0,1]^k`$ be some function satisfying $`_{j=1}^kf_j(𝐯)=1`$ for all $`𝐯^{\mathrm{}}`$. The parameter space is $`𝒲_m^k`$; the investment description is $`\text{CRP-S}_t(𝐰_1,\mathrm{},𝐰_k)=_{j=1}^kf_j(𝐯_t)𝐰_j`$, where $`𝐯_t`$ is the indicator vector for day $`t`$. Under such a scheme, we have the flexibility of splitting our wealth among multiple sets of portfolios $`𝐰_1,\mathrm{},𝐰_k`$ on any given day, rather than being forced to choose a single one. For example, assume that $`𝐯`$ is a $`k`$-dimensional vector, with each $`v_i`$ corresponding to portfolio $`𝐰_i`$. Define $`𝐟:^k[0,1]^k`$ by $`f_i(𝐯_t)=\frac{v_{ti}}{_{\iota =1}^kv_{t\iota }}`$, so that our allocation is biased towards portfolios corresponding to higher indicators while still maintaining a position in the others.

#### $`\text{IA}[k]`$: $`k`$-Way Indicator Aggregation.

For each day $`t0`$, suppose that each stock $`i`$ has a set of $`k`$ indicators $`𝐯_{ti}=(v_{ti1},\mathrm{},v_{tik})`$, where each $`v_{tij}(0,1]`$ and, for $`1jk`$, $`v_{t1j},\mathrm{},v_{tmj}`$ have been normalized such that there is at least one $`i`$ such that $`v_{tij}=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 $`𝕎=𝒲_k`$ and the investment description is

$$\text{IA}_t(𝐰)=(\frac{𝐰𝐯_{t1}}{_{i=1}^m𝐰𝐯_{ti}},\mathrm{},\frac{𝐰𝐯_{tm}}{_{i=1}^m𝐰𝐯_{ti}}).$$

## 3 Universalization of Investment Strategies

### 3.1 Universalization Defined

In a typical stock market, wealth grows geometrically. On day $`t0`$, let $`𝐱_t`$ be the *return vector* for day $`t`$, the vector of factors by which stock prices change on day $`t`$. The return vector corresponding to a trading strategy on a single stock is $`(x_t,1+\frac{1x_t}{\alpha })`$, where $`x_t`$ is the factor by which the price of the stock changes and $`1+\frac{1x_t}{\alpha }`$ 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 $`(x_{t1},\mathrm{},x_{tm})`$, where $`x_{ti}`$ is the factor by which the price of stock $`i`$ changes, where $`1im`$. Henceforth, we do not make a distinction between return vectors corresponding to trading and portfolio strategies; we assume that $`𝐱_t`$ is appropriately defined to correspond to the investment strategy in question. For an investment strategy $`S`$ with parameter vector $`𝐰`$, the *return of $`S(𝐰)`$* during the $`t`$-th day—the factor by which our wealth changes on the $`t`$-th day when invested according to $`S(𝐰)`$—is $`S_t(𝐰)𝐱_t=_{i=1}^mS_{ti}(𝐰)x_{ti}`$ (recall that $`S_t(𝐰)`$ is the investment description of $`S(𝐰)`$ for day $`t`$, which is a vector specifying the proportion of wealth to put in each stock). Given time $`n>0`$, let $`_n(S(𝐰))=_{t=0}^{n1}S_t(𝐰)𝐱_t`$ be the *cumulative return of $`S(𝐰)`$ up to time $`n`$*; we may write $`_n(𝐰)`$ in place of $`_n(S(𝐰))`$ if $`S`$ is obvious from context. We analyze the performance of $`S`$ in terms of the *normalized log-return* $`_n(𝐰)=_n(S(𝐰))=\frac{1}{n}\mathrm{log}_n(𝐰)`$ of the wealth achieved.

For investment strategy $`S`$, let $`𝐰_n^{}=\mathrm{arg}\mathrm{max}_𝐰^{}_n(S(𝐰))`$ be the parameters that maximize the return of $`S`$ up to day $`n`$.444As mentioned above, $`𝐰_n^{}`$ can only be computed with hindsight. An investment strategy $`U`$ *universalizes* (or *is universal for*) $`S`$ if555Unlike previously discussed investment strategies, the behavior of $`U`$ is fully defined without an additional parameter vector $`𝐰`$.

$$_n(U)=_n(S(𝐰_n^{}))\mathrm{o}(1)$$

for all environment vectors $`_n`$. 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 $`𝕎`$ be the parameter space for $`S`$ and let $`\mu `$ be the uniform measure over $`𝕎`$. Our universalization algorithm for $`S`$, $`𝒰(S)`$, is a generalization of Cover’s original result . The investment description $`𝒰_t(S)`$ for the universalization of $`S`$ on day $`t>0`$ is a weighted average of the $`S_t(𝐰)`$ over $`𝐰𝕎`$, with greater weight given to parameters $`𝐰`$ that have performed better in the past (i.e. $`_t(𝐰)`$ is larger). Formally, the investment description is

$$𝒰_t(S)=\frac{_𝕎S_t(𝐰)_t(𝐰)𝑑\mu (𝐰)}{_𝕎_t(𝐰)𝑑\mu (𝐰)}=\frac{_𝕎S_t(𝐰)_t(S(𝐰))𝑑\mu (𝐰)}{_𝕎_t(S(𝐰))𝑑\mu (𝐰)},$$
(8)
where we take $`_0(𝐰)=1`$ for all $`𝐰𝕎`$.666Cover’s algorithm is a special case of this, replacing $`S_t(𝐰)`$ with $`𝐰`$.

###### Remark 5

The definition of universalization can be expanded to include measures other than $`\mu `$, but we consider only $`\mu `$ in our results.

###### Lemma 3 ()

The cumulative $`n`$-day return of $`𝒰(S)`$ is

$$_n(𝒰(S))=_𝕎_n(𝐰)𝑑\mu (𝐰)=𝔼\left(_n(𝐰)\right),$$

the $`\mu `$-weighted average of the cumulative returns of the investment strategies $`\{S(𝐰)|𝐰𝕎\}`$.

###### Proof.

The return of $`𝒰(S)`$ on day $`t`$ is $`𝒰_t(S)𝐱_t`$, where $`𝐱_t`$ is the return vector for day $`t`$. The cumulative $`n`$-day return of $`𝒰(S)`$ is

$`_n(𝒰(S))`$ $`=`$ $`{\displaystyle \underset{t=0}{\overset{n1}{}}}𝒰_t(S)𝐱_t={\displaystyle \underset{t=0}{\overset{n1}{}}}{\displaystyle \frac{_𝕎S_t(𝐰)_t(𝐰)𝑑\mu (𝐰)}{_𝕎_t(𝐰)𝑑\mu (𝐰)}}𝐱_t`$
$`=`$ $`{\displaystyle \underset{t=0}{\overset{n1}{}}}{\displaystyle \frac{_𝕎(S_t(𝐰)𝐱_t)_t(𝐰)𝑑\mu (𝐰)}{_𝕎_t(𝐰)𝑑\mu (𝐰)}}={\displaystyle \underset{t=0}{\overset{n1}{}}}{\displaystyle \frac{_𝕎_{t+1}(𝐰)𝑑\mu (𝐰)}{_𝕎_t(𝐰)𝑑\mu (𝐰)}}.`$
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 $`\overline{S}`$ by

$$\overline{S}_t(𝐰)=(1\frac{\epsilon }{2(t+1)^2})S_t(𝐰)+\frac{\epsilon }{2m(t+1)^2}$$

for $`t0`$ and some fixed $`0<\epsilon <1`$. Rather than universalizing $`S`$, we instead universalize $`\overline{S}`$. Lemma 4 tells us that we do not lose much by doing this.

###### Lemma 4

For all $`n0`$, (1) $`_n(𝒰(\overline{S}))(1\epsilon )_n(𝒰(S))`$ and (2) $`_n(𝒰(\overline{S}))=_n(𝒰(S))\frac{\mathrm{o}(n)}{n}`$. (3) If $`𝒰(S)`$ is a universalization of $`S`$, then $`𝒰(\overline{S})`$ is a universalization of $`S`$ as well.

###### Proof.

Statements (2) and (3) follow directly from (1). Statement (1) follows from the fact that for all $`𝐰𝕎`$, $`_n(\overline{S}(𝐰))=_{t=0}^{n1}\overline{S}_t(𝐰)𝐱_t_{t=0}^{n1}(1\frac{\epsilon }{2(t+1)^2})S_t(𝐰)𝐱_t(1_{t=0}^{n1}\frac{\epsilon }{2(t+1)^2})_n(S(𝐰))(1\epsilon )_n(S(𝐰))`$. ∎

###### Remark 6

Henceforth, we assume that suitable modifications have been made to $`S`$ to ensure that $`S_{ti}(𝐰)\frac{\epsilon }{2m(t+1)^2}`$ for all $`1im`$ and $`t0`$.

###### Theorem 5

Given an investment strategy $`S`$, let $`𝕎=𝒲_k^{\mathrm{}}`$ (for some $`k2`$ and $`\mathrm{}1`$) be its parameter space. For $`1im`$, $`1\iota \mathrm{}`$ and $`1jk`$, assume that there is a constant $`c`$ such that $`\left|\frac{S_{ti}(𝐰)}{w_{\iota j}}\right|c(t+1)`$ for all $`𝐰𝕎`$. Then $`𝒰(S)`$ is a universalization of $`S`$.

To prove Theorem 5, we first prove some preliminary results.

###### Lemma 6

For nonnegative vector $`𝐚`$ and strictly positive vectors $`𝐛`$ and $`𝐱`$,

$$\underset{i}{\mathrm{min}}\frac{a_i}{b_i}\frac{𝐚𝐱}{𝐛𝐱}\underset{i}{\mathrm{max}}\frac{a_i}{b_i}.$$

###### Proof.

Assume that the components of $`𝐚`$ and $`𝐛`$ are strictly positive. Otherwise, the lemma holds trivially. Let $`i_{\mathrm{max}}=\mathrm{arg}\mathrm{max}_i\frac{a_i}{b_i}`$ and $`i_{\mathrm{min}}=\mathrm{arg}\mathrm{min}_i\frac{a_i}{b_i}`$, so that

$$\frac{a_i}{b_i}\frac{a_{i_{\mathrm{max}}}}{b_{i_{\mathrm{max}}}}\frac{a_i}{a_{i_{\mathrm{max}}}}\frac{b_i}{b_{i_{\mathrm{max}}}}\text{and}\frac{a_i}{b_i}\frac{a_{i_{\mathrm{min}}}}{b_{i_{\mathrm{min}}}}\frac{a_i}{a_{i_{\mathrm{min}}}}\frac{b_i}{b_{i_{\mathrm{min}}}}.$$

Then

$$\begin{array}{cccccc}& \hfill \frac{a_{i_{\mathrm{min}}}(x_{i_{\mathrm{min}}}+_{ii_{\mathrm{min}}}\frac{a_i}{a_{i_{\mathrm{min}}}}x_i)}{b_{i_{\mathrm{min}}}(x_{i_{\mathrm{min}}}+_{ii_{\mathrm{min}}}\frac{b_i}{b_{i_{\mathrm{min}}}}x_i)}& =& \frac{𝐚𝐱}{𝐛𝐱}& =& \frac{a_{i_{\mathrm{max}}}(x_{i_{\mathrm{max}}}+_{ii_{\mathrm{max}}}\frac{a_i}{a_{i_{\mathrm{max}}}}x_i)}{b_{i_{\mathrm{max}}}(x_{i_{\mathrm{max}}}+_{ii_{\mathrm{max}}}\frac{b_i}{b_{i_{\mathrm{max}}}}x_i)}\hfill \\ & \hfill \frac{a_{i_{\mathrm{min}}}}{b_{i_{\mathrm{min}}}}& & \frac{𝐚𝐱}{𝐛𝐱}& & \frac{a_{i_{\mathrm{max}}}}{b_{i_{\mathrm{max}}}}.\hfill \end{array}$$

Our next two results are related to the $`(k1)`$-dimensional volumes of some subsets of $`^k`$.

###### Lemma 7

The $`(k1)`$-dimensional volume of the simplex $`𝒲_k=\{𝐰[0,1]^k|_{i=1}^kw_i=1\}`$, defined in (1), is $`\frac{\sqrt{k}}{(k1)!}`$.

###### Proof.

By induction on $`k`$, it can be shown that the $`k`$-dimensional volume of the solid $`W_k(s)=\{𝐰|_{i=1}^kw_is\}`$ is $`\frac{s^k}{k!}`$. Written in terms of the length $`r`$ of the line segment passing between the origin and $`(\frac{s}{k},\mathrm{},\frac{s}{k})^k`$, the volume is $`\frac{1}{k!}r^kk^{\frac{k}{2}}`$ since $`s=r\sqrt{k}`$. Upon differentiation with respect to $`r`$, $`\frac{1}{(k1)!}r^{k1}k^{\frac{k}{2}}=\frac{1}{(k1)!}\sqrt{k}s^{k1}`$, we arrive at the $`(k1)`$-dimensional volume of the simplex $`𝒲_k(s)=\{𝐰|_{i=1}^kw_i=s\}`$. Setting $`s=1`$ yields the desired result. ∎

###### Lemma 8

The $`(k1)`$-dimensional volume of a $`(k1)`$-dimensional ball of radius $`\rho `$ embedded in $`𝒲_k`$ is $`\frac{\pi ^{\frac{k1}{2}}\rho ^{k1}}{\mathrm{\Gamma }(\frac{k1}{2}+1)}`$, where

$$\mathrm{\Gamma }(\mathrm{})=(\mathrm{}1)!\text{and}\mathrm{\Gamma }(\mathrm{}+\frac{1}{2})=(\mathrm{}\frac{1}{2})(\mathrm{}\frac{3}{2})\mathrm{}(\frac{1}{2})\sqrt{\pi }.$$

###### Proof.

This result is proven in Folland \[8, Corollary 2.56\]. ∎

Proof of Theorem 5:  ¿From Lemma 3, the return of $`𝒰(S)`$ is the average of the cumulative returns of the investment strategies $`\{S(𝐰)|𝐰𝕎\}`$. Let $`𝐰^{}=\mathrm{arg}\mathrm{max}_{𝐰𝕎}_n(S(𝐰))`$ be the parameters that maximize the return of $`S`$. We show that there is a set $`B`$ of nonzero volume around $`𝐰^{}`$ such that for $`𝐰B`$, the return $`_n(𝐰)`$ is close to the optimal return $`_n(𝐰^{})`$. 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 $`_n(𝐰)`$. From Remark 6 and our assumption in the statement of the theorem, for all $`𝐰`$, $`t`$, $`i`$, $`\iota `$, and $`j`$

$$\frac{\left|\frac{S_{ti}(𝐰)}{w_{\iota j}}\right|}{S_{ti}(𝐰)}c^{}m(t+1)^3,$$

where $`c^{}=\frac{2c}{\epsilon }`$. Using this fact and Lemma 6, the partial derivative of the return function $`_n(𝐰)=_n(S(𝐰))=_{t=0}^{n1}r_t(S(𝐰))`$ with respect to parameter $`w_{\iota j}`$ is

$`\left|{\displaystyle \frac{_n(𝐰)}{w_{\iota j}}}\right|`$ $``$ $`_n(𝐰){\displaystyle \underset{t=0}{\overset{n1}{}}}{\displaystyle \frac{\left|\frac{(S_t(𝐰)𝐱_t)}{w_{\iota j}}\right|}{S_t(𝐰)𝐱_t}}_n(𝐰){\displaystyle \underset{t=0}{\overset{n1}{}}}{\displaystyle \frac{_{i=1}^m\left|\frac{S_{ti}(𝐰)}{w_{\iota j}}\right|x_{ti}}{_{i=1}^mS_{ti}(𝐰)x_{ti}}}`$
$``$ $`_n(𝐰){\displaystyle \underset{t=0}{\overset{n1}{}}}c^{}m(t+1)^3c^{}_n(𝐰)mn^4`$
and

$$|_n(𝐰)|c^{}_n(𝐰)mn^4\sqrt{k\mathrm{}}.$$
(9)
We would like to take our set $`B`$ to be some $`d`$-dimensional ball around $`𝐰^{}`$; unfortunately, if $`𝐰^{}`$ is on (or close to) an edge of $`𝕎`$, the reasoning introduced at the beginning of this proof is not valid. We instead perturb $`𝐰^{}`$ to a point $`\stackrel{~}{𝐰}`$ that is at least

$$\rho =\frac{\gamma }{c^{}mn^4k^2\mathrm{}}$$

away from all edges, where $`0<\gamma <1`$ is a constant, and such that $`_n(\stackrel{~}{𝐰})`$ is close to $`_n(𝐰^{})`$. To illustrate the perturbation, let $`𝐰^{}=(𝐰_1^{},\mathrm{},𝐰_{\mathrm{}}^{})`$ where $`𝐰_\iota ^{}=(w_{\iota 1}^{},\mathrm{},w_{\iota k}^{})`$ and $`w_{\iota k}^{}=1_{i=1}^{k1}w_{\iota i}^{}`$ for $`1\iota \mathrm{}`$. We perturb each $`𝐰_\iota ^{}`$ in the same way. Let $`\stackrel{~}{𝐰}_\iota ^0=𝐰_\iota ^{}`$. For $`1jk`$, given $`\stackrel{~}{𝐰}_\iota ^{j1}`$, define $`\stackrel{~}{𝐰}_\iota ^j`$ as follows. Let $`j_{\mathrm{max}}`$ be the index of the maximum coordinate of $`\stackrel{~}{𝐰}_\iota ^{j1}`$. If $`0\stackrel{~}{w}_{\iota j}^j<\rho `$, define $`\stackrel{~}{w}_{\iota j}^j=\stackrel{~}{w}_{\iota j}^{j1}+\rho `$, $`\stackrel{~}{w}_{\iota j_{\mathrm{max}}}^j=\stackrel{~}{w}_{\iota j_{\mathrm{max}}}^{j1}\rho `$ and leave all other coordinates unchanged. Otherwise, let $`\stackrel{~}{𝐰}_{j_0}^j=\stackrel{~}{𝐰}_{j_0}^{j1}`$. The final perturbation is $`\stackrel{~}{𝐰}=(\stackrel{~}{𝐰}_1,\mathrm{},\stackrel{~}{𝐰}_{\mathrm{}})`$, where $`\stackrel{~}{𝐰}_\iota =\stackrel{~}{𝐰}_\iota ^k`$. By construction, $`\stackrel{~}{𝐰}𝕎`$, $`\stackrel{~}{𝐰}`$ is at least $`\rho `$ away from the edges of $`𝕎`$ and $`|w_{\iota j}^{}\stackrel{~}{w}_{\iota j}|k\rho `$ for all $`\iota `$ and $`j`$. We bound $`\frac{_n(𝐰^{})}{_n(\stackrel{~}{𝐰})}`$ by the multivariate mean value theorem and the Cauchy-Schwartz inequality:

$`_n(\stackrel{~}{𝐰})`$ $`=`$ $`_n(𝐰^{})+_n(\stackrel{~}{𝐰})_n(𝐰^{})`$
$``$ $`_n(𝐰^{})|_n(𝐰^{})(\stackrel{~}{𝐰}𝐰^{})|\text{(for some }𝐰^{}\text{ between }\stackrel{~}{𝐰}\text{ and }𝐰^{}\text{)}`$
$``$ $`_n(𝐰^{})|_n(𝐰^{})||\stackrel{~}{𝐰}𝐰^{}|_n(𝐰^{})c^{}_n(𝐰^{})mn^4\sqrt{k\mathrm{}}k\rho \sqrt{k\mathrm{}}`$
$``$ $`_n(𝐰^{})c^{}_n(𝐰^{})mn^4\sqrt{k\mathrm{}}k\rho \sqrt{k\mathrm{}}_n(𝐰^{})(1\gamma ).`$
For $`0\iota \mathrm{}`$ let $`C_\iota =\{𝐰_\iota ^k||\stackrel{~}{𝐰}_\iota 𝐰_\iota |\rho \}`$. From the construction of $`\stackrel{~}{𝐰}`$, $`B_\iota =C_\iota 𝒲_k`$ is a $`(k1)`$-dimensional ball of radius $`\rho `$. Let $`\stackrel{~}{𝐰}_\iota ^{}=\mathrm{arg}\mathrm{max}_{𝐰B_\iota }_n(𝐰)`$ and let $`\stackrel{~}{𝐰}^{}=(\stackrel{~}{𝐰}_1^{},\mathrm{},\stackrel{~}{𝐰}_{\mathrm{}}^{})`$ be the profit maximizing parameters in $`B=B_1\times \mathrm{}\times B_{\mathrm{}}`$. For $`𝐰B`$,

$`_n(𝐰)`$ $`=`$ $`_n(\stackrel{~}{𝐰}^{})+_n(𝐰)_n(\stackrel{~}{𝐰}^{})`$
$``$ $`_n(\stackrel{~}{𝐰}^{})|_n(𝐰^{})||\stackrel{~}{𝐰}^{}𝐰|\text{(for some }𝐰^{}\text{ between }\stackrel{~}{𝐰}^{}\text{ and }𝐰\text{)}`$
$``$ $`_n(\stackrel{~}{𝐰}^{})c^{}_n(\stackrel{~}{𝐰}^{})mn^4\sqrt{k\mathrm{}}2\rho \sqrt{\mathrm{}}_n(\stackrel{~}{𝐰}^{})(1\gamma )`$
$``$ $`_n(𝐰^{})(12\gamma ).`$
By Lemma 3

$`_n(𝒰(S))`$ $`=`$ $`{\displaystyle _𝕎}_n(S(𝐰))𝑑\mu (𝐰){\displaystyle _B}_n(𝐰)𝑑\mu (𝐰)(12\gamma )_n(𝐰^{}){\displaystyle _B}𝑑\mu (𝐰)`$
$``$ $`(12\gamma )_n(𝐰^{}){\displaystyle \frac{_B𝑑𝐰}{_𝕎𝑑𝐰}}`$
$`=`$ $`(12\gamma )_n(𝐰^{})\left({\displaystyle \frac{\pi ^{\frac{k1}{2}}\rho ^{k1}}{\mathrm{\Gamma }(\frac{k1}{2}+1)}}{\displaystyle \frac{(k1)!}{\sqrt{k}}}\right)^{\mathrm{}}\text{(from Lemmas }\text{7}\text{ and }\text{8}\text{)}`$
$`=`$ $`_n(𝐰^{})\mathrm{\Lambda }(\gamma ,m,k,\mathrm{})n^{4k\mathrm{}}`$
where $`\mathrm{\Lambda }`$ is some constant depending on $`\gamma `$, $`m`$, $`k`$, and $`\mathrm{}`$. Therefore,

$$_n(𝐰^{})_n(𝒰(S))\frac{\mathrm{log}\mathrm{\Lambda }(\gamma ,m,k,\mathrm{})}{n}+4k\mathrm{}\frac{\mathrm{log}n}{n}=\frac{\mathrm{o}(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 $`𝕎`$ that are not necessarily of the form $`𝒲_k^{\mathrm{}}`$.

### 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 $`𝕎`$ grow with time. In fact, even if the dimension of the parameter space (the coefficient of $`\frac{\mathrm{log}n}{n}`$ in (10)) is $`𝒪(\frac{n}{\varphi (n)\mathrm{log}n})`$, where $`\varphi (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 $`=[0,n)`$ into $`\psi =𝒪(\frac{n}{\varphi (n)\mathrm{log}n})`$ subintervals $`_1,\mathrm{},_\psi `$ and let $`𝐰__j^{}`$ be the parameters that optimize the return during $`_j`$. In $`_1`$, we run the universalization algorithm given by (8) over the basic parameter space $`𝕎`$ of $`S`$. In $`_2`$, we run the algorithm over $`𝕎\times 𝕎`$; to compute the investment description for a day $`t_2`$ using (8), we compute the return $`_t(𝐰_1,𝐰_2)`$ as the product of the returns we would have earned in $`_1`$ using $`𝐰_1`$ and what we would have earned up to day $`t`$ in $`_2`$ using $`𝐰_2`$. We proceed similarly in intervals $`_3`$ through $`_\psi `$. This will allow us to track the strategy that uses the optimal parameters $`𝐰__j^{}`$ corresponding to each $`_j`$. 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 $`\left|\frac{T_{ti}(𝐰)}{w_j}\right|`$ for our trading strategies $`T`$, we show that they are universalizable.

###### Theorem 9

The moving average cross-over trading strategy, $`\text{MA}[k]`$, is universalizable for the long/short allocation functions $`g_{(t)}(x)`$ and $`g_{\mathrm{}}(x)`$ defined in (3) and (4) respectively.

###### Proof.

The parameters for $`\text{MA}[k]`$ are of the form $`𝐰_F=(w_{F1},\mathrm{},w_{F(k1)},1w_{F1}\mathrm{}w_{F(k1)})`$ and $`𝐰_S=(w_{S1},\mathrm{},w_{S(k1)},1w_{S1}\mathrm{}w_{S(k1)})`$. Using the long/short allocation function $`g_{(t)}(x)`$ defined in (3), the partial derivative of the investment description with respect to a parameter $`w_{Fj}`$ (or similarly $`w_{Sj}`$) is

$$\left|\frac{\text{MA}_{ti}(𝐰_F,𝐰_S)}{w_{Fj}}\right|=\left|\frac{g((𝐰_F𝐰_S)𝐯_t)}{w_{Fj}}\right|\frac{t}{2}(v_{tj}v_{tk})\frac{t}{2}$$

where $`1j<k`$ and $`i\{1,2\}`$. Similarly, we can show that using the long/short allocation function $`g_{\mathrm{}}(x)`$ defined in (4), $`\left|\frac{\text{MA}_{ti}(𝐰_F,𝐰_S)}{w_{Fj}}\right|\frac{1}{2}`$. ∎

###### Theorem 10

The support and resistance breakout trading strategy, $`\text{SR}[k]`$, is universalizable for the long/short allocation functions $`h_{(t)}(x,y)`$ and $`h_p(x,y)`$ defined in (5) and (7) respectively.

###### Proof.

We arrive at the result by differentiating the long/short allocation functions $`h_{(t)}(x,y)`$ and $`h_p(x,y)`$ with respect to an arbitrary parameter $`w_j`$ and showing that the partial derivative is $`𝒪(t)`$, as in the proof of Theorem 9. ∎

### 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 $`\text{CRP}_{ti}`$ and $`\text{CRP-S}_{ti}`$ with respect to an arbitrary parameter $`w_j`$ are at most $`1`$. ∎

###### Theorem 12

The $`k`$-way indicator aggregation portfolio strategy, $`\text{IA}[k]`$, is universalizable.

###### Proof.

First, we show that $`_{\mathrm{}=1}^m𝐰𝐯_t\mathrm{}\frac{1}{k}`$ for all $`t`$. Since $`_{j=1}^kw_j=1`$, there exists $`j_0`$ such that $`w_{j_0}\frac{1}{k}`$. Then $`_{\mathrm{}=1}^m𝐰𝐯_t\mathrm{}_{\mathrm{}=1}^mw_{j_0}v_{t\mathrm{}j_0}\frac{1}{k}_{\mathrm{}=1}^mv_{t\mathrm{}j_0}\frac{1}{k}`$ since the $`\{v_{t\mathrm{}j_0}\}_{1\mathrm{}m}`$ have been normalized such that there is at least one $`\mathrm{}_0`$ such that $`v_{t\mathrm{}_0j_0}=1`$.

Now, let $`S=\text{IA}[k]`$. By Theorem 5, we need only show that $`\frac{S_{ti}(𝐰)}{w_j}=𝒪(t)`$, for $`1jk1`$. For $`t0`$ and $`1im`$ recall that $`S_{ti}(𝐰)=\frac{𝐰𝐯_{ti}}{_{\mathrm{}=1}^m𝐰𝐯_t\mathrm{}}`$. Then, for $`1jk1`$, since $`𝐰=(w_1,\mathrm{},w_{k1},1(w_1+\mathrm{}+w_{k1}))`$,

$`{\displaystyle \frac{S_{ti}(𝐰)}{w_j}}`$ $`=`$ $`{\displaystyle \frac{v_{tij}v_{tik}}{_{\mathrm{}=1}^m𝐰𝐯_t\mathrm{}}}{\displaystyle \frac{𝐰𝐯_{ti}}{(_{\mathrm{}=1}^m𝐰𝐯_t\mathrm{})^2}}{\displaystyle \underset{\mathrm{}=1}{\overset{m}{}}}(v_{t\mathrm{}j}v_{t\mathrm{}k})`$
$``$ $`{\displaystyle \frac{1}{_{\mathrm{}=1}^m𝐰𝐯_t\mathrm{}}}+{\displaystyle \frac{m}{(_{\mathrm{}=1}^m𝐰𝐯_t\mathrm{})^2}}k+mk^2,`$
as we wanted to show. ∎

## 4 Fast Computation of Universal Investment Strategies

### 4.1 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 , we propose to approximate it by sampling the parameters according to a biased distribution, giving greater weight to better performing parameters. Define the measure $`\zeta _t`$ on $`𝕎`$ by

$$d\zeta _t(𝐰)=\frac{_t(S(𝐰))}{_𝕎_t(S(𝐰))𝑑\mu (𝐰)}d\mu (𝐰).$$

###### Lemma 13 ()

The investment description $`𝒰_t(S)`$ for universalization is the average of $`S_t(𝐰)`$ with respect to the $`\zeta _t`$ measure.

###### Proof.

The average of $`S_t(𝐰)`$ with respect to $`\zeta _t`$ is

$`𝔼_{𝐰(𝕎,\zeta _t)}(S_t(𝐰))`$ $`=`$ $`{\displaystyle _𝕎}S_t(𝐰)𝑑\zeta _t(𝐰)`$
$`=`$ $`{\displaystyle _𝕎}S_t(𝐰){\displaystyle \frac{_t(S(𝐰))}{_𝕎_t(S(𝐰))𝑑\mu (𝐰)}}𝑑\mu (𝐰)=𝒰_t(S),`$
where the final equality follows from (8). ∎

In Section 4.2, we show that for certain strategies we can efficiently sample from a distribution $`\overline{\zeta }_t`$ that is “close” to $`\zeta _t`$, i.e. given $`\gamma _t>0`$, we generate samples from $`\overline{\zeta }_t`$ in $`𝒪(\mathrm{log}\frac{1}{\gamma _t})`$ time and such that

$$_𝕎\left|\zeta _t(𝐰)\overline{\zeta }_t(𝐰)\right|𝑑\mu (𝐰)\gamma _t.$$
(11)
Assume for now that we can sample from $`\overline{\zeta }_t`$, with $`\gamma _t=\frac{\epsilon ^2}{4m(t+1)^4}`$, where $`\epsilon `$ is the constant appearing in Remark 6. Let $`\overline{𝒰}_t(S)=_𝕎S_t(𝐰)𝑑\overline{\zeta }_t(𝐰)`$ be the corresponding approximation to $`𝒰(S)`$. Lemma 14 tells us that we do not lose much by sampling from $`\overline{\zeta }_t`$.

###### Lemma 14

For all $`n0`$, (1) $`_n(\overline{𝒰}(S))(1\epsilon )_n(𝒰(S))`$ and (2) if $`𝒰(S)`$ is a universalization of $`S`$, then $`\overline{𝒰}(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 $`\overline{𝒰}(S)`$ is within a $`1\frac{\epsilon }{2(t+1)^2}`$ factor of the corresponding amount under $`𝒰(S)`$, i.e. $`\overline{𝒰}_{ti}(S)(1\frac{\epsilon }{2(t+1)^2})𝒰_{ti}(S)`$ for $`0t<n`$ and $`1im`$. For $`𝐰𝕎`$, let $`\gamma _t(𝐰)=|\overline{\zeta }_t(𝐰)\zeta _t(𝐰)|`$, so that $`_𝕎\gamma _t(𝐰)𝑑𝐰=\gamma _t\frac{\epsilon ^2}{4m(t+1)^4}`$. We have

$`\overline{𝒰}_{ti}(S)`$ $`=`$ $`{\displaystyle _𝕎}S_{ti}(𝐰)\overline{\zeta }_t(𝐰)𝑑\mu (𝐰){\displaystyle _𝕎}S_{ti}(𝐰)(\zeta _t(𝐰)\gamma _t(𝐰))𝑑\mu (𝐰)`$
$`=`$ $`𝒰_{ti}(S){\displaystyle _𝕎}S_{ti}(𝐰)\gamma _t(𝐰)𝑑\mu (𝐰)𝒰_{ti}(S)\gamma _t\text{(since }S_{ti}(𝐰)1\text{)}`$
$``$ $`(1\frac{\epsilon }{2(t+1)^2})𝒰_{ti}(S)\text{(since }𝒰_{ti}(S)\mathrm{min}_𝐰S(𝐰)\frac{\epsilon }{2m(t+1)^2}\text{ and }\gamma _t\frac{\epsilon ^2}{4m(t+1)^4}\text{),}`$
as we wanted to show. ∎

By sampling from $`\overline{\zeta }_t`$, we use a generalization of the Chernoff bound to get an approximation $`\stackrel{~}{𝒰}(S)`$ to $`\overline{𝒰}(S)`$ such that with high probability $`\stackrel{~}{𝒰}_{ti}(S)(1\frac{\epsilon }{2(t+1)^2})\overline{𝒰}_{ti}(S)`$ for $`0t<n`$ and $`1im`$. Using an argument similar to that in the proof of Lemma 14, we see that if $`\overline{𝒰}(S)`$ is a universalization of $`S`$, then such a $`\stackrel{~}{𝒰}(S)`$ is a universalization of $`S`$ as well. Choose $`𝐰_1,\mathrm{},𝐰_{N_t}𝕎`$ at random according to distribution $`\overline{\zeta }_t`$ and let $`\stackrel{~}{𝒰}_{ti}(S)=\frac{1}{N_t}_{i=1}^{N_t}S_{ti}(𝐰_i)`$. Lemma 15 discusses the number of samples $`N_t`$ required to get a sufficiently good approximation to $`\overline{𝒰}_t(S)`$.

###### Lemma 15

Given $`0<\delta <1`$ use $`N_t\frac{8m^2(t+1)^8}{\epsilon ^4}\mathrm{log}\frac{2m(t+1)^2}{\delta }`$ samples to compute $`\stackrel{~}{𝒰}_t(S)`$, where $`\epsilon `$ is the constant appearing in Remark 6. With probability $`1\delta `$, $`\stackrel{~}{𝒰}_{ti}(S)(1\frac{\epsilon }{2(t+1)^2})\overline{𝒰}_{ti}(S)`$ for all $`1im`$ and $`t0`$.

###### Proof.

Hoeffding  proves a general version of the Chernoff bound. For random variables $`0X_i1`$ with $`𝔼(X_i)=\mu `$ and $`\stackrel{~}{X}=\frac{1}{N}_{i=1}^NX_i`$ the bound states that $`\mathrm{Pr}(\stackrel{~}{X}(1\alpha )\mu )e^{2N\alpha ^2\mu ^2}`$. In our case, we would like $`\stackrel{~}{𝒰}_{ti}(1\frac{\epsilon }{2(t+1)^2})\overline{𝒰}_{ti}`$. As this must hold for $`1im`$ and $`t0`$ with total probability $`1\delta `$, we require $`\mathrm{Pr}(\stackrel{~}{𝒰}_{ti}(1\frac{\epsilon }{2(t+1)^2})\overline{𝒰}_{ti})\frac{\delta }{2m(t+1)^2}`$ for each $`i`$ and $`t`$. From our assumption stated in Remark 6, $`\mu =\overline{𝒰}_{ti}\frac{\epsilon }{2m(t+1)^2}`$ and the desired probability bound is achieved with $`N_t\frac{8m^2(t+1)^8}{\epsilon ^4}\mathrm{log}\frac{2m(t+1)^2}{\delta }`$ samples. ∎

### 4.2 Efficient Sampling

We now discuss how to sample from $`𝕎=𝒲_k^{\mathrm{}}=𝒲_k\times \mathrm{}\times 𝒲_k`$ according to distribution $`\zeta _t()_t()=_t(S())`$. $`𝕎`$ is a convex set of diameter $`d=\sqrt{2\mathrm{}}`$. We focus on a discretization of the sampling problem. Choose an orthogonal coordinate system on each $`𝒲_k`$ and partition it into hypercubes of side length $`\delta _t`$, where $`\delta _t`$ is a constant chosen below. Let $`\mathrm{\Omega }`$ be the set of centers of cubes that intersect $`𝕎`$ and choose the partition such that the coordinates of $`𝐰\mathrm{\Omega }`$ are multiples of $`\delta _t`$. For $`𝐰\mathrm{\Omega }`$, let $`C(𝐰)`$ be the cube with center $`𝐰`$. We show how to choose $`𝐰\mathrm{\Omega }`$ with probability “close to”

$$\pi _t(𝐰)=\frac{_t(𝐰)}{_{𝐰\mathrm{\Omega }}_t(𝐰)}.$$

In particular, we sample from a distribution $`\stackrel{~}{\pi }_t`$ that satisfies

$$\underset{𝐰\mathrm{\Omega }}{}\left|\pi _t(𝐰)\stackrel{~}{\pi }_t(𝐰)\right|\gamma _t=\frac{\epsilon ^2}{4m(t+1)^4}.$$
(12)
Note that this is a discretization of (11). We will also have that for each $`𝐰\mathrm{\Omega }`$,

$$\frac{\stackrel{~}{\pi }_t(𝐰)}{\pi _t(𝐰)}2.$$
(13)
We would like to choose $`\delta _t`$ sufficiently small that $`_t`$ is “nearly constant” over $`C(𝐰)`$ i.e. there is a small constant $`\nu >0`$ such that

$$(1+\nu )^1_t(𝐰)_t(𝐰^{})(1+\nu )_t(𝐰)$$
(14)
for all $`𝐰^{}C(𝐰)`$. Such a $`\delta _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 in Theorem 5, i.e. $`\left|\frac{S_{ti}(𝐰)}{w_j}\right|ct`$. Given $`\nu >0`$, let $`\delta _t=\delta _t(\nu )=\frac{\nu }{3c^{}mt^4k\mathrm{}}`$, where $`c^{}`$ is defined in the proof of Theorem 5. For $`𝐰,𝐰^{}𝕎`$ such that $`|w_{ij}w_{ij}^{}|\delta _t(\nu )`$ for all $`1i\mathrm{}`$ and $`1jk`$, $`(1+\nu )^1_t(𝐰)_t(𝐰^{})(1+\nu )_t(𝐰)`$.

###### Proof.

Note that $`|𝐰𝐰^{}|\delta _t\sqrt{k\mathrm{}}`$. Let $`𝐰^{}`$ be the parameters that maximize the return on the line between $`𝐰`$ and $`𝐰^{}`$. By the multivariate mean value theorem and the bound for $`|_t|`$ given in (9),

$`_t(𝐰^{})`$ $`=`$ $`_t(𝐰)+_t(𝐰^{})_t(𝐰)`$
$``$ $`_t(𝐰)+|_t(𝐰_m)||𝐰𝐰^{}|\text{(for some }𝐰_m\text{ between }𝐰^{}\text{ and }𝐰\text{)}`$
$``$ $`_t(𝐰)+c^{}_t(𝐰_m)mn^4\sqrt{k\mathrm{}}\delta _t\sqrt{k\mathrm{}}_t(𝐰)+_t(𝐰^{}){\displaystyle \frac{\nu }{3}}`$
$`_t(𝐰)`$ $``$ $`_t(𝐰^{})(1{\displaystyle \frac{\nu }{3}})_t(𝐰^{})(1{\displaystyle \frac{\nu }{3}})`$
so that $`_t(𝐰^{})(1+\nu )_t(𝐰)`$. By similar reasoning,

$`_t(𝐰^{})`$ $`=`$ $`_t(𝐰^{})+_t(𝐰^{})_t(𝐰^{})`$
$``$ $`_t(𝐰^{})|_t(𝐰_m)||𝐰^{}𝐰^{}|\text{(for some }𝐰_m\text{ between }𝐰^{}\text{ and }𝐰^{}\text{)}`$
$``$ $`_t(𝐰^{})(1{\displaystyle \frac{\nu }{3}})_t(𝐰)(1{\displaystyle \frac{\nu }{3}})_t(𝐰)(1+\nu )^1,`$
completing the proof. ∎

We use a Metropolis algorithm  to sample from $`\stackrel{~}{\pi }_t`$. We generate a random walk on $`\mathrm{\Omega }`$ according to a Markov chain whose stationary distribution is $`\pi _t`$. Begin by selecting a point $`𝐰_0\mathrm{\Omega }`$ according to either $`\stackrel{~}{\pi }_{t1}`$ or $`\stackrel{~}{\pi }_{t2}`$;777Ideally, we would like to begin with a point selected according to $`\stackrel{~}{\pi }_{t1}`$, but, as discussed in Remark 8, this is not always possible. Remark 8 explains how to do this.

###### Remark 8

We can select a point according to $`\stackrel{~}{\pi }_{t1}`$ by “saving” our samples that were generated at time $`t1`$. By Lemma 15, we would have generated $`N_{t1}\frac{8m^2t^8}{\epsilon ^4}\mathrm{log}\frac{2mt^2}{\delta }`$ samples at time $`t1`$, which is not enough to generate the $`N_t\frac{8m^2(t+1)^8}{\epsilon ^4}\mathrm{log}\frac{2m(t+1)^2}{\delta }`$ samples necessary at time $`t`$. Instead, we can “save” samples that were generated at times $`t1`$ and $`t2`$. For sufficiently large $`t`$, $`N_tN_{t1}+N_{t2}`$ and our initial point $`𝐰_0`$ would be picked according to either $`\stackrel{~}{\pi }_{t1}`$ or $`\stackrel{~}{\pi }_{t2}`$. As we see in the proof of Lemma 22, this distinction is not important.

If $`𝐰_\tau `$ is the position of our random walk at time $`\tau 0`$, we pick its position at time $`\tau +1`$ as follows. Note that $`𝐰_\tau `$ has $`2(k1)\mathrm{}`$ neighbors, two along each axis in the Cartesian product of $`\mathrm{}`$ $`(k1)`$-dimensional spaces. Let $`𝐰`$ be a neighbor of $`𝐰_\tau `$, selected uniformly at random. If $`𝐰\mathrm{\Omega }`$, set

$$𝐰_{\tau +1}=\{\begin{array}{cc}𝐰\hfill & \text{with probability }p=\mathrm{min}(1,\frac{_t(𝐰)}{_t(𝐰_\tau )})\hfill \\ 𝐰_\tau \hfill & \text{with probability }1p\text{.}\hfill \end{array}$$

If $`𝐰\mathrm{\Omega }`$, let $`𝐰_{\tau +1}=𝐰_\tau `$. It is well-known that the stationary distribution of this random walk is $`\pi _t`$. We must determine how many steps of the walk are necessary before the distribution has gotten sufficiently close to stationary. Let $`p_\tau `$ be the distribution attained after $`\tau `$ steps of the random walk. That is, $`p_\tau (𝐰)`$ is the probability of being at $`𝐰`$ after $`\tau `$ steps.

###### Remark 9

A distinction should be made between $`t`$ and $`\tau `$. We use $`t`$ to refer to the time step in our universalization algorithm. We use $`\tau `$ to refer to “sub” time steps used in the Markov chain to sample from $`\pi _t`$. When $`t`$ is clear from context, we may drop it from the subscripts in our notation.

Applegate and Kannan  show that if the desired distribution $`\pi _t`$ is proportional to a log-concave function $`F`$ (i.e. $`\mathrm{log}F`$ is concave) the Markov chain is *rapidly mixing*, reaches its steady state in polynomial time. Frieze and Kannan  give an improved upper bound on the mixing time using Logarithmic Sobolev inequalities .

###### Theorem 17 (Theorem 1 of )

Assume the diameter $`d`$ of $`𝕎`$ satisfies $`d\delta _t\sqrt{k\mathrm{}}`$ and that the target distribution $`\pi `$ is proportional to a log-concave function. There is an absolute constant $`\kappa >0`$ such that

$$2\left(\underset{𝐰\mathrm{\Omega }}{}|\pi (𝐰)p_\tau (𝐰)|\right)^2e^{\frac{\kappa \tau \delta _t^2}{k\mathrm{}d^2}}\mathrm{log}\frac{1}{\pi _{}}+\frac{M\pi _ek\mathrm{}d^2}{\kappa \delta _t^2},$$
(15)
where $`\pi _{}=\mathrm{min}_{𝐰\mathrm{\Omega }}\pi (𝐰)`$, $`M=\mathrm{max}_{𝐰\mathrm{\Omega }}\frac{p_0(𝐰)}{\pi (𝐰)}\mathrm{log}\frac{p_0(𝐰)}{\pi (𝐰)}`$, $`p_0()`$ is the initial distribution on $`\mathrm{\Omega }`$, $`\pi _e=_{𝐰\mathrm{\Omega }_e}\pi (𝐰)`$, and $`\mathrm{\Omega }_e=\{𝐰\mathrm{\Omega }|\mathrm{Vol}(C(𝐰)𝕎)<\mathrm{Vol}(C(𝐰))\}`$ (the “$`e`$” in the subscripts of $`\pi _e`$ and $`\mathrm{\Omega }_e`$ stands for “edge”).

In the random walk described above, if $`𝐰_\tau `$ is on an edge of $`\mathrm{\Omega }`$, so it has many neighbors outside $`\mathrm{\Omega }`$, the walk may get “stuck” at $`𝐰_\tau `$ for a long time, as seen in the “$`\pi _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 $`_t`$ that becomes exponentially small near the edges of $`𝕎`$. For $`1i\mathrm{}`$, $`1jk`$, and $`𝐰=(𝐰_1,\mathrm{},𝐰_{\mathrm{}})=((w_{11},\mathrm{},w_{1k}),\mathrm{},(w_\mathrm{}1,\mathrm{},w_\mathrm{}k))𝕎`$ let

$$f_{ij}(𝐰)=e^{\mathrm{\Gamma }\mathrm{min}(\sigma +w_{ij},0)},$$
(16)
where $`\sigma >0`$ and $`\mathrm{\Gamma }>2`$ are constants that we choose below, and let

$$F_t(𝐰)=_t(𝐰)\underset{i=1}{\overset{\mathrm{}}{}}\underset{j=1}{\overset{k}{}}f_{ij}(𝐰).$$

###### Lemma 18

$`F_t`$ is log-concave if and only if $`_t`$ is log-concave.888We characterize investment strategies for which $`_t`$ is log-concave in Theorem 26

###### Proof.

This follows from the fact that log-concave functions are closed under multiplication and the fact that $`\mathrm{log}f_{ij}(𝐰)=\mathrm{\Gamma }\mathrm{min}(\sigma +w_{ij},0)`$, which is concave. ∎

Choose $`\sigma =\frac{1}{k}\delta _t(\frac{\gamma _t}{2})`$, where $`\delta _t()`$ is defined in Lemma 16 and $`\gamma _t`$ is defined in (12). Let $`\zeta _FF_t`$ be the probability measure proportional to $`F_t`$. We need to show that for our purposes, sampling from $`\zeta _F`$ is not much different than sampling from $`\zeta _t`$. By Lemma 14, we can do this by showing that $`_𝕎|\zeta _t(𝐰)\zeta _F(𝐰)|𝑑𝐰\gamma _t`$, which we do in Lemma 19.

###### Remark 10

Before continuing, we show how $`𝕎`$ can be scaled, which will be useful in future proofs. Take $`𝐩=(\frac{1}{k},\mathrm{},\frac{1}{k})𝒲_k`$; given $`\chi (1,1)`$, let

$$𝐰^{(\chi )}=(1+\chi )(𝐰𝐩)+𝐩$$

and let

$$𝒲_k^{(\chi )}=\{𝐰^{(\chi )}|𝐰𝒲_k\}$$

be a scaled version of $`𝒲_k`$ about $`𝐩`$, where the scaling factor is $`1+\chi `$. To extend this scaling to $`𝕎=𝒲_k^{\mathrm{}}`$, given $`𝐰=(𝐰_1,\mathrm{},𝐰_{\mathrm{}})𝕎`$, let $`𝐰^{(\chi )}=(𝐰_1^{(\chi )},\mathrm{},𝐰_{\mathrm{}}^{(\chi )})`$ and let

$$𝕎^{(\chi )}=\{𝐰^{(\chi )}|𝐰𝕎\}.$$

A fact we use is that for $`1i\mathrm{}`$, $`1jk`$, and $`𝐰=(𝐰_1,\mathrm{},𝐰_{\mathrm{}})𝕎`$

$$|w_{ij}^{(\chi )}w_{ij}|=|(1+\chi )(w_{ij}\frac{1}{k})+\frac{1}{k}w_{ij}||\chi |.$$

###### Lemma 19

$`_𝕎|\zeta _t(𝐰)\zeta _F(𝐰)|𝑑𝐰\gamma _t`$.

###### Proof.

Let $`𝕎^{}=𝕎^{(k\sigma )}`$ be the “scaled-in” version of $`𝕎`$, as defined in Remark 10. By Lemma 16, since $`|w_{ij}w_{ij}^{}|k\sigma =\delta _t(\frac{\gamma _t}{2})`$ for all $`i`$ and $`j`$, $`_t(𝐰^{})\frac{1}{1+\frac{\gamma _t}{2}}_t(𝐰)`$ and

$$_𝕎^{}_t(𝐰)𝑑𝐰\frac{1}{1+\frac{\gamma _t}{2}}_𝕎_t(𝐰)𝑑𝐰.$$
(17)
Let $`𝕎_{eq}=\{𝐰𝕎|F_t(𝐰)=_t(𝐰)\}`$ be the subset of $`𝕎`$ where $`F_t()`$ and $`_t()`$ are equal; $`𝕎^{}𝕎_{eq}`$ since, by construction of $`𝐰^{}`$, $`w_{ij}^{}\sigma `$ for all $`i`$ and $`j`$. Let $`𝕎_+=\{𝐰𝕎|\zeta _F(𝐰)\zeta _t(𝐰)\}`$ be the subset of $`𝕎`$ where $`\zeta _F()`$ is at least $`\zeta _t()`$ and let $`𝕎_{}=𝕎𝕎_+`$. We bound

$$_𝕎|\zeta _F(𝐰)\zeta _t(𝐰)|𝑑𝐰=_{𝕎_+}(\zeta _F(𝐰)\zeta _t(𝐰))𝑑𝐰+_𝕎_{}(\zeta _t(𝐰)\zeta _F(𝐰))𝑑𝐰$$

by bounding $`_𝕎_{}(\zeta _t\zeta _F)`$, which also gives a bound for $`_{𝕎_+}(\zeta _F\zeta _t)`$, since

$$_{𝕎_+}(\zeta _F\zeta _t)=\left(1_𝕎_{}\zeta _F\right)\left(1_𝕎_{}\zeta _t\right)=_𝕎_{}(\zeta _t\zeta _F).$$

Since $`F_t_t`$, $`_𝕎F_t_𝕎_t`$ and $`\zeta _F(𝐰)=\frac{F_t(𝐰)}{_𝕎F_t}\frac{_t(𝐰)}{_𝕎_t}=\zeta _t(𝐰)`$ for $`𝐰𝕎_{eq}`$; thus $`𝕎^{}𝕎_{eq}𝕎_+`$ and $`𝕎_{}𝕎𝕎^{}`$. We have

$`{\displaystyle _𝕎_{}}(\zeta _t(𝐰)\zeta _F(𝐰))𝑑𝐰`$ $``$ $`{\displaystyle _{𝕎𝕎^{}}}\zeta _t(𝐰)𝑑𝐰={\displaystyle \frac{_{𝕎𝕎^{}}_t(𝐰)𝑑𝐰}{_𝕎_t(𝐰)𝑑𝐰}}=1{\displaystyle \frac{_𝕎^{}_t(𝐰)𝑑𝐰}{_𝕎_t(𝐰)𝑑𝐰}}`$
$``$ $`1{\displaystyle \frac{1}{1+\frac{\gamma _t}{2}}}{\displaystyle \frac{\gamma _t}{2}},`$
where the second-last inequality follows from (17). This completes the proof. ∎

Henceforth, we are concerned with sampling from $`𝕎`$ with probability proportional to $`F_t()`$. We use the Metropolis algorithm described above, replacing $`R_t()`$ with $`F_t()`$; we must refine our grid spacing $`\delta _t`$ so that (14) is satisfied by $`F_t`$; let $`\delta _t^{}`$ be the new grid spacing.

###### Lemma 20

Suppose that the conditions of Lemma 16 are satisfied. Given $`\nu >0`$, let $`\delta _t^{}(\nu )=\delta _t^{}=\frac{\nu }{3\mathrm{\Gamma }c^{}mt^4k\mathrm{}}=\delta _t(\frac{\nu }{\mathrm{\Gamma }})`$, where $`\mathrm{\Gamma }`$ appears in (16). For $`𝐰,𝐰^{}𝕎`$ such that $`|w_{ij}w_{ij}^{}|\delta _t^{}(\nu )`$ for all $`1i\mathrm{}`$ and $`1jk`$, $`(1+\nu )^1F_t(𝐰)F_t(𝐰^{})(1+\nu )F_t(𝐰)`$.

###### Proof.

By Lemma 16, $`_t(𝐰)`$ and $`_t(𝐰^{})`$ differ by at most a factor $`1+\frac{\nu }{\mathrm{\Gamma }}`$. For each $`i`$ and $`j`$, $`f_{ij}(𝐰)`$ and $`f_{ij}(𝐰^{})`$ differ by at most a factor $`e^{\mathrm{\Gamma }\delta _t^{}(\nu )}`$ and hence $`_{i=1}^{\mathrm{}}_{j=1}^kf_{ij}(𝐰)`$ and $`_{i=1}^{\mathrm{}}_{j=1}^kf_{ij}(𝐰^{})`$ differ by at most a factor $`e^{k\mathrm{}\mathrm{\Gamma }\delta _t^{}(\nu )}=e^{\frac{\nu }{3c^{}mt^4}}`$. Hence, for $`\mathrm{\Gamma }2`$ and sufficiently large $`t`$, $`F_t(𝐰)`$ and $`F_t(𝐰^{})`$ differ by at most a factor $`1+\nu `$. ∎

We are now ready to use Theorem 17 to select $`\tau `$ so that the resulting distribution $`p_\tau `$ satisfies (12) (Theorem 24) and (13) (Theorem 25), with $`p_\tau `$ in place of $`\stackrel{~}{\pi }_t`$ and $`F_t`$ in place of $`_t`$. We begin with some preliminary lemmas.

###### Lemma 21

There is a constant $`\beta >0`$ such that $`\mathrm{log}\frac{1}{\pi _{}}k\mathrm{}\mathrm{\Gamma }\sigma +k\mathrm{}\mathrm{log}\frac{\beta }{\delta _t^{}}+t\mathrm{log}\frac{2mt^2}{\epsilon }`$, where $`\epsilon `$ is defined in Remark 6.

###### Proof.

Take $`\beta `$ such that the number of points in $`\mathrm{\Omega }`$ is at most $`(\frac{\beta }{\delta _t^{}})^{(k1)\mathrm{}}`$. For $`𝐰_1,𝐰_2\mathrm{\Omega }`$, the ratio of single-day returns on day $`t^{}`$ using $`𝐰_1`$ and $`𝐰_2`$ is

$$\frac{S_t^{}(𝐰_1)𝐱_t^{}}{S_t^{}(𝐰_2)𝐱_t^{}}\frac{\epsilon }{2m(t^{}+1)^2}$$

by Remark 6 and Lemma 6. The ratio of the cumulative returns up to day $`t`$ is

$$\frac{_t(𝐰_1)}{_t(𝐰_2)}\left(\frac{\epsilon }{2mt^2}\right)^t,$$

and thus $`\frac{_t(𝐰)}{_{𝐰\mathrm{\Omega }}_t(𝐰)}(\frac{\delta _t^{}}{\beta })^{(k1)\mathrm{}}\left(\frac{\epsilon }{2mt^2}\right)^t`$. Factoring in the maximum dampening effect of the $`f_{ij}`$, $`\pi _{}e^{k\mathrm{}\mathrm{\Gamma }\sigma }(\frac{\delta _t^{}}{\beta })^{(k1)\mathrm{}}\left(\frac{\epsilon }{2mt^2}\right)^t`$ and $`\mathrm{log}\frac{1}{\pi _{}}k\mathrm{}\mathrm{\Gamma }\sigma +k\mathrm{}\mathrm{log}\frac{\beta }{\delta _t^{}}+t\mathrm{log}\frac{2mt^2}{\epsilon }`$. ∎

###### Lemma 22

$`M4\left(\frac{2m(t+1)^2}{\epsilon }\right)^2\mathrm{log}\frac{2m(t+1)^2}{\epsilon }`$.

###### Proof.

As stated in Remark 8, the initial distribution is either $`p_0=\stackrel{~}{\pi }_{t1}`$ or $`\stackrel{~}{\pi }_{t2}`$. It turns out that the worst case happens when $`p_0=\stackrel{~}{\pi }_{t2}`$. For all $`𝐰\mathrm{\Omega }`$, $`\frac{\stackrel{~}{\pi }_{t2}(𝐰)}{\pi _{t2}(𝐰)}2`$ by (13) and

$`{\displaystyle \frac{\pi _{t2}(𝐰)}{\pi _t(𝐰)}}`$ $`=`$ $`{\displaystyle \frac{F_{t2}(𝐰)}{_{𝐰\mathrm{\Omega }}F_{t2}(𝐰)}}{\displaystyle \frac{_{𝐰\mathrm{\Omega }}F_t(𝐰)}{F_t(𝐰)}}`$
$``$ $`{\displaystyle \frac{F_{t2}(𝐰)}{F_t(𝐰)}}{\displaystyle \frac{F_t(𝐰^{})}{F_{t2}(𝐰^{})}}\text{(by Lemma }\text{6}\text{, where }𝐰^{}=\mathrm{arg}\mathrm{max}_{𝐰\mathrm{\Omega }}\frac{F_t(𝐰)}{F_{t2}(𝐰)}\text{)}`$
$`=`$ $`{\displaystyle \frac{_{t2}(𝐰)}{_t(𝐰)}}{\displaystyle \frac{_t(𝐰^{})}{_{t2}(𝐰^{})}}\text{(since the }\{f_{ij}()\}_{i,j}\text{ remain constant with time)}`$
$`=`$ $`{\displaystyle \frac{(S_t(𝐰^{})𝐱_t)(S_{t1}(𝐰^{})𝐱_{t1})}{(S_t(𝐰)𝐱_t)(S_{t1}(𝐰)𝐱_{t1})}}\left({\displaystyle \frac{2m(t+1)^2}{\epsilon }}\right)^2,`$
where the final inequality follows from the discussion in the proof of Lemma 21. This proves the result since $`\frac{\stackrel{~}{\pi }_{t2}(𝐰)}{\pi _t(𝐰)}=\frac{\stackrel{~}{\pi }_{t2}(𝐰)}{\pi _{t2(𝐰)}}\frac{\pi _{t2(𝐰)}}{\pi _t(𝐰)}`$. ∎

###### Lemma 23

$`\pi _e(1+\nu )^4(1+\frac{\gamma _t}{2})e^{\mathrm{\Gamma }\sigma }`$, where $`\nu `$ appears in the definition of $`\delta _t^{}`$ in Lemma 20, $`\gamma _t`$ appears in (12), and $`\mathrm{\Gamma }`$ and $`\sigma `$ appear in (16).

###### Proof.

Extend our $`\delta _t^{}`$-hypercube partition of $`𝕎`$ to the hyperplane containing $`𝕎`$ and let $`\mathrm{\Psi }`$ be the set of centers of the hypercubes in this extended partition. For $`K^k\mathrm{}`$, let $`\mathrm{\Psi }_K`$ be the set of grid points $`𝐰\mathrm{\Psi }`$ such that $`C(𝐰)K\mathrm{}`$, so that $`\mathrm{\Omega }=\mathrm{\Psi }_𝕎`$. By Lemma 20, for $`K𝕎`$,

$$\frac{1}{1+\nu }\underset{𝐰\mathrm{\Psi }_K}{}F_t(𝐰)\mathrm{Vol}(C(𝐰)K)_KF_t(𝐰)𝑑𝐰(1+\nu )\underset{𝐰\mathrm{\Psi }_K}{}F_t(𝐰)\mathrm{Vol}(C(𝐰)K).$$
(18)
Using the notation of Lemma 19, let $`𝕎^{}=𝕎^{(k\sigma )}`$ be a “scaled-in” version of $`𝕎`$; we showed in Lemma 19 that for $`𝐰𝕎^{}`$, $`F_t(𝐰)=_t(𝐰)`$ and that

$$_𝕎^{}F_t(𝐰)𝑑𝐰=_𝕎^{}_t(𝐰)𝑑𝐰\frac{1}{1+\frac{\gamma _t}{2}}_𝕎_t(𝐰)𝑑𝐰.$$
(19)
Let $`𝕎^{\prime \prime }=𝕎^{(\delta _t^{}(\nu ))}`$ be a “scaled-out” version of $`𝕎`$ and extend the domains of $`F_t()`$ and $`_t()`$ to $`𝕎^{\prime \prime }`$ by defining $`F_t(𝐰^{\prime \prime })=F_t(\overline{𝐰}^{\prime \prime })`$ and $`_t(𝐰^{\prime \prime })=_t(\overline{𝐰}^{\prime \prime })`$ for $`𝐰^{\prime \prime }𝕎^{\prime \prime }𝕎`$, where $`\overline{𝐰}^{\prime \prime }`$ is the point where the line between $`𝐰^{\prime \prime }`$ and $`𝐩^{\mathrm{}}=(𝐩,\mathrm{},𝐩)𝕎`$ intersects the boundary of $`𝕎`$. By Lemma 20 and the construction of the extension of $`_t`$, $`_t(𝐰^{\prime \prime })(1+\nu )_t(𝐰)`$ and

$$_{𝕎^{\prime \prime }}_t(𝐰)𝑑𝐰(1+\nu )_𝕎_t(𝐰)𝑑𝐰.$$
(20)
By construction of $`𝕎^{\prime \prime }`$, $`C(𝐰)𝕎^{\prime \prime }`$ for $`𝐰\mathrm{\Omega }_e`$; from the definition of $`F_t`$ and the choice of $`\delta _t^{}`$, $`F_t(𝐰)(1+\nu )e^{\mathrm{\Gamma }\sigma }_t(𝐰)`$ for $`𝐰\mathrm{\Omega }_e`$. Using these facts,

$`\pi _e`$ $`=`$ $`{\displaystyle \frac{_{𝐰\mathrm{\Omega }_e}F_t(𝐰)}{_{𝐰\mathrm{\Omega }}F_t(𝐰)}}{\displaystyle \frac{\delta _t^{(k1)\mathrm{}}}{\delta _t^{(k1)\mathrm{}}}}{\displaystyle \frac{(1+\nu )e^{\mathrm{\Gamma }\sigma }_{𝐰\mathrm{\Omega }_e}_t(𝐰)}{_{𝐰\mathrm{\Omega }}F_t(𝐰)}}`$
$``$ $`(1+\nu )e^{\mathrm{\Gamma }\sigma }{\displaystyle \frac{_{𝐰\mathrm{\Psi }_{𝕎^{\prime \prime }}}\mathrm{Vol}(C(𝐰)𝕎^{\prime \prime })_t(𝐰)}{_{𝐰\mathrm{\Psi }_𝕎}\mathrm{Vol}(C(𝐰)𝕎)F_t(𝐰)}}\text{(since }\mathrm{Vol}(C(𝐰))=\delta _t^{(k1)\mathrm{}}\text{)}`$
$``$ $`(1+\nu )e^{\mathrm{\Gamma }\sigma }{\displaystyle \frac{(1+\nu )_{𝕎^{\prime \prime }}_t(𝐰)𝑑𝐰}{\frac{1}{(1+\nu )}_𝕎F_t(𝐰)𝑑𝐰}}\text{(by (}\text{18}\text{))}`$
$``$ $`(1+\nu )^3e^{\mathrm{\Gamma }\sigma }{\displaystyle \frac{_{𝕎^{\prime \prime }}_t(𝐰)𝑑𝐰}{_𝕎^{}F_t(𝐰)𝑑𝐰}}(1+\nu )^4(1+{\displaystyle \frac{\gamma _t}{2}})e^{\mathrm{\Gamma }\sigma }\text{(by (}\text{19}\text{) and (}\text{20}\text{)).}`$
###### Remark 11

We simplify notation below by using $`𝒪^{}()`$ notation, which ignores logarithmic and constant terms. For our purposes, $`f()=𝒪^{}(g())`$ if there exists a constant $`C0`$ such that $`f()=𝒪(g()\mathrm{log}^C(k\mathrm{}mt/\epsilon ))`$. The values derived above in this notation are $`\gamma _t=𝒪^{}(\frac{\epsilon ^2}{mt^4})`$, $`\delta _t=𝒪^{}(\frac{\nu }{mt^4k\mathrm{}})`$, $`\sigma =𝒪^{}(\frac{\epsilon ^2}{m^2t^8k^2\mathrm{}})`$, $`\delta _t^{}=𝒪^{}(\frac{\nu }{\mathrm{\Gamma }mt^4k\mathrm{}})`$, $`\mathrm{log}\frac{1}{\pi _{}}=𝒪^{}(k\mathrm{}\mathrm{\Gamma }\sigma +t)`$, $`M=𝒪^{}(\frac{m^2t^4}{\epsilon ^2})`$, and $`\pi _e=𝒪^{}(e^{\mathrm{\Gamma }\sigma })`$.

###### Theorem 24

Letting $`\mathrm{\Gamma }=𝒪^{}(\frac{1}{\sigma })=𝒪^{}(\frac{m^2t^8k^2\mathrm{}}{\epsilon ^2})`$, the random walk reaches a distribution $`\stackrel{~}{\pi }`$ that satisfies (12) after $`\tau =𝒪^{}(\frac{k^7\mathrm{}^6m^6t^{24}}{\kappa \nu ^2\epsilon ^4})`$ steps.

###### Proof.

We show how to bound the right-side of (15), where the grid spacing $`\delta _t`$ has been replaced by $`\delta _t^{}`$. The second term, $`\frac{M\pi _ek\mathrm{}d^2}{\kappa \delta _{t}^{}{}_{}{}^{2}}`$, can be made exponentially small in $`\mathrm{\Gamma }`$ by choosing $`\mathrm{\Gamma }=𝒪^{}(\frac{1}{\sigma })`$. The value of $`\tau `$ stated in the theorem is large enough to make the first term, $`e^{\frac{\kappa \tau \delta _{t}^{}{}_{}{}^{2}}{k\mathrm{}d^2}}\mathrm{log}\frac{1}{\pi _{}}`$, exponentially small in $`\tau `$. ∎

###### Theorem 25

Suppose that the distribution $`p_{\tau _0}`$ obtained after $`\tau _0`$ steps satisfies

$$\underset{𝐰\mathrm{\Omega }}{}\left|\pi (𝐰)p_{\tau _0}(𝐰)\right|\gamma _t.$$

After $`\tau _0^{}\frac{\tau _0}{\tau _0\mathrm{log}\frac{1}{\pi _{}}\mathrm{log}\frac{1}{\gamma _t}}\mathrm{log}\frac{1}{\pi _{}}=𝒪^{}(\tau _0(k\mathrm{}+t))`$ steps, the resulting distribution $`p_{\tau _0^{}}`$ satisfies

$$\underset{𝐰\mathrm{\Omega }}{\mathrm{max}}\frac{p_{\tau _0^{}}(𝐰)}{\pi (𝐰)}11,$$

which implies (13).

###### Proof.

Let $`d(\tau )=\frac{1}{2}_{𝐰\mathrm{\Omega }}\left|\pi (𝐰)p_\tau (𝐰)\right|`$ and $`\widehat{d}(\tau )=\mathrm{max}_{𝐰\mathrm{\Omega }}\frac{p_\tau (𝐰)}{\pi (𝐰)}1`$ so that $`d(\tau _0)\frac{1}{2}\gamma _t`$. Aldous and Fill prove \[1, Equations (5) and (6)\] that if $`\tau \frac{1}{\lambda }\mathrm{log}\frac{1}{\pi _{}}`$, then $`\widehat{d}(\tau )1`$, where $`\pi _{}=\mathrm{min}_{w\mathrm{\Omega }}\pi _t(w)`$ is as defined in the statement of Theorem 17 and $`\lambda `$ is the second-largest eigenvalue of the steady-state transition matrix $`P`$ of $`\pi _t`$.

To prove the bound on $`\tau _0^{}`$, we show that $`\lambda \frac{\tau _0\mathrm{log}\frac{1}{\pi _{}}\mathrm{log}\frac{1}{\gamma _t}}{\tau _0}=1\frac{\mathrm{log}\frac{1}{\pi _{}}+\mathrm{log}\frac{1}{\gamma _t}}{\tau _0}`$. We do this by appealing to a result from Sinclair \[16, Proposition 1 (i)\], which states that

$$\tau _0\frac{\mathrm{log}\frac{1}{\pi _{}}+\mathrm{log}\frac{1}{\gamma _t}}{1\lambda }.$$

Solving for $`\lambda `$ yields the bound for $`\tau _0^{}`$. The $`𝒪^{}()`$ bound comes from the fact that $`\mathrm{\Gamma }\sigma =𝒪^{}(1)`$ and that $`\mathrm{log}\frac{1}{\gamma _t}`$ and $`\mathrm{log}\frac{1}{\pi _{}}`$ are low-order terms relative to the $`\tau _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 $`_n(S())`$ are log-concave. Theorem 26 and Corollary 27 characterize such functions.

###### Theorem 26

Given investment strategy $`S`$, suppose that for all parameters $`w_i`$ and $`w_j`$, $`\frac{^2S}{w_iw_j}=0`$. Then $`_t(𝐰)=_t(S(𝐰))`$ is log-concave.

###### Proof.

Let $`r_t(𝐰)=S_t(𝐰)𝐱_t`$, so that $`_n(𝐰)=_{t=0}^{n1}r_t(𝐰)`$. Since log-concave functions are closed under multiplication, we need only show that $`r_t(𝐰)`$ is log-concave. The gradient vector of $`\mathrm{log}r_t(𝐰)`$ has $`i`$-th element $`\frac{\mathrm{log}r_t(𝐰)}{w_i}=\frac{1}{r_t(𝐰)}\frac{r_t(𝐰)}{w_i}`$ and the matrix of second derivatives has $`(i,j)`$-th element

$$\frac{1}{r_t(𝐰)^2}\frac{r_t(𝐰)}{w_i}\frac{r_t(𝐰)}{w_j}+\frac{1}{r_t(𝐰)}\frac{^2r_t(𝐰)}{w_iw_j}=\frac{1}{r_t(𝐰)^2}\frac{r_t(𝐰)}{w_i}\frac{r_t(𝐰)}{w_j}$$

since $`\frac{^2r_t(𝐰)}{w_iw_j}=_{\iota =1}^m\frac{^2S_{t\iota }(𝐰)}{w_iw_j}x_{t\iota }=0`$ by assumption. The matrix of second derivatives is negative semidefinite, implying that $`\mathrm{log}r_t(𝐰)`$ 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 $`\text{MA}[k]`$ and $`\text{SR}[k]`$ with long/short allocation functions $`g_{\mathrm{}}(x)`$ and $`h_p(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. ∎

## 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  are a special case of Theorem 5. These proofs not only prove that $`_n(𝒰(\text{CRP}))`$ converges to $`_n(\text{CRP}(𝐰_n^{}))`$, but also prove a bound on the rate of convergence,

$$\frac{_n(\text{CRP}(𝐰_n^{}))}{_n(𝒰(\text{CRP}))}\left(\genfrac{}{}{0pt}{}{n+m1}{m1}\right)(n+1)^{m1}.$$

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.


format: text

text:
# Strings from Quivers, Membranes from Moose

## Acknowledgements

We thank Robbert Dijkgraaf, Veronika Hubeny, Igor Klebanov, Juan Maldacena, Horatiu Nastase, Nati Seiberg, Savdeep Sethi, Mohammed Sheikh-Jabbari, Charles Thorn and Herman Verlinde for helpful discussions and comments. The work of SM is supported in part by DOE grant DE-FG02-90ER40542 and by the Monell Foundation. The work of MR and EV is supported by NSF-grant PHY-9802484 and DOE grant DE-FG02-91ER40571 respectively.