\documentstyle[colt97,times]{article} 
\newcommand{\inv}[1]{\frac{1}{#1}}
\newcommand{\qed}{\rule{5pt}{7pt}\bigskip}

\begin{document}


\bibliographystyle{alpha}
\title{Universal Portfolios With and Without Transaction Costs}

\author{ {\bf Avrim Blum \thanks{
	Supported in part
	by NSF National Young Investigator grant CCR-9357793.}}\\
School of Computer Science\\
Carnegie Mellon University\\
Pittsburgh, PA 15213\\
avrim+@cs.cmu.edu
\And
{\bf Adam Kalai\thanks{Supported in part by an NSF Graduate Fellowship.}}\\
School of Computer Science \\
Carnegie Mellon University\\
Pittsburgh, PA 15213\\
akalai+@cs.cmu.edu}
%%\date{DRAFT DRAFT DRAFT}

\maketitle
\thispagestyle{empty}
\begin{abstract}
A constant rebalanced portfolio is an investment strategy which keeps
the same distribution of wealth among a set of stocks from period to period.
Recently there has been work on on-line investment strategies that
are competitive with the best constant rebalanced portfolio determined
in hindsight \cite{Cover, Helmbold, Cover2, Cover3, Cover4, Cover5}.  
For the universal algorithm of Cover \cite{Cover},
we provide a simple analysis which naturally extends to the case of a
fixed percentage transaction cost (commission), answering a question raised in 
\cite{Cover, Helmbold, Cover2, Cover3, Cover4, Cover5}.  
In addition, we present a simple randomized
implementation that is significantly faster in practice.
We conclude by explaining how these
algorithms can be applied to other problems,
such as combining the predictions of
statistical language models, where the resulting guarantees are more striking.
\end{abstract}

\section{Introduction}
A constant rebalanced portfolio (CRP) is an investment strategy which keeps
the same distribution of wealth among a set of stocks from period to period.
That is, the proportion of total wealth in a given stock is the
same at the beginning of each period.  
Recently there has been work on on-line investment strategies which
are competitive with the best CRP determined
in hindsight \cite{Cover, Helmbold, Cover2, Cover3, Cover4, Cover5},
 in the sense that the
daily performance of these algorithms approaches that of the best CRP
as the number of periods grows without bound.

As an example of a useful CRP, consider the following market with just
two stocks \cite{Helmbold, Cover4}.
The price of one stock remains constant, 
and the price of the other stock alternately halves and doubles.
Investing in a single
stock will not increase the wealth by more than a factor of two.
However, a $(\frac{1}{2},\frac{1}{2})$ CRP will increase its wealth
exponentially. At the end of each day it trades stock so that it has
an equal worth in each stock. 
On alternate days the total value will change by a factor of 
$\frac{1}{2}(1)+\frac{1}{2}(\frac{1}{2})=\frac{3}{4}$ and 
$\frac{1}{2}(1)+\frac{1}{2}(2)=\frac{3}{2}$, thus increasing total
worth by a factor of $9/8$ every two days.
 
We extend this model by adding a fixed percentage commission cost $c<1$ to
each transaction, as is common in financial modeling \cite{Davis}.
For simplicity, we will assume that this cost applies to buying stock
but not selling.  To fully define the commission model, in addition to
specifying the cost of each 
transaction, we must also specify how a CRP pays this overhead.  In Section
2, we give
three natural properties of such a specification which we will use for
our analysis.  These properties are satisfied by the optimal investor
who must simultaneously rebalance her portfolio and pay for these
transaction costs from the sale of stock.

In Section 3 we present a new, simpler analysis
and implementation for Cover's universal algorithm \cite{Cover}, and
show how this extends to the case 
of commission in Section 4.  The previous bound for a market with $m$
assets and $n$ periods was a performance ratio of at least
\[\frac{\mbox{wealth of UNIVERSAL}}{\mbox{wealth of best CRP}} \geq 
\frac{1}{(n+1)^{m-1}}.\]
In the presence of a commission $c$, this becomes
\[\frac{\mbox{wealth of UNIVERSAL}_c}{\mbox{wealth of best CRP}} \geq \frac{1}{((1+c)n+1)^{m-1}}.\]

The above ratio is a decreasing function of $n$.  However, the average 
per-period ratio, $(1/(n+1)^{m-1})^{1/n}$, increases to $1$ as $n$
increases without bound.  For example, if the best CRP makes one and a
half times as much as we do over a period of 22 years, it is only making a
factor of $1.5^{1/22} \approx 1.02$ as much as we do per year.  Our
analysis resolves the question raised in \cite{Cover2} of whether it is
even possible to achieve the exponential growth rate of the best CRP
in the presence of commission.  However, we do not consider the
Dirichelet$(1/2, \ldots, 1/2)$ Universal algorithm \cite{Cover2} which
has the better guaranteed ratio of $2\sqrt{1/(n+1)^{m-1}}$.

Semi-constant-rebalanced
portfolios, which may or may not rebalance during each period, have
been suggested as an investment strategy in the presence of
commission \cite{Helmbold}. In Section 5 we show that the exponential
wealth of a semi-constant-rebalanced portfolio cannot, in general,
be achieved without future knowledge of the market.

Finally, in Section 6, we explain how these stock market algorithms
can be used on other problems, such as combining the predictions of 
language models almost as
well as if we had prior knowledge of the optimal mixture.

\section{Notation and Definitions}
We use mainly the notation of \cite{Cover}.  A price relative for a given
asset is the nonnegative ratio of closing price to opening price during
a given period.  If the market has $m$ assets and trading takes place during $n$
periods, then the market's performance can be expressed by $n$ price
relative vectors, ${\bf x}^n=({\bf x}_1,{\bf x}_2,\ldots,{\bf
x}_n), {\bf x}_i \in \Re_+^m$, 
where $x_{ij}$ is
the nonnegative price relative of the $j^{\mbox{th}}$ stock for the
$i^{\mbox{th}}$ period.  
 
A portfolio is simply a distribution of wealth
among the stocks.  We represent a distribution of wealth by 
${\bf b} \in \Re^m_+,$ where $\sum_jb_j=1.$  So ${\bf b}$ is an element of the
$(m-1)$-dimensional simplex $\beta,$
$$\beta = \{{\bf b} = (b_1,b_2,\ldots,b_m): \sum_jb_j=1, \forall_j \ b_j \geq 0\}.$$
The CRP investment strategy
for a particular portfolio ${\bf b},$ $\mbox{CRP}_{\bf b},$
redistributes its wealth at the end of each period so that the proportion
of money in the $j^{\mbox{th}}$ stock is $b_j$.
An investment using a portfolio ${\bf b}$ during a period with price relatives
${\bf x}$ increases one's wealth
by a factor of ${\bf b} \cdot {\bf x} = \sum b_j x_j.$
Therefore, over $n$ periods, the wealth achieved by $\mbox{CRP}_{\bf b}$ is,
\[S_n({\bf b},{\bf x}^n) = \prod_{i=1}^n {{\bf b} \cdot {\bf x}_i}.\]
%Finally, for a market sequence ${\bf x}^n$, we let ${\bf b}^*({\bf
%x}^n)$ or just ${\bf b}^*$ denote an
%optimal CRP and $S_n^*({\bf x}^n)$ the wealth achieved by $\mbox{CRP}_{{\bf b}^*}$,
%i.e., ${\bf b}^* = \arg \max_{\bf b} S_n({\bf b},{\bf x}^n)$ and $S_n^*({\bf
%x}^n) = \max_{\bf b} S_n({\bf b},{\bf x}^n)$.

\subsection{Commission}
Suppose we have a fixed percentage commission $0 \leq c \leq 1$ charged for
buying each stock.  We need to specify how an investor, who needs
to achieve a target distribution of wealth, pays for
these transaction costs.  We would like a model with the following natural
properties:
\begin{enumerate}
\item The costs paid changing from distribution ${\bf b}_1$ to ${\bf
b}_3$ should be no more than the costs paid changing from ${\bf b}_1$
to ${\bf b}_2$ and then from ${\bf b}_2$ to ${\bf b}_3$.
\item The cost, per dollar, of changing from a distribution ${\bf b}$
to a distribution $\alpha{\bf b}+(1-\alpha){\bf b}'$ should be no more
than $(1-\alpha)c$.  Essentially, this is saying that we do not pay
too much commission between distributions that are ``close.''
\item An investment strategy $I$ which invests an initial fraction $\alpha$ of its
money according to investment strategy $I_1$ and an initial $1-\alpha$ of its
money according to $I_2$, should
achieve at least $\alpha$ times the wealth of $I_1$ plus $1-\alpha$
times the wealth of $I_2$.
%%  This is like the statement that a collection of investors
%%  operating together can save by occasionally trading amongst
%%  themselves. 
(In fact, $I$ may do even better by occasionally saving in commission
cost if, for instance, strategy $I_1$ says to sell stock A and
strategy $I_2$ says to buy it.)
\end{enumerate}

The above three properties are all we need for our analysis.  
To make this more concrete, consider the following setting.
We assume that the investor must initially sell some stock
to get cash to pay for her transaction costs.  For example, suppose there is a
hefty $40\%$ commission on each purchase.  Say, at the
end of a period, an
investor has $\$200$ in stock A, and $\$800$ in stock B, and this
investor wishes to rebalance to a $(1/2,1/2)$ portfolio.  The optimal
investor would first sell $\$100$ of stock B to cover the upcoming
transaction costs.  She now has $\$200$ in stock A, $\$700$ in
stock B, and $\$100$ in cash.  When
 she trades $\$250$ of stock B for stock A to get a
$\$450$, $\$450$ portfolio, she then pays her  $(40\%)\$250=\$100$ in
transaction costs.  

Our analysis will not depend on the specifics of this optimal investor.
More formally, though, the optimal investor pays $comm^c({\bf b},{\bf b'})$ per
dollar to change from portfolio ${\bf b} \in \beta$ to ${\bf b'} \in
\beta$.  For each dollar initially in ${\bf b}$, she
will have $1-comm^c({\bf b},{\bf b'})$ dollars distributed according
to ${\bf b'}$, with $w_j=b'_j(1-comm^c({\bf b},{\bf b'}))$ dollars in the
$j^{\mbox{th}}$ stock, so ${\bf w}=(1-comm^c({\bf b},{\bf b'})){\bf
b'}$.  This optimal investor has sold only stock
which is in excess of $w_j$, so that she
never sells and buys the same stock.  Thus her total purchases are,
\[  
\sum_{j: w_j > b_j}\left(
w_j-b_j\right).
\]
The optimality criterion is that her total wealth decreases by exactly
the amount required to pay for these transaction costs.  Thus, 
$comm^c({\bf b},{\bf b'})$ is the unique solution of:
\[  
comm^c({\bf b},{\bf b'})=c\sum_{j: w_j > b_j}\left(w_j-b_j\right).
\]

This type of optimal investor clearly satisfies the three properties.  She
satisfies the first property because, being optimal, she
does at least as well as an investor who changes his portfolio twice.
She satisfies the second property because her net purchases must be
less than $(1-\alpha){\bf b'}$.  Finally, the investor satisfies the
third property because she pays less commission than the naive
investor who never takes advantage of offsetting transactions and
achieves exactly 
 $\alpha$ times the wealth of $I_1$ plus $1-\alpha$
times the wealth of $I_2$. 

Based on this model, a $\mbox{CRP}_{{\bf b}}$ investor achieves wealth
\[S^c_n({\bf b},{\bf x}^n) = \prod_{i=1}^n {\bf b} \cdot {\bf x}_i
(1-comm^c({\bf b'}({\bf x}_i),{\bf b})),\]
where ${\bf b'}({\bf x}_i)$ is the distribution of wealth of
$\mbox{CRP}_{{\bf b}}$ after seeing price relatives ${\bf x}_i$. That is, ${\bf
b'}({\bf x}_i)_j = b_jx_{ij}/{\bf b} \cdot {\bf x}_i$.
Fortunately, we will not need this formula in our analysis; we will
only use the three properties given earlier.

%Similarly, for a market sequence ${\bf x}^n$, we let ${\bf b}^{c*}({\bf
%x}^n)$ or just ${\bf b}^{c*}$ denote an
%optimal CRP and $S_n^{c*}({\bf x}^n)$ the wealth achieved by 
%$\mbox{CRP}_{{\bf b}^{c*}}$,
%i.e., ${\bf b}^{c*} = \arg \max_{\bf b} S^c_n({\bf b},{\bf x}^n)$ and $S^{c*}_n({\bf
%x}^n) = \max_{\bf b} S^c_n({\bf b},{\bf x}^n)$.

\section{Analysis Without Commission}
In this section, we give a simple analysis of the universal algorithm
of Cover, without commission.  To get our bearings, let's first
consider an easier question.  Suppose you just wanted a strategy that
was competitive with respect to the best single stock.  In other words, 
you want to maximize the worst-case ratio of your wealth to
that of the best stock.  In this case, a good strategy is to simply
divide your money among the $m$ stocks and 
let it sit.  You will always have at least $\frac{1}{m}$ times as much
money as the best stock.  Note that this deterministic strategy
achieves the expected wealth 
of the randomized strategy that just places all its money in a random stock.


Now consider the problem of competing with the best CRP.  Cover's
universal portfolio algorithm is similar to the above.  It splits its
money evenly among all CRPs and lets it sit in these CRP strategies.
Likewise, it always achieves the expected wealth of the randomized strategy which
invests all its money in a random CRP.  In particular, the bookkeeping
works as follows:
\begin{definition}{{\bf (UNIVERSAL)}} The  universal
portfolio algorithm, UNIVERSAL, at time i is specified by 
$${\bf \hat b}_i = 
\frac{\int_{\beta}{{\bf b}S_{i-1}({\bf b},{\bf x}^{i-1})d\mu({\bf b})}}
{\int_{\beta}{S_{i-1}({\bf b},{\bf x}^{i-1})d\mu({\bf b})}}, \ i = 1, 2,
\ldots$$
with $\mu$ equal to the uniform distribution over portfolios ${\bf
b}$.  (We do not consider the Dirichelet$(1/2,1/2,\ldots)$ distribution.)
\end{definition}

\begin{theorem}
As in \cite{Cover2},
\begin{eqnarray*}
\frac{\mbox{wealth of UNIVERSAL}}{\mbox{wealth of best CRP}} & \geq & 
\left( \begin{array}{c} n+m-1 \\ m-1 \end{array} \right)^{-1} \\
& \geq & \inv{(n+1)^{m-1}},
\end{eqnarray*} for all markets with $m$ stocks and $n$ periods.
\end{theorem}

\noindent
{\bf Proof.}
As mentioned above and in \cite{Cover2}, 
the wealth of UNIVERSAL is simply the expected
wealth of a random CRP.  Say, in hindsight, ${\bf b}^*$ is an optimal
CRP for the particular market.  Then,
\begin{eqnarray}
\frac{\mbox{wealth of UNIVERSAL}}{\mbox{wealth of best CRP}} =
\mbox{E}_{{\bf b} \in \beta}\left[
\frac{\mbox{wealth of CRP}_{\bf b}}{\mbox{wealth of CRP}_{{\bf
b}^*}}\right]\!. \label{eq:exp}
\end{eqnarray}

Next, we observe that ``close'' portfolios will perform almost as well
as ${\bf b}^*$.  Specifically, if $b_j \geq y b^*_j, $ for all $j$, then 
\begin{eqnarray}
\mbox{wealth of CRP}_{\bf b} \geq y^n (\mbox{wealth of CRP}_{{\bf
b}^*}). \label{eq:close}
\end{eqnarray}
So, to prove the theorem, we just need to show that a sufficiently
large volume of portfolios is sufficiently close to ${\bf b}^*$ to
make the expectation in (\ref{eq:exp}) sufficiently large.  Let
\begin{eqnarray*}
r({\bf b}) = \max\{y: b_j \geq y b^*_j, \mbox{for all } j\}.
\end{eqnarray*}
So, the wealth of $\mbox{CRP}_{\bf b}$ is at least $r({\bf
b})^n$ times the wealth of CRP$_{{\bf b}^*}$, and therefore the ratio
in (\ref{eq:exp}) is at least the expectation of $r({\bf b})^n$.
This expectation can be conveniently rewritten,
\begin{eqnarray*}
\mbox{E}_{{\bf b} \in \beta}[r({\bf b})^n] &=& 
\int_0^1 \mbox{Prob}_{{\bf b} \in \beta}[r({\bf b})^n \geq x]dx
 \\
&=& \int_0^1 \mbox{Prob}_{{\bf b} \in \beta}[b_j \geq x^{1/n} b^*_j,
\mbox{for all } j]dx. 
\end{eqnarray*}

This last probability is easy to compute, because $\{{\bf b} \in \beta: b_j \geq
y b_j^*, \mbox{for all } j\}$ is a shrunken simplex, translated from
the origin to $y{\bf b}^*$.
\begin{eqnarray*}
\lefteqn{\mbox{Prob}_{{\bf b} \in \beta}[b_j \geq y b^*_j,
\mbox{for all } j] =} \\
 &=& \frac{\mbox{Vol}_{m-1}(\{{\bf b} \in \beta: b_j \geq
y b_j^*, \mbox{for all } j\})}
{\mbox{Vol}_{m-1}(\beta)} \\
 &=& \frac{\mbox{Vol}_{m-1}(\{y{\bf b}^* + (1-y){\bf b}: {\bf b} \in \beta\})}
{\mbox{Vol}_{m-1}(\beta)} \\
 &=& \frac{\mbox{Vol}_{m-1}((1-y)\beta)}
{\mbox{Vol}_{m-1}(\beta)} \\
 &=& (1-y)^{m-1}. 
\end{eqnarray*}

All that remains is to evaluate an integral:
\begin{eqnarray*}
\frac{\mbox{wealth of UNIVERSAL}}{\mbox{wealth of best CRP}} &\geq&
\int_0^1 (1-x^{1/n})^{m-1}dx \\
&=& n \int_0^1 y^{n-1} (1-y)^{m-1} dy.
\end{eqnarray*}
This follows from the change of variable, $y=x^{1/n}$.
Using integration by parts repeatedly, this last quantity becomes,
\begin{eqnarray*}
\lefteqn{
n\left(\left.\frac{y^n(1-y)^{m-1}}{n}\right|_0^1+\frac{m-1}{n}\int_0^1 y^{n}
(1-y)^{m-2} dy\right)}\\
&=& n\left( \frac{m-1}{n}\int_0^1 y^{n}
(1-y)^{m-2} dy\right) \\
&=& n\left( \frac{m-1}{n}\frac{m-2}{n+1}\int_0^1 y^{n+1}
(1-y)^{m-3} dy\right) \\
&=& \ldots \\
&=& n\left(\frac{(m-1)!(n-1)!}{(n+m-2)!}\int_0^1 y^{n+m-2}dy\right)\\
&=& \frac{1}{\left( \begin{array}{c}n+m-1 \\ m-1 \end{array}
\right)}.
\end{eqnarray*} 
\qed

\subsection{Randomized Approximation}
The implementation presented in \cite{Cover2} has space and time
requirements which grow like $n^{m-1}$.  
However, the universal algorithm is simply a weighted average of all
CRPs.  This suggests an obvious randomized approximation.  First
choose $N$ portfolios
uniformly at random.  Then invest $1/N^{\mbox{th}}$ of the money in
each of the $N$ CRPs.  If the best constant
rebalanced portfolio achieves a wealth R times as large as the
universal algorithm, Chebyshev's inequality guarantees that, using 
$N=(R-1)/{\epsilon^2 \delta}$ random portfolios, with
probability at least
$1-\delta$, the approximation achieves a wealth at
least $1-\epsilon$ times as large as the universal algorithm.
For a given market with
no commission, one can determine, in hindsight, the optimal CRP
\cite{Helmbold2} and then estimate $R$.
In the worst case $R$ grows like $n^{m-1}$.  
However, experiments on stock
market data, presented in \cite{Cover, Helmbold}, all have a ratio
$R<2$ for various combinations of two stocks, making this approach
especially efficient.

This same observation can be used to implement the
Dirichelet$(1/2,\ldots,1/2)$ universal algorithm \cite{Cover2}.  In
this case, it is an improvement because R grows, at worst, like $n^{(m-1)/2}$.
%%The implementation in \cite{Cover}
%%is too slow to run on three stocks over a long period of
%%time (simulations were daily for 22 years).

\section{Analysis With Commission}
In this section, we introduce a slight
modification of UNIVERSAL, $\mbox{UNIVERSAL}_c$, 
which is competitive in the
presence of a fixed commission $0 \leq c \leq 1$.  
The importance of this section is not as much in
introducing a new algorithm as it is in showing that a trivial
extension of UNIVERSAL is theoretically
competitive in the presence of commission.

At the start of the $i^{\mbox{th}}$ period, UNIVERSAL computes a
weighted average of CRPs, where the weight of a particular
$\mbox{CRP}_{\bf b}$ is proportional to the wealth it has accumulated during
the first $i-1$ days, $S_{i-1}({\bf b},{\bf x}^{i-1})$.
$\mbox{UNIVERSAL}_c$ is similar.  At the start of the $i^{\mbox{th}}$
period, $\mbox{UNIVERSAL}_c$ computes a
weighted average of CRPs, where the weight of a particular
$\mbox{CRP}_{\bf b}$ is proportional to the wealth it has accumulated during
the first $i-1$ days {\em including commission costs}, 
$S^c_{i-1}({\bf b},{\bf x}^{i-1})$.  Formally,
\begin{definition}{$(\mbox{UNIVERSAL}_c)$} The  universal
portfolio with commission algorithm  at time i is specified by
$${\bf \hat b}_i^c = 
\frac{\int_{\beta}{{\bf b}S^c_{i-1}({\bf b},{\bf x}^{i-1})d\mu({\bf b})}}
{\int_{\beta}{S^c_{i-1}({\bf b},{\bf x}^{i-1})d\mu({\bf b})}}, \ i = 1, 2,
\ldots$$
with $\mu$ equal to the uniform distribution over portfolios ${\bf
b}$. 
\end{definition}

In the zero-commission case, the wealth of the UNIVERSAL algorithm was
equal to the expected wealth of a CRP chosen at random.  In the presence
of commission $c$, the wealth of UNIVERSAL$_c$ is {\em at least} as large as
this expectation.   It can actually be larger because of lower
commission costs due to offsetting trades (in the same way that a
collection of investors operating together can save on commission by
occasionally trading amongst themselves).  This is the third property
given in Section 2.1.
Conceivably one might be
able to use this to prove a {\em better} bound in the presence of
commission.  We have not been able to do this, but we do get a bound
that is nearly as good, as follows.

\begin{theorem}
{In the presence of commission $0 \leq c \leq 1$,
\begin{eqnarray*}
\frac{\mbox{wealth of UNIVERSAL}_c}{\mbox{wealth of best CRP}} & \geq
& \left( \begin{array}{c} (1+c)n+m-1 \\ m-1 \end{array} \right)^{-1}\\
& \geq & \inv{((1+c)n+1)^{m-1}},
\end{eqnarray*}
for all markets with $m$ stocks and $n$ periods.}
\end{theorem}

\noindent
{\bf Proof.} 
We need only modify equations (\ref{eq:exp}) and (\ref{eq:close}) of
the previous proof.  As discussed above, equation (\ref{eq:exp})
changes from an equality to an inequality, 
\[
\frac{\mbox{wealth of UNIVERSAL}_c}{\mbox{wealth of best CRP}} \geq
\mbox{E}_{{\bf b} \in \beta}\left[
\frac{\mbox{wealth of CRP}_{\bf b}}{\mbox{wealth of CRP}_{{\bf
b}^*}}\right],
\]
which only helps.  
%% We may think of $\mbox{wealth of UNIVERSAL}_c$ as a collection of
%% CRP investors, in which case the above inequality is equivalent to the
%% statement that the investors can only pay less in commission trading
%% together because of offsetting trades. 

Based on the three properties given in Section
2.1, if $b_j \geq y b^*_j,$ for all $j$ then
\begin{eqnarray}
\frac{(\mbox{single-period profit of CRP}_{\bf b})}
{(\mbox{single-period profit of CRP}_{{\bf b}^*})} \geq y(1-c(1-y)). \label{eq:os}
\end{eqnarray}
To see this, note first that $\mbox{CRP}_{\bf b}$ earns at least as much as
an investor who only has $y$ times as much money, but begins with it
distributed according to ${\bf b}^*$ and ends with it distributed
according to ${\bf b}$.  In other words, the extra stock beyond $y
b^*_j$ cannot hurt.  (This also follows from the third property.)
Secondly, note that this investor pays no more in commission than a
naive investor who first rebalances to ${\bf b}^*$ and then to ${\bf
b}$, by the first property.  Finally, the second property implies that
the commission cost for changing from ${\bf b}^*$ to ${\bf b}$ is no
more than $c(1-y)$.  Thus, $\mbox{CRP}_{\bf b}$ does no worse than
$y(1-c(1-y))$ times an investor who starts and ends the period with
distribution ${\bf b}^*$.  This is (\ref{eq:os}).

Because of the concavity of the $\log$ function,
\begin{eqnarray*}
\log [{1-c(1-y)}] &=& \log [(1-c)1+cy] \\
&\geq&(1-c)\log 1 + c \log y \\
&=& \log y^c. 
\end{eqnarray*}
Combining this with (\ref{eq:os}),
\[
\mbox{wealth of CRP}_{\bf b} \geq y^{(1+c)n} (\mbox{wealth of CRP}_{{\bf
b}^*}). 
\]
Since (\ref{eq:close}) is the only use of $n$ in the previous proof, we can
replace $n$ by $(1+c)n$ in the final guarantee.  \qed

This algorithm can be implemented in the same randomized way as UNIVERSAL.

\section{Semi-constant-rebalanced Portfolios}
In \cite{Helmbold}, the idea of a semi-constant-rebalanced portfolio
(SCRP) is
proposed as a good strategy in the presence of transaction costs.  
An SCRP is a portfolio which may be rebalanced on any
subset of the periods.  For instance, one may prefer not to rebalance if the
transaction costs outweigh the benefits of rebalancing.  
We show that no strategy can
guarantee the exponential growth rate of the best
SCRP in hindsight, even without commission.

As in \cite{Cover3}, consider the set of all market sequences of
length $n$ over two
stocks, where each day one of the stock relatives is 1 and the other
is $\epsilon$ for some small $\epsilon \geq 0$,
$${\cal K} = \{ {\bf x}^n : {\bf x}_i = (1,\epsilon) \mbox{\ or\ }
{\bf x}_i = (\epsilon,1), 
\mbox{\ for all \ } i \leq n \}.$$
In these markets, each day one of the stocks crashes and the other
stays the same.

Clearly, if we choose a random element of ${\cal K}$, every
non-anticipating investment strategy (a strategy which has no
knowledge of the future) will achieve an expected wealth of
$(\frac{1+\epsilon}{2})^n$. 

%As stated in \cite{Cover2}, for any non-anticipating investment
%strategy which earns $\hat S_n({\bf x}^n)$,
%$$\sum_{{\bf x}^n \in \cal K} \hat S_n({\bf x}^n) = 1.$$
%This can be shown by elementary induction.

However, a SCRP chosen in hindsight
can do much better.  A
good $\mbox{SCRP}_{(\frac{1}{2},\frac{1}{2})}$ strategy would
initially 
divide its money into two parts, and
then rebalance only when the market is about to switch (when 
${\bf x}_i \neq {\bf x}_{i+1}$).  If the market switches $k$ times, this
strategy achieves wealth $\geq 1/2^{k+1}$.  Thus, if we choose a random
market from ${\cal K}$, in hindsight we can make at least
\[
(1/2)^n \sum_{k=0}^{n-1}
2 \left( \begin{array}{c} n-1 \\ k \end{array} \right) (1/2)^{k+1} =
(1/2)^n(1+1/2)^{n-1}.
\]  Thus the hindsight strategy's expected performance is at least
$(\inv{1+\epsilon})^n (3/2)^{n-1}$
times as large as the expected performance of any non-anticipating strategy.

\section{Application to Statistical Language Modeling}
Analogies between universal compression and the UNIVERSAL algorithm
have been made by Cover \cite{Cover5}.  The $\mbox{EG}(\eta)$
portfolio algorithm of \cite{Helmbold} has also been used for finding
the best mixture of predictive models \cite{Kivinen, Helmbold2}.
We would like to explicitly present an analogy between stocks and
language models which shows
how the UNIVERSAL algorithm can be
applied to language models and other predictors.
This analogy is more general than Kelly's racehorse analogy because it
covers price relatives other than just $\{0,1\}$.

A statistical language model is a probability distribution over
sequences of words.  A language model is
generally represented as a conditional probability
distribution for the next word to be seen, given the previous
words, i.e.,
\[ P(w_i|h_{i-1}), h_{i-1}=w_1,w_2,\ldots,w_{i-1}. \]

The most common way to combine various language models is to linearly
interpolate them.  A mixture of three language models, for example a
unigram model $P_1$, a bigram model $P_2$, and a trigram model $P_3$
might be,
\[
P(w|h_{i}) = \lambda_1 P_1(w|h_{i}) +
\lambda_2 P_2(w|h_{i}) +
\lambda_3 P_3(w|h_{i}),
\]
\[
\mbox{where }  \lambda_1 +  \lambda_2 +  \lambda_3 = 1,  \lambda_i
\geq 0.
\]
This is similar to a CRP.  If we
consider the analogy between language models and stocks, where a price
relative $x_{ij}$ corresponds to a conditional probability
$P_j(w_i|h_{i-1})$ and a portfolio ${\bf b}$ corresponds to a daily mixture
of language models, then the probability that a combined language
model algorithm assigns to a sequence $h_n = w_1, \ldots, w_n$ is simply the
value of the holdings of the corresponding portfolio algorithm.  The
log of the probability assigned to the observed sequence is a common
measure of a language model's performance.  This leads us to the
following algorithm.

Given language models $P_1, P_2, \dots, P_m$ and a sequence of words
$h_n = w_1, \ldots, w_n$, if UNIVERSAL invests its money based on
portfolios $\hat{\bf b}_i$ when observing price relatives $x_{ij} =
P_j(w_i|h_{i-1})$, then the universal language model $P$ predicts
\[P(w_i|h_{i-1}) = \sum_{j=1}^m \hat{b}_{ij} P_j(w_i|h_{i-1}).\]


\begin{theorem}{
For any sequence of $n$ words $h_n = w_1, \ldots, w_n$ and any $m$
language models, the log probability assigned to $h_n$ by the
universal algorithm $P$ is at least the log probability assigned to
$h_n$ by the best mixture, minus $(m-1) \log n$.}
\end{theorem}

This follows directly from the observation that the wealth of  a portfolio
algorithm is exactly the probability it assigns to the word sequence.
It is impressive because it shows how these mixture parameters can be
``learned'' on the fly with on-line guarantees.  Furthermore, the
amortized cost of $(m-1) \log n/n$ bits per word is a small overhead
as $n$ gets large. 
It also helps to explain a relationship between portfolios and
weighted-average-type algorithms for making predictions from
expert advice
\cite{CFHHSW93,DeSantis,FosVoh93,Haussler,Kivinen,Vovk90,Vovk95}.

\begin{thebibliography}{10}

\bibitem{CFHHSW93}
N.~Cesa-Bianchi, Y.~Freund, D.P. Helmbold, D.~Haussler, R.E. Schapire, and M.K.
  Warmuth.
\newblock How to use expert advice.
\newblock In {\em Annual ACM Symposium on Theory of Computing}, pages 382--391,
  1993.

\bibitem{Cover}
{T.M.} Cover.
\newblock Universal portfolios.
\newblock {\em Math. Finance}, 1(1):1-29, January 1991.

\bibitem{Cover2}
{T.M.} Cover and E.~Ordentlich.
\newblock Universal portfolios with side information.
\newblock {\em IEEE Transactions on Information Theory}, 42(2), March
1996.

\bibitem{Cover3}
{T.M.} Cover and E.~Ordentlich.
\newblock The Cost of Achieving the Best Portfolio in Hindsight.
\newblock Department of Statistics Technical Report NSF-90, Stanford
University, 1996.

\bibitem{Cover5}
{T.M.} Cover.
\newblock Universal data compression and portfolio selection.
\newblock In {\em Proceedings of the $37$th IEEE Symposium on Foundations of
  Computer Science}, pages 534-538, Oct 1996.


\bibitem{Davis}
M.H.A. Davis and A.R. Norman.
\newblock Portfolio Selection with Transaction Costs.
\newblock {\em Mathematics of Operations Research}, 15(4), November 1990.


\bibitem{DeSantis}
A.~DeSantis, G.~Markowsky, and M.~Wegman.
\newblock Learning probabilistic prediction functions.
\newblock In {\em Proceedings of the $29$th IEEE Symposium on Foundations of
  Computer Science}, pages 110--119, Oct 1988.

\bibitem{FosVoh93}
D.P. Foster and R.V. Vohra.
\newblock A randomization rule for selecting forecasts.
\newblock {\em Operations Research}, 41:704--709, 1993.

\bibitem{Haussler}
D.~Haussler, J.~Kivinen, and M.~Warmuth.
\newblock Tight worst-case loss bounds for predicting with expert
advice. 
\newblock Technical Report UCSC-CRL-94-36,
University of California, Santa Cruz, November 1994.

\bibitem{Helmbold}
D.~Helmbold, R.~Schapire, Y.~Singer, and M.~Warmuth.
\newblock On-line portfolio selection using multiplicative updates. 
\newblock {\em Machine Learning: Proceedings of the Thirteenth 
International Conference}, 1996.

\bibitem{Helmbold2}
D.~Helmbold, R.~Schapire, Y.~Singer, and M.~Warmuth.
\newblock A comparison of new and old algorithms for a mixture
estimation problem.
\newblock {\em Proceedings of the Eighth Annual Workshop on
Computational Learning Theory}, pages 69-78, 1995.

\bibitem{Kivinen}
J.~Kivinen and M~Warmuth.
\newblock Exponentiated gradient versus gradient descent for linear 
predictors. 
\newblock Technical Report UCSC-CRL-94-16, University of California, 
Santa Cruz, June 1994. 

\bibitem{Cover4}
E. Ordentlich. and {T.M.} Cover.
\newblock Online portfolio selection.
\newblock In {\em Proceedings of the 9th Annual Conference on Computational
Learning Theory}, Desenzano del Garda, Italy, 1996.

\bibitem{Vovk90}
V.~Vovk.
\newblock Aggregating strategies.
\newblock In {\em Proceedings of the Third Annual Workshop on Computational
  Learning Theory}, pages 371--383. Morgan Kaufmann, 1990.

\bibitem{Vovk95}
V.~G. Vovk.
\newblock A game of prediction with expert advice.
\newblock In {\em Proceedings of the 8th Annual Conference on Computational
  Learning Theory}, pages 51--60. ACM Press, New York, NY, 1995.

%\bibitem{Yamanishi}
%K. Yamanishi. 
%\newblock A loss bound model for on-line stochastic prediction
%algorithms. 
%\newblock {\em Information and Computation}, 119(1):39-54, 15 May 1995. 

\end{thebibliography}

\end{document}
