
\documentclass[jair,11pt,letterpaper]{article}
\usepackage{theapa}
\usepackage{jair}

\usepackage{amsmath,amssymb}
\usepackage{graphics,epsfig}
\usepackage[usenames,dvipsnames]{color}
\usepackage{color,epsfig}
\usepackage{graphicx}
\usepackage{latexsym}


\begin{document}


\jairheading{21}{2004}{579-594}{08/03}{05/04}
\ShortHeadings{Can We Learn to Beat the Best Stock}
{Borodin, El-Yaniv, \& Gogan}
\firstpageno{579}




%run latex2e
%\documentclass[twoside,11pt]{article}
%\usepackage{jmlr}
%\usepackage{amsmath,amssymb}
%\usepackage{graphics,epsfig}
%\usepackage[usenames,dvipsnames]{color}
%\usepackage{color,epsfig}
%\usepackage{graphicx}
%\usepackage{latexsym}
%
%
%
%\usepackage{epsf}

%\input{psfig.sty}
%\usepackage{graphics,epsfig}
%\usepackage[usenames,dvipsnames]{color}
%\newcommand{\Red}{\color{red}}
%\newcommand{\Blue}{\color{blue}}
%\newcommand{\Green}{\color{green}}
%\newcommand{\Black}{\color{black}}
%\newcommand{\Magenta}{\color{Magenta}}
%\newcommand{\rnote}[1]{{\Blue #1}}
%\newcommand{\bnote}[1]{{\Red #1}}
%
%\newcommand{\mnote}[1]
%{}
%
\include{macros-rev}




%\bibliographystyle{alpha}

\title{Can We Learn to Beat the Best Stock}

\author{\name Allan Borodin \email  bor@cs.toronto.edu \\
       \addr Department of Computer Science\\
       University of Toronto \\
       Toronto, ON, M5S 3G4 Canada
       \AND
       \name Ran El-Yaniv \email rani@cs.technion.ac.il \\
       \addr Department of Computer Science\\
       Technion - Israel Institute of Technology\\
       Haifa 32000, Israel
       \AND
       \name Vincent Gogan \email vincent@cs.toronto.edu \\
       \addr Department of Computer Science\\
       University of Toronto \\
       Toronto, ON, M5S 3G4 Canada
}


%\editor{}

\maketitle
%\thispagestyle{empty}

\begin{abstract}
A novel algorithm for actively trading stocks is presented. While
traditional expert advice and ``universal'' algorithms
(as well as standard technical trading
heuristics) attempt to predict winners or trends, our approach
relies on predictable statistical relations between all pairs of
stocks in the market. Our empirical results on historical markets
provide strong evidence that this type of technical trading can
``beat the market'' and moreover, can beat the best stock in the
market. In doing so we utilize a new idea for smoothing critical
parameters in the context of expert learning.
\end{abstract}





\newcommand{\sign}{\textrm{sign}}
\newcommand{\transfer}{\textsf{transfer}}
\newcommand{\claim}{\textsf{claim}}
\newcommand{\CS}{{\mbox{\em CS}}}
\newcommand{\LX}{\textsf{LX}}
\newcommand{\MX}{{\mbox{\em MX}}}
\newcommand{\tcorr}{{t_{\mbox{\tiny corr}}}}


\section{Introduction}
The portfolio selection (PS) problem is a challenging problem for machine learning,
online algorithms and, of course, computational finance. As is well known
\cite<e.g. see>{Lugosi01}
%the PS problem is intimately related to the problem of sequence
%prediction under log loss. Indeed as
sequence prediction under the log loss measure can be viewed as a special case of
portfolio selection,
%the investment problem
%is at least as hard as the sequence prediction problem and
and perhaps more surprisingly, from a certain  worst case minimax criterion,
%(against
%constant rebalancing schemes)
portfolio selection is not essentially any harder (than prediction)
as shown in \cite{CoverO96} (see also \citeR{Lugosi01}, Thm. 20 \& 21). But
%whereas the class of optimal constant rebalancing schemes
%provides a very interesting benchmark and motivation for portfolio selection,
there seems to be a qualitative difference between the practical utility of
``universal'' sequence prediction and ``universal'' portfolio selection.
Simply stated,
universal sequence prediction algorithms under various probabilistic
and worst-case
models appear to work very well in practice whereas the known universal portfolio selection
algorithms do not seem to provide any substantial benefit over a naive investment
strategy (see Section~\ref{sec:experimental}).


%(see Feder {\it et al} \cite{FederG92})
%(as we  will see)
%(as well as expert learning algorithms such as EG)


%Can a computer program predict the stock market? Judging by the
%overwhelmingly
%extensive but inconclusive work done in financial
%forecasting, perhaps this is not the most beneficial question to ask.

A major pragmatic question is whether or not a computer program can  consistently
outperform the market. A closer inspection of the interesting ideas developed in
information theory
%, theoretical computer science
and online learning suggests that a promising approach is to exploit the natural
volatility in the market and in particular to benefit from simple and rather
persistent statistical relations between stocks rather than to try to predict stock
prices or ``winners''.
% or
%even trends but rather to exploit the natural volatility in the
%market and in particular to benefit from simple and rather
%persistent statistical relations between stocks.
We present a non-universal portfolio selection algorithm\footnote{Any PS algorithm
can be modified to be universal by investing any fixed fraction of the initial
wealth in a universal algorithm.}, which does not try to predict winners.
%algorithm based on this approach that exploits anti-correlations
%between all stock pairs in the market.
The motivation behind our algorithm is the rationale behind \emph{constant
rebalancing} algorithms and the worst case study of universal trading
introduced by \citeA{Cover91}. Not only does our proposed algorithm substantially ``beat the
market'' on historical markets, it also beats the best stock. So why are we
presenting this algorithm and not just simply making money?  There are, of course
some caveats and obstacles to utilizing the algorithm. But for large investors the
possibility of a goose laying silver (if not golden) eggs is not
perhaps impossible.

%For each trading period (e.g. a minute, a day, a
%month, etc.)
%\rnote{This issue of a trading period may sound
%confusing: is it a minute or a day? We should rephrase this and
%maybe hint that we are looking at algorithms which can be operated
%any time (each time we input the current market we receive a
%recommended portfolio). In this sense the decision on how
%frequently to operate these algorithms is another parameter, which
%we don't deal with. (It would be good to consider a new type of
%algorithms which monitor the market online and decide to trade
%whenever it is beneficial.) In any case, here is a suggested
%simplified wording:}

\section{The Portfolio Selection Problem}
\label{sec:PS}

Assume a market with $m$ stocks.
% and daily
%``frictionless'' trading
%securities. The securities can be stocks, bonds, currencies,
%commodities, etc. (throughout
%the paper these securities are called ``stocks''.)
%\footnote{This is our first and main
%caveat; namely, we are greatly simplifying the nature of the market by
%assuming that we can
%purchase and sell stocks at the closing price without any transaction costs.}
%at the closing of the
%market.
%\footnote{Here (and this is our first and perhaps main
%caveat), we are greatly simplifying the nature of the market and
%assuming that our strategies can
%purchase and sell stocks at the closing price.}
%using $x_{i+1,j}$ is the ratio of
%opening price on the $i+1^{st}$ day to the opening price on the $i^{th}$ day.
%That is, we are assuming that a trader can buy or sell at the opening price.
%One can compensate for this by incorporating bid-ask spreads
%into transaction costs.}
Let $\vvv_t = (v_{t}(1), \ldots, v_{t}(m))$ be the daily closing
prices\footnote{There is nothing special about ``daily
closing prices'' and the problem can be defined with respect to
any (sub)sequence of the (intra-day) sequence of all price offers
which appear in the stock market.}
of the $m$ stocks for the $t^{th}$ day,
where $v_{t}(j)$ is the price of the $j$th stock.
%given in the ``local'' currency, called
%here {\em cash} or {\em dollars}.
It is convenient to work with {\em relative prices} $x_t(j) = v_t(j) / v_{t-1}(j)$
so that an investment of \$$d$ in the $j$th stock just before the $t^{th}$
day yields
%$\frac{d}{v_{t-1}(j)} \cdot v_t(j) =
$d x_t(j)$ dollars. We let $\xxx_t = (x_t(1),\ldots, x_t(m))$  denote the {\em
market vector} of relative prices corresponding to the $t^{th}$ day.
%\mnote{Isn't $x_{0,j} = 1$?  VG
%We have to say what is the range of $i$. I think we should have $I$ start at 1
%in which case $x_{1,j}$ is indeed 1. AB}
A {\em portfolio} $\bbb$ is an allocation of wealth in the stocks, specified by the
proportions $\bbb = (b(1), \ldots, b(m))$ of current dollar wealth invested in each
of the stocks, where $b(j) \geq 0$ and $\sum_j b(j) = 1$. The \emph{daily return} of
a portfolio $\bbb$ w.r.t. a market vector $\xxx$ is $\bbb \cdot \xxx = \sum_j b(j)
x(j)$ and the (compound) {\em total return}, $\Ret_X(\bbb_1, \ldots, \bbb_n)$, of a
sequence of portfolios $\bbb_1, \ldots, \bbb_n$ w.r.t. a market sequence $X =
\xxx_1, \ldots, \xxx_n$ is $\prod_{t=1}^n \bbb_t \cdot \xxx_t$. A portfolio
selection algorithm ${\cal A}$ is any deterministic or
randomized rule for specifying a
sequence of portfolios and we let $\Ret_X({\cal A})$ denote
its total return for the market sequence $X$.

%\newenvironment{Theorem}[1]{\noindent%
%\begin{minipage}{\textwidth}{\bf {#1}}\sf }%
%{\rm\end{minipage}\par\medskip}


The simplest
%portfolio selection
strategy is to ``buy-and-hold'' stocks using some portfolio $\bbb$. We denote this
strategy by $\bah_{\bbb}$ and  let $\ubah$ denote the uniform buy-and-hold when
%(i.e $\ubah$ invests in the portfolio
$\bbb = (1/m, \ldots, 1/m)$.
%For simplicity
We say that a portfolio selection algorithm ``beats the market'' when it outpeforms
$\ubah$ on a given market sequence although in practice ``the market'' can be
represented by some non-uniform $\bah$.\footnote{For example
the Dow Jones Industrial Average (DJIA) is calculated as a non uniform
average of the 30 DJIA stocks; see e.g. \texttt{http://www.dowjones.com/}}
Buy-and-hold strategies rely on
the tendency of successful markets to grow. Much of modern portfolio theory focuses
on how to choose a good $\bbb$ for the buy-and-hold strategy.
The seminal ideas of
\citeA{Markowitz59} yield an algorithmic procedure for choosing the
weights of the portfolio $\bbb$ so as to minimize the variance for any feasible
expected return. This variance minimization is possible by placing appropriate
(larger) weights on subsets of sufficiently anti-correlated stocks, an idea which we shall also
utilize.
%There are other approaches to investment that utilize
%the buy-and-hold approach. Notable examples are investors
%who attempt to predict the success of individual stocks
%and place non-zero weights in $\bbb$ only on such
%predicted winners.\footnote{There are some success stories of
%consistent ``stock picking'' by some investors such as Warren Buffet
%(see e.g. \cite{Hagstrom94}).}
%Denoting by $\bbb_{\UUU(m)}=(\frac{1}{m},\ldots,\frac{1}{m}$ the
%uniform portfolio over $m$ stocks,
%Note that buy-and-hold
%is most profitable in
%rising markets.
%Clearly, the return of any buy and hold portfolio is
%limited by the return of the best stock.
%its final return is limited by the return of the best stock.
We denote the optimal \emph{in hindsight} buy-and-hold strategy (i.e. invest only in
the best stock) by $\bah^*$.
%Clearly, $\bah^*$ invests all its money in the best stock.


%This mean-variance optimization method is
%due to Markowitz \cite{Markowitz59}.
An alternative approach to the static buy-and-hold is to dynamically change the
portfolio during the trading period. This approach is often called
%``dynamic asset allocation'' or
``active trading''.
%A notable motivation for such active portfolio selection
%is to take
%advantage of price fluctuations
%by attempting to implement the ideal
%(albeit usually unattainable)
%policy
%to ``buy low - sell high''.
%\footnote{
%In many markets, such as the foreign exchange, the trading period is not
%daily but is dynamically determined by new,
%around the clock events (i.e.\ price ``ticks'').}
%``Lucky'' active trading can lead to returns that dramatically outperform the
%performance of the best stock.
One example of active trading is {\em constant rebalancing};
%(also called ``constant mix'');
namely, fix a portfolio $\bbb$ and (re)invest your dollars {\it each day} according
to $\bbb$.
%On the next period,
%As stock prices change,
%the relative proportions of your investment deviate each day from the
%proportions specified by $\bbb$. Now sell and buy some stocks to
%rebalance your portfolio back to the $\bbb$ portfolio.
We denote this constant rebalancing strategy by $\cbal_{\bbb}$ and let  $\cbal^*$
denote the optimal (in hindsight) $\cbal$.
%$\cbal_\bbb$ having
%an associated fixed portfolio
%$\bbb = (b_1,\ldots,b_m)$ and operating as follows: at the beginning of
%each trading period make trades so as to rebalance the portfolio to
%$\bbb$ (that is, a fraction $b_j$ is invested in the $j$th stock,
%$i = 1,\ldots,m$) every day.
%As compared to any buy-and-hold strategy, a
A constant rebalancing strategy can often take advantage of market fluctuations to
achieve a return significantly greater than that of $\bah^*$.
% (the
%return of the best stock).
%\footnote{Clearly, the
%optimal (in hindsight) constant rebalancing strategy is always
%at least as good as the best stock.}
%It is easy to see that the return of
%$\cbalopt$ is bounded
%from below by the return of $\bahopt$ since every $\bah$ strategy can
%be thought of as a $\cbal$ algorithm.
%We let  $\cbal^*$ denote the optimal (in hindsight) $\cbal$.
$\cbal^*$ is always at least as good as the best stock $\bah^*$ and in some real
market sequences a constant rebalancing strategy will take advantage of market
fluctuations and
%to achieve a return significantly greater
%can
significantly outperform the best stock (see e.g. Table~\ref{tab:returns}).
%and~\ref{tab:risk_return}).
%For some markets this is true even in the presence of modest commission costs.
For now, consider \citeS{CoverG86} classic (but contrived) example
of a market consisting of cash and one stock and
%that constantly fluctuates so that
%its relative prices are
%$\frac{1}{2},2,\frac{1}{2},2,\ldots$.
%\footnote{A sequence of prices
%that give rise to such a sequence of relative price might be
%$20,10,20,10,\ldots$. \bnote{I still dont think we need to put this footnote in
%and I would remove it.}}
%That is,
the market sequence of price relatives
%we consider is
$\choose{1}{1/2}, \choose{1}{2}, \choose{1}{1/2}, \choose{1}{2}, \ldots$.
%(where the vector $\choose{1}{1/2}$ shows the daily relative prices for
%both the cash and the stock).
Now consider the $\cbal_{\bbb}$ with $\bbb = (\frac{1}{2}, \frac{1}{2})$. On each
odd day the daily return of $\cbal_{\bbb}$ is $\frac{1}{2}1+\frac{1}{2}\frac{1}{2} =
\frac{3}{4}$ and on each even day, it is $3/2$. The total return over $n$ days is
therefore $(9/8)^{n/2}$,
%$\left(\frac{3}{4}\frac{3}{2}\right)^{n/2}=(\frac{9}{8})^{n/2}$,
illustrating how a constant rebalancing strategy can yield exponential returns in a
``no-growth market''.
%A theoretical motivation for considering rebalancing algorithms
%is given in \cite{CoverT91}.
Under the assumption that the daily market vectors are observations of identically
and independently distributed (i.i.d) random variables, it is shown in
\cite{CoverT91} that $\cbal^*$ performs at least as good (in the sense of expected
total return) as the best online portfolio selection algorithm. However,
%one should keep in mind that
%despite a common assumption
%among many academicians,
%that markets satisfy the ``Random Walk Hypothesis'' \cite{Fama65}
many studies
%(e.g. \cite{LoMacKinlay88,Lo91,Ding93,Andersen98,LoMacKinlay01})
\cite<see e.g.>{LoMacKinlay01} argue that stock price sequences do have long term
memory and are not i.i.d.
%so that they
%markets are not i.i.d. and
%can have significant predictable components
%and are not i.i.d.

%there is yet another motivating reason  for considering
%$\cbal$ algorithms.
%One should keep in mind, however, that the

%\begin{theorem}[Cover and Thomas \cite{CoverT91}]
%\label{thm:cbal-iid}
%Let $X = \xxx_1, \ldots, \xxx_n$ be i.i.d. according to some
%distribution $F(\xxx)$.
%Then, for some $\bbb$, $\cbal_{\bbb}$ performs at least
%as good (in the sense of expected return) as the best
%online PS algorithm.
%\end{theorem}

%Theorem~\ref{thm:cbal-iid} tells us that it is sufficient
%to look for our best online algorithm in the set of $\cbal$
%algorithms, provided that the market is generated by an
%i.i.d. source.
%One should keep in mind, however, that the
%i.i.d. assumption is hard to justify. For alternative
%statistical market
%theories and  empirical evidence see  \cite{Green72,BollerslevCK92}.
%%\mnote{Can we find a ref for the comment that
%%i.i.d is not justifiable?}


%\begin{example}[Cover and Gluss~\cite{CoverG86}, Cover~\cite{Cover91}]
%\label{ex:cbal}
%Consider the case $m=2$ with one stock
%%\mnote{I am crediting both Cover and Gluss and Cover; i think
%it was Cover who first stated the bound given here but Cover
%%and Gluss who had the example first.}
%and cash. Consider the market sequence
%$$
%X = \choose{1}{1/2}, \choose{1}{2}, \choose{1}{1/2}, \choose{1}{2}, \ldots
%$$
%\begin{eqnarray*}
%\cbal_{(\frac{1}{2}, \frac{1}{2})}(X) &=&
        %\left[
                %\left( \frac{1}{2} \cdot (1 + \frac{1}{2}) \right)
                %\left( \frac{1}{2} \cdot (1 + 2) \right) \right]^{n/2}  \\
%&=& \left[\frac{3}{4} \cdot \frac{3}{2} \right]^{n/2} =
%\left(\frac{9}{8}\right)^{n/2}
 %\enspace .
%\end{eqnarray*}
%\end{example}

%Under the assumption that the daily market vectors are identically and
%independently distributed (i.i.d),
%there is yet another motivating reason  for considering
%$\cbal$ algorithms.
%

%\begin{theorem}[Cover and Thomas \cite{CoverT91}]
%\label{thm:cbal-iid}
%Let $X = \xxx_1, \ldots, \xxx_n$ be i.i.d. according to some
%distribution $F(\xxx)$.
%Then, for some $\bbb$, $\cbal_{\bbb}$ performs at least
%as good (in the sense of expected return) as the best
%online portfolio selection algorithm.
%\end{theorem}
%

%The first difficulty one comes across in trying to design and evaluate
%portfolio selection algorithms in a rigorous manner, is the choice
%of performance measure.
%In this paper we mainly focus on a {\em competitive analysis} framework
%whereby the performance of an online portfolio selection strategy
%is compared to that of a benchmark algorithm on every input.
%\mnote{Do we want to make the distinction between competitive and
%comparative analysis? VG I think the use of ``comparative'' below
%was a typo and I have replaced it by ``competitive''. AB}
%For example, for buy and hold
%strategies, a
%One reasonable (but still ambitious) offline benchmark is the return
%provided by the best stock. It is easy to see that a uniform
%distribution of funds achieves a ratio of $m$ and it is not
%hard to
%show that this is the best possible online stratgey from this perspective.
%For
%more active strategies, an optimal offline algorithm (that has complete
%%knowledge of the future) could provide returns so extreme that any
%reasonable approach is doomed when viewed in comparison.
%Specifically, it is not difficult to show
%in section~\ref{sec:lower} we prove, using a basic result of
%Ordentlich and Cover \cite{OrdentlichC96},
%that any online algorithm competing
%against the optimal offline algorithm,
%called $\opt$ is at best $m^n$-competitive
%where again $n$ is the number of trading days and $m$ is the number of stocks;
%that is, for any online portfolio selection algorithm, there is a (worst case) market sequence
%such that the ratio of the optimal
%offline return to the online return is $m^n$.

A non-traditional objective  (in computational finance)
%in studying portfolio selection
is to develop online trading strategies that are in some sense {\em always
guaranteed} to perform well.\footnote{A trading strategy is
\emph{online} if it computes the portfolio
for the $(t+1)^{st}$ day using only market information for
the first $t$ days. This is in contrast to \emph{offline}
algorithms such as $\ubah^*$, $\cbal^*$ and the optimal strategy of picking
the best stock for each individual day. Such offline algorithms
compute a sequence
of portfolios as a function of the entire market sequence.}
%In pursuing this approach in a rigorous manner
%a conceptual difficulty is the choice of performance measure.
Within a line of research pioneered by
Cover \shortcite{CoverG86,Cover91,CoverO96} one
attempts to design portfolio selection algorithms that can provably do well (in
terms of their total return) with respect to some online or offline benchmark
algorithms.
%algorithms, without
%statistical assumptions.
%Such benchmark algorithms can be either \emph{online}
%or \emph{offline}.
Two natural online
%\emph{online}
benchmark algorithms are the uniform buy and hold $\ubah$,
and the uniform constant rebalancing strategy $\SPLIT$, which is $\cbal_{\bbb}$ with
$\bbb=(\frac{1}{m},\ldots,\frac{1}{m})$.
%, denoted by $\SPLIT$.
A natural offline
%\emph{offline}
benchmark is $\bah^*$ and a more challenging offline
benchmark is $\cbal^*$.
%, which, for any particular market sequence
%chooses the optimal fixed portfolio $\bbb^*$ that maximizes the return
%of $\cbal_{\bbb}$.
%Note that offline algorithms such as $\bopt$ can only be computed
%in hindsight.


A portfolio selection algorithm ${\cal A}$ is called \emph{universal}
if {\it for every market sequence} $X$ over $n$ days, it
guarantees a subexponential ratio (in $n$) between its return
$\Ret_X({\cal A})$
and that of $\Ret_X(\cbal^*)$.
In particular,
Cover and Ordentlich's {\em Universal Portfolios}
algorithm \shortcite{Cover91,CoverO96},
denoted here by $\uni$, was proven to be universal; more specifically
%against $\cbal^*$, in the
{\it for every market sequence} $X$ of $m$ stocks over $n$ days, it
guarantees the subexponential (indeed polynomial) ratio
\begin{equation}
\label{eq:universal}
 \Ret_{X}(\cbal^*) / \Ret_{X}(\uni) = O\left( n^{\frac{m-1}{2}} \right).
\end{equation}
%where $\Ret_X(\alg)$ denotes the total return of algorithm
%$\alg$ with respect to the market $X$.
%\bnote{We have a small problem in that later we will use $\uni$
%to stand for the Dirichlet version.}
%(An improved algorithm proposed in \cite{CoverO96} achieves an
%optimal ratio proportional to $n^{\frac{m-1}{2}}$.)
From a theoretical perspective this is surprising as
this performance ratio is bounded by a polynomial in
$n$ (for fixed $m$) whereas $\cbal^*$ is capable of exponential returns.
From a practical perspective,
this bound is not very useful because the empirical returns
observed for $\cbal^*$ portfolios is often not exponential
in the number of trading days.
However, the
motivation that underlies the potential of $\cbal$ algorithms is useful!
We follow
this motivation and develop a new algorithm which we call $\anticor$. By attempting
to systematically follow the constant rebalancing philosophy, $\anticor$ is capable
of some extraordinary performance in the absence of transaction costs, or even with
very small transaction costs.
% but (in its simplest form)
%will go bankrupt in the presence of moderate transaction costs.

\section{Trying to Learn the Winners}
\label{sec:winners}

The most direct approach to expert learning and portfolio
selection
 is a ``(reward based)
weighted average prediction'' scheme, which adaptively computes a weighted average
of experts by gradually increasing (by some multiplicative or additive update rule)
the relative weights of the more successful experts.
In this section we briefly discuss some related portfolio selection
results along these lines.

%(and/or decreasing the weights of less successful
%experts).
For example, in the context of the PS problem consider the
%The second algorithm is the  efficient
``exponentiated gradient'' $\EG(\eta)$ algorithm proposed
by \shortcite{HelmboldSSW96}.
%The algorithm was developed in an online
%regression framework where the motivation is to
%work well with regard to the best weighted
%combination of stocks.
%Every weighted combination is a portfolio.
The $\EG(\eta)$ algorithm computes the next portfolio to be
$$
\bbb_{t+1}(j) = \frac {\bbb_t(j)\exp\left\{\eta \xxx_t(j)/(\bbb_t \cdot
\xxx_t)\right\}} {\sum_{j=1}^{m} \bbb_t(j) \exp \left\{\eta \xxx_t(j)/(\bbb_t \cdot
\xxx_t)\right\}},
$$
where $\eta$ is a ``learning rate'' parameter.
%by using an update
%function that maximizes an objective function of the form
%$$
%F^t(\bbb_{i+1}) = \eta\log{(\bbb_{i+1}\cdot \xxx_i)} - d(\bbb_{i+1},\bbb_i)
%where $d(\bbb,\bbb')$ is some distance
%measure over distributions
%\mnote{I think we are overusing the symbol `d' as above we used
%it for a distribution.I chnaged the usage as a distribution to "cal D".}
%(portfolios) and $\eta$ is a
%``learning rate parameter''.
$\EG$ was designed to greedily choose the best portfolio for yesterday's market
$\xxx_t$ while at the same time paying a penalty from moving far from yesterday's
portfolio. For a universal bound on $\EG$, Helmbold {\it et al.} set
%is  requires
%the value of $\eta$ to be
%quite small;  in particular, for the proof
$\eta=2 x_{\min} \sqrt{2 (\log m)/n}$ where $x_{\min}$ is a lower bound on any price
relative.\footnote{Helmbold {\it et al.} show how to eliminate the need to know
$x_{\min}$ and $n$. While $\EG$ can be made universal, its performance ratio is only
sub-exponential (and not polynomial) in $n$.}
% but it is
%easier to implement than $\uni$.}.
%on price relatives as well as how to apply a standard
%doubling trick so as to derive an algorithm that does not assume a known
%$n$.}.
%\mnote{I changed the wording here about EG hoping it is a little "softer".}
%question whether or not any significant amount of learning is
%taking place.
%would have a hard time
%saying that any learning is going on.
It is easy to see that as $n$ increases, $\eta$ decreases to $0$ so that we can
think of $\eta$ as being very small in order to achieve universality.
When $\eta =
0$, the algorithm $\EG(\eta)$ degenerates to the uniform $\cbal$
(assuming we started with a uniform portfolio)
%_{\frac{1}{m}, \ldots, \frac{1}{m}}$
which is not a universal algorithm.
%Nevertheless,
%the small learning rate (as given by their proof) of
%to make
%it universal.
It is also the case
%\rnote{This is true for many algs}
%\bnote{One might say that the natural degeneration in such a market should be
%$\ubah$ and not $\SPLIT$. But even if many algs degenerate this way
%it seemed necessary to say that $\EG$ would become $\SPLIT$.}
that if each day the price relatives for all stocks were identical, then $\EG$ (as
well as other PS algorithms) will converge to the uniform $\cbal$. Combining a small
learning rate with a ``reasonably balanced'' market
%(i.e.\ the
%price relatives are not too erratic),
we expect the performance of $\EG$ to be similar to that of the uniform $\cbal$ and
this is confirmed by our experiments (see
Table~\ref{tab:returns}).\footnote{Following Helmbold {\it et al.} we fix $\eta =
0.01$ in our experiments.
Additional experiments, for
a wide range of fixed $\eta$ settings, confirm
that for our datasets the choice of $\eta = 0.01$ is an optimal
or near optimal choice.
Of course, it is possible to adaptively set
$\eta$ throughout the trading period, but that is beyond the scope of this
paper.}
%is also competitive
%\bnote{We never really define competitive.} with respect to the optimal
%offline constant rebalancing algorithm but the performance guarantee
%but the guarantee in this case is only
%sub-exponential in $n$.
%When $\eta = 0$, the algorithm $\EG(\eta)$ degenerates to the uniform
%$\cbal_{\frac{1}{m}, \ldots, \frac{1}{m}}$ which is not a universal
%algorithm. It is easy to see that as $n$ increases,
%$\eta$ decreases to $0$ so that we can think of
%$\eta$ as being very small in
%order to achieve universality.
%Nevertheless,
%the small learning rate (as given by their proof) of $\EG$ is sufficient
%to make
%it universal. It is also the case
%that if each day the price relatives for all stocks were identical,
%then (as one would expect) $\EG$ will again be identical to
%the uniform $\cbal$.
%When one
%combines a small learning rate with a ``reasonably stable'' market (i.e.\ the
%price ratives are not too erratic), we might expect the
%performance of $\EG$ to be similar to that of the uniform $\cbal$
%and this seems to be confirmed by our experiments.
%%However, $\EG$ is much simpler to implement.
%Following Helmbold {\it et al}
%we first fix $\eta = 0.1$ in our experiments.

Cover's universal algorithms
%can also be expressed
%as algorithms that
adaptively learn each day's portfolio by increasing the weights of successful
$\cbal$s. The update rule for these universal algorithms is
%To generate $\bbb_{t+1}$, the portfolio for the $(i+1)^{st}$ day
%this algorithm computes
%a weighted average of all
%possible portfolios
$$
\bbb_{t+1} = \frac{\int \bbb \cdot \Ret_{t}(\cbal_{\bbb}) d\mu(\bbb)} {\int
\Ret_{t}(\cbal_{\bbb}) d\mu(\bbb)},\
$$
where $\mu(\cdot)$ is some prior distribution over portfolios. Thus, the weight of a
possible portfolio is proportional to its total return $\Ret_t(\bbb)$ thus far times
its prior. The particular universal algorithm we consider in our experiments uses
the Dirichlet prior (with parameters $(\frac{1}{2},\ldots,\frac{1}{2})$)
\cite{CoverO96}.\footnote{The
papers \shortcite{Cover91,CoverO96,BlumK98} consider
a simpler version of this algorithm where the (Dirichlet)
prior is uniform. This algorithm is also universal and achieves
a ratio $\Theta(n^{m-1})$.
Experimentally (on our
datasets) there is a negligible difference between these two variants
and here we only report on the results of the asymptotically
optimal algorithm.}
%in \cite{Cover91} and the above Dirichlet universal algorithm.}
%Within a contsant factor, this algorithm attains the optimal ratio
%(\ref{eq:universal}) with respect to $\cbal^*$.
%, the offline constant rebalancing benchmark.
%This algorithm attains the best known theoretical worst case bound
%with respect to the optimal offline constant rebalancing benchmark algorithm.
%The proof of universality also shows that
Somewhat surprisingly, as noted in \shortcite{CoverO96}
the algorithm is equivalent to a static weighted average
(given by $\mu(\bbb)$)
over all $\cbal$s \cite<see also>[p. 291]{BorodinE98}.
This equivalence helps to demystify the universality result and also
shows that the algorithm can never outperform $\cbal^*$.

%In addition, our limited
%empirical results of this algorithm showed that
%it does indeed perform like the uniform $\cbal_{(1/m,\ldots,1/m)}$.
%\mnote{We should be gentle here.
%I agree that we have to say this carefully.
%I added the qualifier `limited' and maybe
%we can soften in a bit more but
%the truth is the truth. AB
%Actually thetruth is that it performs like the unifrom cbal.}
%\mnote{Vincent: this is Not true for $m>2$? }
%\mnote{It is also true for all 36 stocks [vincent].
%Then we have to say so. AB}
%for any pair of stocks (respectively, for the
%entire set of 36 stocks),
%it performed approximately like  the uniform $\cbal_{(1/m,\ldots,1/m)}$.
%An interesting point to make about the $\EG$ algorithm is with respect to
%its heritage and with respect to how $\bopt$ makes money relative to
%the buy and hold strategy.
%The $\EG$ algorithm was developed in an online
%regression framework. Its motivation is to
%work as well as the best weighted
%combination of experts, which in our case are stocks. Every
%such combination is a portfolio.
%When
%trying to select the best weighting of experts, the
%$\EG$ algorithm is well motivated. It is trying to
%minimize a loss function
%based on the weighting of various expert opinions.
%It is very
%difficult, however, to see how to map this problem to the one of
%portfolio selection. The concept of best stock and best expert do not
%directly map.   WHY ??????
%However, it is apparent that $\bopt$ does not make its money (over
%buy and hold) by seeking out the best stock. Instead, it chooses a
%portfolio that actively takes advantage of the ups and downs of the
%stock prices. If one is maintaining a {\em constant portfolio},
%one is selling
%rising stocks and buying falling ones. This strategy is
%advantageous when the
%falling stock reverses its trend and starts rising. As it rises, value
%will be created by selling at a higher price.
%\mnote{I changed the wording here about EG hoping it is a little "softer".}
%question whether or not any significant amount of learning is
%taking place.
%would have a hard time
%saying that any learning is going on.
%When $\eta = 0$, the algorithm $\EG(\eta)$ degenerates to the uniform
%$\cbal_{\frac{1}{m}, \ldots, \frac{1}{m}}$ which is not a universal
%algorithm. It is easy to see that as $n$ increases,
%$\eta$ decreases to $0$ so that we can think of
%$\eta$ as being very small in
%order to achieve universality. Nevertheless,
%the small learning rate (as given by their proof) of $\EG$ is sufficient
%to make
%it universal. It is also the case
%that if each day the price relatives for all stocks were identical,
%then (as one would expect) $\EG$ will again be identical to
%the uniform $\cbal$. When one
%combines a small learning rate with a ``reasonably stable'' market (i.e.\ the
%price ratives are not too erratic), we might expect the
%performance of $\EG$ to be similar to that of the uniform $\cbal$
%and this seems to be confirmed by our experiments.

A different type of ``winner learning'' algorithm can be obtained from any
%The third algorithm \cite{BorodinEG00} attempts to predict the
%The third algorithm we describe
%\cite{BorodinEG00}
sequence prediction strategy, as noted in \cite{BorodinEG00}.
%On each day the algorithm
%attempts to predict the
%best stocks for the next day.
For each stock $j$, a (soft) sequence prediction algorithm provides a probability $p(j)$
that the next symbol will be $j \in \{1, \ldots, m\}$. We view this as a prediction
that stock $j$ will have the best relative price for the next day and set
$\bbb_{t+1}(j) = p_j$.
The paper \shortcite{BorodinEG00}
considers predictions made using the prediction component
of the well-known Lempel-Ziv ($\LZ$) lossless compression algorithm
\cite{LempelZ78}. This prediction component is nicely described in
\cite{Langdon83} and in \cite{Feder91}. As a prediction algorithm,
$\LZ$ is provably powerful in various senses. First it can be shown that it is
asymptotically optimal with respect to any stationary and ergodic finite order
Markov source \cite{Rissanen83,LempelZ78}.
Moreover, Feder shows that $\LZ$ is also
universal in a worst case sense with respect to the (offline) benchmark class of all
finite state prediction machines.
%However, it is easy to show (see \cite{BorodinEG00}) that $\LZ$
%as a PS algorithm is not universal.
%As  we will see, the LZ portfolio selection is able to consistently
%beat the market
%(with the exception of the TSE) and  can sometime beat the uniform $\cbal$
%\footnote{In a currency exchange market reported in \cite{BorodinEG00},
%LZ is able to beat $\cbal^*$.}.
To summarize, the common approach to devising PS algorithms has been to attempt and
learn winners using simple or more sophisticated winner learning schemes.

%\rnote{We could mention that in EG the experts (or winners that we try to
%predict) are stocks. In ``Universal'' the winners sought are portfolios and
%in the LZ, these are stocks again.}
%\bnote{I think this might confuse the issue and would suggest
%we dont try to make this distinction.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Anticor Algorithm}
\label{sec:anticor}




%Given that the above learning algorithms do not consistently beat
%the market in our experimental trials,
We propose a different approach,
motivated by a $\cbal$-inspired ``philosophy''.
%We return
%to the underlying motivation for the potential of $\cbal$s.
% to produce large
%returns.
How can we
%There are a number of ways
%\rnote{What are these number of ways (i.e. it seems we give
%one interpretation)}
%we can
%
interpret
%and abstract
the success of
%$\cbal_{(1/2,1/2)}$
the uniform $\cbal$ on the Cover and Gluss example of Section~\ref{sec:PS}?
Clearly,
the uniform $\cbal$ here is taking advantage of price fluctuation by constantly
transferring wealth from the high performing stock to the
relatively
%\bnote{Here i removed anti-correlated as we may not insist that
%there be an anticorrelation; in the next sentence we say that
%this should be part of the decision.}
%anti-correlated
low
performing stock.
Even in a less contrived market, a $\cbal$ is capable of large returns.
A market model favoring the use of a $\cbal$ is one in which
stock growth rates are stable in the long term and
occasional larger return rates will be followed
by smaller rates (and vice versa). This market phenomenon is
is sometimes called ``reversal to the mean''.


There are many ways that one can interpret and implement
algorithms based on the philosophy of
``reversal to the mean''.
In particular, any $\cbal$ can be viewed as a static implementation of this philosophy.
We now describe the motivation and basic ingredients in our $\anticor$ algorithm
which adaptively (based on recent empirical statistics) and rather
aggressively\footnote{Our $\anticor$ algorithm is aggressive
(say, compared to $\cbal$)
in the sense that it can transfer all assets out of a given stock.
Various heuristics can be used to moderate this behavior.}
implements ``reversal to the mean''.

For a given trading day,
consider the most recent past $w$ trading days, where $w$
is some integer parameter.
The growth rate of any stock $i$ during this \emph{window} of time
is measured by the product of relative prices
during this window.\footnote{Since we would rather
deal with arithmetic instead of geometric means
we will use the logarithms of relative prices.}
Motivated by the assumption that
we have a portfolio of stocks that are all performing similarly in
terms of long term growth rates, $\anticor$'s first
condition for transferring money from
stock $i$ to stock $j$ is that
the growth rate for stock $i$ exceeds that of stock $j$
in this most recent window of time.\footnote{Note that here the umderlying
model assumption is reversal to the \emph{same} mean. One can modify the algorithm
so as to account for different means.}
In addition, the $\anticor$ algorithm requires some indication that stock
$j$ will start to emulate the past growth of stock $i$
in the near future.  To this end, $\anticor$ requires a positive
correlation between stock $i$ during the second last window
and stock $j$ during the last window.
The relative extent to which we will transfer money from stock $i$
to stock $j$ will depend on the strength of this correlation as well
as the strength of the ``self anti-correlations'' for stocks $i$ and $j$
(again in two consecutive windows).
$\anticor$ is so named because we use these correlations and anticorrelations
in consecutive windows to indicate the potential for anticorrelations
of the growth rates for stocks $i$ and $j$ in the near future
(with hopefully the growth rate of stock $j$ becoming greater than that of
stock $i$).


%we should be able to take
%advantage when a stock is currently outperforming
%other stocks especially if this
%strong performance is \emph{anti-correlated} with the
%performance of these other stocks.
%Our $\anticor_w$ algorithm
%%\footnote{The $\anticor_w$ algorithm is a substantial refinement of
%%our previous algorithm $DELTA$ described in \cite{BorodinEG00}.}
%%attempts to aggressively exploit such a scenario
%%in the following way.
%%The algorithm
%considers a short market history (consisting of two consecutive ``windows'', each of
%$w$ trading days) so as to model statistical relations between each pair of stocks.
%%The algorithm updates the model every trading
%%day. Using this model we define a condition as to whether or not a stock
%%$j$ has any ``claim'' on stock $i$. The extent of each such claim is
%%computed and then a  redistribution of the portfolio takes place.
%%Precisely, let $w>1$ be any integer and
%%Let $X = \xxx_1,\ldots,\xxx_t$ be a
%%market sequence with $t\geq 2w$, where
%%$\xxx_i = (x_{i1},\ldots,x_{im})$ is a market vector of relative prices.
%%Let $\bbb_t = (b_{t1},\ldots,b_{tm})$ be the last portfolio
%%corresponding to day $t$.
%%Algorithm $\anticor_w$ computes the next portfolio
%%$\bbb_{t+1}$ as follows.
Formally, we define
\begin{eqnarray}
\label{eq:LX}
\LX_1 = \log(\xxx_{t-2w+1}),\ldots,\log(\xxx_{t-w})^T \mbox{\ \ and \ \ } \LX_2 =
\log(\xxx_{t-w+1}),\ldots,\log(\xxx_{t})^T,
\end{eqnarray}
where $\log(\xxx_k)$ denotes $(\log(x_{k}(1)),\ldots,\log(x_{k}(m)))$.
%\bnote{Do we need a transpose for the previous vector?}
Thus, $\LX_1$ and $\LX_2$ are the two vector sequences (equivalently, two $w \times
m$ matrices) constructed by taking the logarithm over the market subsequences
%(of relative price vectors)
corresponding to the time windows $[t-2w+1,t-w]$ and $[t-w+1,t]$, respectively.
%Viewing $\LX_k$, $k=1,2$, as $w \times m$ matrices,
We denote the $j$th column of $\LX_k$ by $\LX_k(j)$. Let
$\mu_k=(\mu_k(1),\ldots,\mu_k(m))$,
%$k=1,2$,
be the vectors of averages of columns of $\LX_k$.
%(that is, $\mu_k(j) =
%E\{LX_k(j)\}$).
%\bnote{Do we want to remove the comment that this is the
%expectation of the log relatives given the distinction between the
%expectation and the empirical average. In an case we need to fix the
%def of $M_{cov}$ by dividing by $w$ or $w-1$ which ever we do.}
Similarly, let $\sigma_k$,
%%$k=1,2$
be the vector of standard deviations of columns of $\LX_k$.
%Define $M_{cov}$ to be
The cross-correlation matrix (and its normalization) between column vectors in
$\LX_1$ and $\LX_2$ are defined as\footnote{Recall that the
{\em correlation coefficient} is a normalized covariance
with the covariance divided by the product of the standard
deviations; that is, $Cor(X,Y) = Cov(X,Y)/(std(X)*std(Y))$ where
                $Cov(X,Y) = E[(X-mean(X))(Y-mean(Y))]$.}
\begin{align}
M_{cov}(i,j) &= \frac{1}{w-1}(\LX_1(i)-\mu_1(i))^T(\LX_2(j)-\mu_2(j)); \nonumber\\
M_{cor}(i,j) &= \left\{
\begin{array}{ll}
    \frac{M_{cov}(i,j)}{\sigma_1(i) \sigma_2(j)} &
                \hbox{$\sigma_1(i),\sigma_2(j)\neq 0$;} \\
    0 & \hbox{otherwise.} \label{eq:m_cor} \\
\end{array}%
\right.
\end{align}
$M_{cor}(i,j) \in [-1,1]$ measures the correlation between log-relative prices of
stock $i$ over the first window and stock
%the log-relative prices of stock
$j$ over the second window.
%We use $\mu_2$ and $M_{cor}(i,j)$ to determine the redistribution
%of our investment as follows.
We note that if
$\sigma_1(i)$ (respectively, $\sigma_2(j)$) is zero
over some window then the growth rate of stock $i$ during the second
last window (respectively, stock $j$ during the last window)
is constant during this window. For sufficiently large windows of time
constant growth of any stock $i$ is unlikely.
However, in this unlikely case we choose not
to move money into or out of such a stock $i$.\footnote{Of course, other
approaches can be used to accommodate constant or nearly constant
growth rate.}



For each pair of stocks $i$ and $j$ we compute
%attempt to measure
$\claim_{i \to j}$, the extent to which we want to shift our investment from stock
$i$ to stock $j$.
% using the ``philosophy'' of $\cbal$.
Namely,  there is such a $\claim$ iff $\mu_2(i) > \mu_2(j)$ and $M_{cor}(i,j) > 0$
in which case $\claim_{i \to j} = M_{cor}(i,j) + A(i) + A(j)$ where $A(h) =
|M_{cor}(h,h)| $ if $M_{cor}(h,h) < 0$, else 0.
Following our interpretation for the
success of a $\cbal$, $M_{cor}(i,j) > 0$ is used to predict that stocks $i$ and $j$
will be correlated in consecutive windows (i.e. the current window and the next
window based on the evidence for the last two windows) and $M_{cor}(h,h) <0$
predicts that stock $h$ will be
negatively auto-correlated over consecutive
windows.
%The $\cbal$ philosophy suggests that we may want to
%move wealth invested in stock $i$ to stock $j$
%if the relative price of stock $i$ is larger than that
%of stock $j$. Taking a more stable estimate of relative
%prices using averages computed over the last window this condition is estimated
%by the condition $\mu_2(i) > \mu_2(j)$.
%However we only apply this condition if $M_{cor}(i,j)>0$.
%which means that stock $i$ is positively correlated with $j$
%over the last consecutive windows.
%We use this second condition as
%a proxy for a prediction that these stocks will be positively correlated
%over the next two windows (i.e. the last window of $w$ days
%followed by the future window of $w$ days). These two conditions
%together predict that stock $j$'s relative price will rise and we first set
%$\claim_{i \to j} = M_{cor}(i,j)$.
%In addition, if we have further evidence that either stock
%$i$ or stock $j$ tend to be anti-cross-correlated with itself over
%consecutive windows, we increase the ``claim'' $j$ has on $i$ accordingly.
%In particular, if $M_{cor}(i,i) <0$ then we add  $|M_{cor}(i,i)|$
%to $\claim_{i \to j}$ and if $M_{cor}(j,j) <0$ then
%we also add $|M_{cor}(j,j)|$ to $\claim_{i \to j}$.
%The rationale is that (self) anti-correlations of stocks $i$
%and $j$ serve as predictions that the relative prices of these stocks
%will ``oscillate''.
%Once $\claim_{i \to j}$ is computed for all $i \neq j$
Finally, $\bbb_{t+1}(i)  = \bbb_t(i) + \sum_{j \neq i}[ \transfer_{j \to i} -
\transfer_{i \to j}$] where
%follows. We start with the last portfolio
%and set $\bbb_{t+1}=\bbb_t$. Then,
%for all $i \neq j$,
$\transfer_{i \to j} = \bbb_t(i) \cdot \claim_{i \to j}/\sum_j \claim_{i \to j}$.
%and finally add $\transfer_{j \to i} - \transfer_{i \to j}$ to
%$\bbb_{t+1}(i)$.
% (the $i$th component of $\bbb_{t+1}$).
A pseudocode summarizing the $\anticor$ algorithm
appears in Figure~\ref{fig:anticor}. The pseudocode describes
the routine $\anticor(w,t,X_t,\hat{\bbb}_t)$ that receives
a window size $w$, the current trading day $t$, the historical
market sequence $X_t$ (giving the market vectors corresponding to days
$1,\ldots,t$) and the current portfolio
$\hat{\bbb}_t$
defined to be
$\hat{\bbb}_t = \frac{1}{\bbb_t \cdot \xxx_t}(\bbb_t(1)
\xxx_t(1),\ldots,\bbb_t(m) \xxx_t(m))$.
The routine is first called with an
empty historical market sequence and with $\hat{\bbb}_t$ being the
uniform portfolio (over $m$ stocks). The routine returns
the new portfolio, to which we should rebalance at the start of the
$(t+1)^{st}$ trading day.
\begin{figure}[htb!]
\fbox{
\begin{minipage}{0.9\columnwidth}
{\footnotesize
\begin{center}
Algoritm \DELTA($w,t,X_t,\hat{\bbb}_t$)\\
\end{center}
\textbf{Input:}
\begin{enumerate}
    \item
    $w$: Window size
    \item
    $t$: Index of last trading day
    \item
    $X_t = \xxx_1,\ldots,\xxx_t$: Historical market sequence
    \item
    $\hat{\bbb}_t$: current portfolio (by the end of trading day $t$)
\end{enumerate}
\textbf{Output:}
$\bbb_{t+1}$:  Next day's portfolio
\begin{enumerate}
\item Return the current portfolio $\hat{b}_t$ if $t<2w$.
\item Compute $\LX_1$ and $\LX_2$
as defined in Equation (\ref{eq:LX}),
and $\mu_1$ and $\mu_2$, the (vector) averages of $\LX_1$ and $\LX_2$,
respectively.
\item Compute $M_{cor}(i,j)$ as defined in Equation (\ref{eq:m_cor}).
\item Calculate claims: for $1\leq i,j\leq m$, initialize
$\claim_{i\to j} = 0$
\item
If $\mu_2(i) \geq \mu_2(j)$ and $M_{cor}(i,j)>0$ then
    \begin{enumerate}
    \item
    %if $M_{cor}(i,j) > 0$ then
    $\claim_{i \to j} = \claim_{i \to j} + M_{cor}(i,j)$;
    \item
    if $M_{cor}(i,i) <0$ then
        $\claim_{i \to j} = \claim_{i \to j} - M_{cor}(i,i)$;
    \item
    if $M_{cor}(j,j) <0$ then
        $\claim_{i \to j} = \claim_{i \to j} - M_{cor}(j,j)$;
    \end{enumerate}
%\end{enumerate}

\item
Calculate new portfolio:
Initialize $\bbb^{t+1} = \hat{\bbb}^t$. For $1 \leq i,j \leq m$
    \begin{enumerate}
    \item
    Let $\transfer_{i \to j} = \bbb^t_i \cdot \claim_{i \to j}/\sum_j \claim_{i \to _j}$;
    \item
    $\bbb^{t+1}_i = \bbb^{t+1}_i - \transfer_{i \to j}$;
    \item
    $\bbb^{t+1}_i = \bbb^{t+1}_i + \transfer_{j \to i}$;
    \end{enumerate}
\end{enumerate}
}
\end{minipage}
}
\caption{Algorithm $\anticor$}
\label{fig:anticor}
\end{figure}


\begin{figure}[h]
\begin{center}
\begin{tabular}{cc}
        \epsfig{file=eps/window_anticor30_NYSE.eps,width=2.3in} &
        \epsfig{file=eps/window_anticor30_TSX.eps,width=2.3in} \\
        (a) & (b)\\
        \epsfig{file=eps/window_anticor30_SP_5.eps,width=2.3in} &
        \epsfig{file=eps/window_anticor30_DJIA.eps,width=2.3in} \\
       (c) & (d)
\end{tabular}
\end{center}
\caption{\label{fig:return_vs_window} $\anticor_w$'s total return (per \$1
investment) vs. window size $2\leq w \leq 30$ for
(a) NYSE; (b) TSX; (c) SP500; (d) DJIA.
The dashed (red) lines represent the final return of the best stock
and the dash-dotted (blue)
lines, the final return the (uniform) market.
The dotted (green) horizontal lines represent a uniform investment on a number
of $\anticor_w$ applications as later described.}
%In (c) the dash-dotted line depicts the return of the entire DJA index.
%Note that market return in figure (a) is too small to be
%clearly seen (it is 14.49).}
\end{figure}

Our $\anticor_w$ algorithm
%can handle any number $m$ of stocks
has one critical parameter, the window size $w$. In
Figure~\ref{fig:return_vs_window} we depict the total return of $\anticor_w$ on two
historical datasets as a function of the window size $w=2,\ldots,30$
(detailed descriptions of these datasets appear
in Section~\ref{sec:experimental}).
%For example,
%Figure~\ref{fig:return_vs_window}(a) considers
%a 22-year New York Stock Exchange dataset
%(see details below)
%and
%specifies (in log-scale) the total returns (per \$1 investment)
%of $\anticor_w$ for $w=2,\ldots,30$.
%The green horizontal line species the return of the best stock
%in that period and the blue line represents the market.
As we might expect, the performance of $\anticor_w$ depends significantly on the
window size. However, for all $w$, $\anticor_w$ beats the uniform market
%(blue horizontal line)
and, moreover, it beats the best stock
%(red horizontal line)
using most window sizes. Of course, in online trading we cannot choose $w$ in
hindsight. Viewing the $\anticor_w$ algorithms as
%investment derivatives
experts, we can try to learn the best expert. But the windows, like individual
stocks,
%for direct
%to be able to directly exploit
%expert learning
%algorithms, different settings of the parameter may also
induce a rather volatile set of experts and standard expert combination algorithms
\shortcite{CesaBianchiFHHSW97} tend to fail.\footnote{This assertion
is based on empirical studies we conducted with
various
%standard
%and more sophisticated
`expert advice' algorithms.}

Alternatively, we can adaptively  learn and invest in some weighted average of all
$\anticor_w$ algorithms with $w$ less than some maximum $W$.
%\footnote{Here we arbitrarily fix $W = 30$; this choice is not in
%any way chosen to be optimal.
%There are many ways to eliminate the parameter $W$,
%which we do not pursue here as this parameter does not play a crucial role. See
%figure YYYY in HHHH.}
%The question is how to choose the weights.
%Without any prior (or acquired) knowledge,
The simplest case is a uniform investment on all the windows; that is,
%Viewed as an investment strategy, this uniform distribution
a uniform buy-and-hold investment on the algorithms $\anticor_w$, $w\in[2,W]$,
denoted by $\bah_W(\anticor)$.
Figure~\ref{fig:return_vs_max_window}
graphs the total
return of $\bah_W(\anticor)$ as a function of $W$ for all values
of $2 \leq W \leq 50$ for the four datasets we consider here.
Considering these graphs, our choice of  $W = 30$
was arbitrary but clearly not optimal.
Of course, we could try to optimize the parameter $W$
for each particular dataset by training the algorithm
on historical data before beginning
to trade. However, our claim is that almost any
choice of $W$ will yield returns that beat the best stock
(the only exception is $W=2$ in the DJIA dataset).
%\bnote{As you can see in the previous sentence I used some of
%your comments
%that follow to state our claim.}
%\rnote{Anything we should add here? We can view
%the algorithm as fixed with $W=30$. But clearly the alg has one parameter
%that one can optimize for each particular dataset. The straightforward
%approach would be to use some months/years of historical data, optimize
%the parameter and only then start trading. The main point here that
%(we claim that) any
%choice of sufficiently large $W$ should be good for generating great returns.}
%%in all cases
%%so there is room for further improvements, which are not pursued here.
%Indeed, for all $W \geq 3$,
%%the total returns
%%of
%$\bah_W(\anticor)$
%%are impressive and, in particular,
%beats the best stock in all our experiments.
%\bnote{We need to make sure that this is indeed true; that is
%that we beat the best stock in all the markets considered. It
%seems that we dont even have to worry about W being sufficiently large
%but I suspect that small W's could be problematic. I changed the
%word "however" in the sentence above to "Indeed"}
%

\begin{figure}[htb]
\begin{center}
\begin{tabular}{cc}
        \epsfig{file=eps/max_win_NYSE.eps,width=2.1in} &
        \epsfig{file=eps/max_win_TSX.eps,width=2.1in}\\
        (a) & (b)\\
       \epsfig{file=eps/max_win_SP500.eps,width=2.1in} &
        \epsfig{file=eps/max_win_DJIA.eps,width=2.1in}\\
        (c) & (d)\\
\end{tabular}
\end{center}
%\vspace{.5cm}
\caption{\label{fig:return_vs_max_window}
$\bah_W(\anticor)$'s total return (per
\$1 investment) as a function of the maximal window $W$:
NYSE (a); TSX (b); SP500 (c); DJIA (d).
}
\end{figure}

\begin{figure}[htb]
\begin{center}
%\begin{tabular}{cc}
 %       \epsfig{file=eps/nips_max_win_NYSE.eps,width=2.in} &
        \epsfig{file=eps/nips_anti-3.eps,width=3.2in}
%\end{tabular}
\end{center}
%\vspace{.5cm}
\caption{\label{fig:anti_3} Cumulative
returns for last month of the DJIA dataset: stocks (left panel); $\anticor_w$
algorithms trading the stocks (denoted $\anticor^1$, middle panel); $\anticor_w$
algorithms trading the $\anticor$ algorithms (right panel).}
\end{figure}





% (
%or more simply as $\bah(\anticor)$).
%when $W$ is clear from the context).
% and later consider its empirical performance.
%A potentially more rewarding approach
%would be to online learn (and dynamically change) our
%portfolio of $\anticor_w$ algorithms.
Since we now consider the various algorithms as stocks (whose prices are determined
by the cumulative returns of the algorithms), we are back to our original portfolio
selection problem and if the $\anticor$ algorithm performs well
on stocks it may
also perform well on algorithms.
We thus consider active investment in the various
$\anticor_w$ algorithms using $\anticor$. We again consider all windows $w \leq W$.
Of course, we can continue to compound the algorithm any number of times. Here we
compound twice and then use a buy-and-hold investment.
The resulting algorithm is
denoted $\bah_W(\anticor(\anticor))$.
%or more simply as $\bah(\anticor(\anticor))$.
One impact of this compounding, depicted in Figure~\ref{fig:anti_3}, is to
smooth out the anti-correlations exhibited in the stocks.
%\footnote{Similar
%figures for the other three data sets can be found at
%{http://www.cs.technion.ac.il/$\sim$rani/portfolios}}.
%Figure~\ref{fig:anti_3} depicts
%the effect of this compounding.
%\rnote{The three panels in this
%figure show the total returns of the stocks (left),
%of $\bah_{30}(\anticor)$ (middle) and
%of $\bah_{30}(\anticor(\anticor))$ (right).}
It is evident that after compounding twice the returns
%``experts''
%\rnote{(returns of the various algorithms)}
become almost completely correlated thus diminishing the possibility that additional
compounding
%using
%$\anticor$
will substantially help.\footnote{This smoothing effect also allows for the use of
simple prediction algorithms such as ``expert advice'' algorithms
\shortcite{CesaBianchiFHHSW97}, which
%while not that successful in
%predicting the best stock can
can now better predict a good window size. We have not explored this direction.}
This idea for smoothing critical parameters may be applicable in other learning
applications. The challenge is to understand the conditions and applications in
which the process of compounding algorithms will have this smoothing effect.


%Before continuing with the experimental results
%we note that the choice of $W$ is rather stable
%in the sense that large returns will be obtained
%using almost any (sufficiently large) value. Consider
%Figure~\ref{fig:return_max_win_NYSE}, which graphs
%the total return of $\bah_W(\anticor)$ as a function of
%$W$ for all values of $2 \leq W \leq 50$
%with respect to the NYSE (left) and DJIA (right) datasets (see details on
%these datasets in Section~\ref{sec:experimental}).
%Clearly, the choice $W = 30$ is not optimal
%in both cases (and in all other cases we considered) so there is room
%for further improvements, which are not pursued in the
%present work. However note that for all
%values of $W$ greater than, say 3, the total return
%of $\bah_W(\anticor)$ is very impressive (and in particular, beats the
%best stock; see also Tables~\ref{tab:returns} and~\ref{tab:risk_return}).
%
%%\begin{figure}[h]
%\begin{center}
%\begin{tabular}{cc}
        %\epsfig{file=eps/max_win_NYSE.eps,width=2in} &
        %\epsfig{file=eps/max_win_DJA.eps,width=2in}
%\end{tabular}
%\end{center}
%\vspace{.5cm}
%\caption{\label{fig:return_max_win_NYSE}
%$\bah(\anticor)$'s total return (per \$1 investment) as a function
%of the maximal window $W$.}
%\end{figure}



%Once again, we could use a standard learning algorithm (by viewing
%each window $w$ as an expert) to adaptively learn and set the window size.
%%Or we could simply apply a uniform buy and hold strategy to the
%%windows and invest in each window uniformly.
%However, our experimental results suggest that trying to
%learn the winners directly  or even trying to learn a parameter such
%as the window size $w$ does not seem to be a generally successful
%approach. But we do observe excellent return when we apply
%a buy and hold (over the window sizes) to our $\DELTA$ algorithm.
%And  now we can apply a standard computer science idea and
%further compose algorithms. That is, rather than viewing stocks
%as experts, lets view stocks as algorithms (i.e. as the extreme buy and hold of
%that stock). Then any set of
%portfolio selection algorithms can be composed together as we are doing when we
%apply buy and hold to $\DELTA$ which in turn is being
%applied to the extreme buy and hold algorithms. We will denote
%this algorithm as $\ubah(\DELTA)$.
%And if $\ubah(\DELTA)$
%is successful, why not try $\ubah(\DELTA(\DELTA))$?  The
%impact of this compounding is to smooth out the anti-correlations
%(see figure~\ref{XXX})
%and the results obtained (see figure~\ref{YYY}) are quite impressive.
%


%When
%no stock has a claim on any other stock, the
%algorithm acts as a buy and hold.
%In Sections~\ref{sec:experimental} and \ref{sec:commissions}








%step the algorithm parses the next phrase to be encoded,
%namely, the smallest
%subsequence (from the current point in the sequence)
%that does not yet appear in its dictionary.
%Clearly, this  subsequence
%is of the form $s,x$ where $s$ is a phrase in the dictionary and $x$ is a
%symbol. Then the algorithm encodes this new phrase.
%Suppose that the algorithm
%encodes $s$ by its position (say in binary) in the dictionary and then
%sends an encoding of the symbol $b$.
%The central result about this algorithm is that in a distributional setting
%%\mnote{I restated this slightly; is there a ref for this result?}
%the compression rate (bits per symbol)  is guaranteed to approach the
%optimal rate (the entropy of the source) for every stationary and ergodic
%source (see \cite{LempelZ78} and \cite{CoverT91}.


%Let us now
%describe the $\LZ$ prediction algorithm. In the binary case, this algorithm
%maintains at all times a binary tree (a ``trie'') that records the phrase
%dictionary and counters which hold statistics of the given input. The
%initial tree contains a root and two (left and right) leaves.  The left
%child of a node corresponds to a parsing of ``0'' and the right child
%corresponds to a parsing of ``1''.  Each node maintains a counter. The
%counter in a leaf is always set to 1. The counter in an internal node is
%always maintained so that it equals the sum of its right and left child
%counters.
%%At all times, the tree records the current dictionary as
%%the set of strings encoded by all the paths that start at the root.
%The algorithm computes in phases where in each phase the previously parsed
%prefix is processed. To process the next prefix that has just been
%parsed from the input, the algorithm starts traversing the tree starting
%from the root. At each node, the prediction for a zero is the zero (left)
%counter divided by the sum of zero and one-counters. When reaching a
%leaf
%%(which must happen because the parsed string contains a complete
%%path)
%the tree is enlarged by making this leaf an internal node and adding
%two leaf-sons to this new internal node. Then the counte
%
%




%Markov and LZ (``Lempel-Ziv'') algorithms are simple
%generalizations of successful
%sequence learning algorithms and $\EG$ (``exponential gradiant'')
%is  a standard learning algorithm. ($\EG$ and $\M$ each have one parameter
%which we set according to values used in previous studies).
%In another contrived
%market where one stock consistently wins (e.g. say doubles) every day
%and all other stocks decline or stay fixed, it is clear that $\DELTA$ would
%perform poorly whereas any algorithm that learns this one winning stock will
%do well. Clearly the historical markets do not behave in this manner. However,
%if one wants to hedge between the $\DELTA$ and ``winners'' strategies (or
%between any set of strategies), then
%one can apply a buy and hold to the various strategies or
%use an ``expert learning algorithm'' to adaptively balance
%the portfolio allocation by viewing each competing algorithm as an expert.
















%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{An Empirical Comparison of the Algorithms}
\label{sec:experimental}


We present an experimental study of the the $\anticor$ algorithm
%comparing
%its performance with
%various online and offline benchmarks
%as well as with
and the three online learning algorithms described in Section~\ref{sec:winners}. We
focus on
%the two variants of $\anticor$ described above:
$\bah_{30}(\anticor)$, abbreviated by $\anti^1$ and $\bah_{30}(\anticor(\anticor))$,
abbreviated by $\anti^2$.
%(we have not considered Anticor variants with other window sizes).
Four historical datasets are used. The first NYSE dataset, is the
one used in \shortcite{Cover91,CoverO96,HelmboldSSW96} and
\shortcite{BlumK98}.
%%Cover
%\cite{Cover91} and then
%%Cover and Ordentlich
%\cite{CoverO96},
%%Helmbold {\it et al}
%\cite{HelmboldSSW96} and
%%Blum and Kalai
%\cite{BlumK98}.
%and
%Singer
%\cite{Singer98}.
This dataset contains 5651 daily prices for 36 stocks in the New York Stock Exchange
(NYSE) for the twenty two year period July $3^{rd}$, 1962 to Dec $31^{st}$, 1984.
%\footnote{
%We do not know what criteria was used in choosing this
%particular set of 36 stocks.}
The second TSX dataset consists of 88 stocks from the Toronto Stock Exchange (TSX),
for the five year period Jan $4^{th}$, 1994 to Dec $31^{st}$, 1998.
%\footnote{This dataset was obtained
%from Steven Belantoni.}
%The set contains all TSX stocks that were traded on each of the 1258 trading
%days in this period.
The third dataset consists of the 25 stocks from SP500 which (as of Apr. 2003) had
the largest market capitalization. This set spans 1276 trading days for the period
Jan $2^{nd}$, 1998 to Jan $31^{st}$, 2003.
%\footnote{This dataset was obtained from MSN Money.}
The fourth dataset consists of the thirty stocks composing the Dow Jones Industrial
Average (DJIA) for the two year period (507 days) from Jan $14^{th}$, 2001 to Jan
$14^{th}$, 2003.\footnote{The four datasets,
%including
including their sources and
%their indiviudal stock compositions
individual stock compositions can be downloaded from
{http://www.cs.technion.ac.il/$\sim$rani/portfolios}.}
%\footnote{This
%dataset was obtained from Super Computing Consulting
%and is adjusted for dividends and
%splits.}




\begin{table}[htb!]
\begin{scriptsize}
\begin{center}
\begin{tabular}{l||r|r|r|r||r|r|r|r}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  Algorithm      & NYSE          & TSX  & SP500 & DJIA & NYSE$^{-1}$ & TSX$^{-1}$
  & SP500$^{-1}$ & DJIA$^{-1}$ \\
  \hline \hline
  \textsc{Market} ($\ubah$)         & 14.49         & 1.61 & 1.34 & 0.76 & 0.11  & 1.67 & 0.87 & 1.43 \\
  \textsc{Best Stock}     & 54.14         & 6.27 & 3.77 & 1.18 & 0.32  & \textbf{37.64}& 1.65 & 2.77 \\
  $\cbal^*$       & 250.59        & 6.77& 4.06 & 1.23 & 2.86  & \textbf{58.61}& 1.91 & 2.97 \\ \hline
  $\ucbal$ & 27.07         & 1.59 & 1.64 &0.81 & 0.22  & 1.18 & 1.09 &1.53 \\
  $\anti^1$   & \textbf{17,059,811.56} & \textbf{26.77}& \textbf{5.56} & \textbf{1.59} &
\textbf{246.22 }& 7.12 & \textbf{6.61} & \textbf{3.67} \\
  $\anti^2$ & \textbf{238,820,058.10}& \textbf{39.07}& \textbf{5.88} & \textbf{2.28} &
\textbf{1383.78}& 7.27 & \textbf{9.69} & \textbf{4.60} \\
%  M0             & 111.84        & 1.27 & 1.73 & 0.77 & 0.86  & 4.08 & 1.16 & 1.79 \\
  $\LZ$             & 79.78         & 1.32 & 1.67 & 0.89 & 5.41  & 4.80 & 1.20 & 1.83 \\
  $\EG$             & 27.08         & 1.59 & 1.64 & 0.81 & 0.22  & 1.19 & 1.09 & 1.53 \\
  $\uni$      & 26.99         & 1.59 & 1.62 & 0.80 & 0.22  & 1.19 & 1.07 &1.53 \\
  \hline
\end{tabular}
\end{center}
\caption{Monetary returns in dollars (per \$1 investment) of various algorithms for
four different datasets and their reversed versions. The winner and runner-up for
each market appear in boldface. All figures are truncated to two decimals. }
%An entry $0.00$ indicates that
%the algorithm crashed in
%the sense that the return
%was less than .005 times the starting value.}
\label{tab:returns}
\end{scriptsize}
\end{table}





%\rnote{
These four datasets are quite different in nature (the market returns for these
datasets appear in the first row of Table~\ref{tab:returns}). While every stock in
the NYSE increased in value,
%(i.e. its total return is larger than 1),
32 of the 88 stocks in the TSX lost money, 7 of the 25 stocks in the SP500 lost
money and 25 of the 30 stocks in the ``negative market'' DJIA lost money.
%The DJIA is particularly
%challenging as this market went down; in particular, the average
%annualized return
%during these two years is -12\% (see Table~\ref{tab:risk_return}).
With the exception of the TSX, these data sets include only highly liquid stocks
with large market capitalizations.
%The NYSE and TSX datasets, as well as an earlier DJIA dataset,
%were used while we were developing
%our $\anticor$ algorithms; however, the SP500 dataset
%and the current DJIA dataset were
%introduced after the algorithms were finalized.}
In order to maximize the utility of these datasets and yet present rather different
markets, we also ran each market in reverse. This is simply done by reversing the
order and inverting the relative prices. The reverse datasets are denoted by a `-1'
superscript.
% (e.g. the reverse NYSE
%is NYSE$^{-1}$).
Some of the reverse markets are particularly challenging. For example,
%the annualized average return of the NYSE$^{-1}$ set is
%$-9\%$ and
\emph{all} of the NYSE$^{-1}$ stocks are going down. Note that the forward and
reverse markets (i.e. $\ubah$) for the TSX are both increasing but that the
TSX$^{-1}$ is also a challenging market since so many stocks (56 of 88) are
declining.



%This benchmark set
%of stocks was chosen to remove bias from our choice of stocks
%\rnote{Allan: I guess the following could be rephrased}
%In order to maximize the utility of these
%data sets and yet present rather different markets, we also
%ran each market in reverse.



%All 36 stocks in the NYSE data had a positive return during this
%22 year period where returns ranged from a low of 3.1 to a high of 54
%(that is, $\bahopt$ = 54).
%Of the 36 stocks, only three
%benefited from an active trading strategy against cash.
%The winning strategy for the remaining
%33 stocks was to buy and hold the stock.
%%When cash was replaced by a 4\% annualized bond, seven stocks
%(those with returns in {\bf bold} in Table~\ref{tbl:NYSE})
%benefited from active trading.
%\begin{center}
%\begin{tabular}{|l|r|r|r|}
%\hline
%Company & Return & CBAL-OPT & WT (CBAL-OPT) \\
%\hline
%Alcoa           &  4.4 &    4.4 & 0.86 \\
%Dupont          &  3.0 &    3.2 & 0.73 \\
%Espey           & 13.7 &   17.9 & 0.73 \\
%Iroquois        &  8.9 &   12.1 & 0.73 \\
%Kin Ark         &  4.1 &   18.3 & 0.53 \\
%Lukens          &  4.3 &    4.9 & 0.70 \\
%Mei Corp        & 22.9 &   23.3 & 0.92 \\
%\hline
%\end{tabular}
%\end{center}
%It is interesting to note that the $\cbalopt$
%CBAL-OPT
%of all 36 stocks is
%comprised of a portfolio of just 5 stocks and has a return
%of 251.

%\subsubsection{Pairs of Stocks}
%When looking at individual {\em pairs} of stocks, however, one finds a
%different story. Instead of just these five or seven stocks
%benefiting from being paired with one another, one finds that of the
%possible 630 pairs, almost half (44\%) have a $\cbalopt$
%%CBAL-OPT
%that is 10\% or
%more than the return of the best stock. It is this fact that has encouraged
%the consideration of competitive-based online algorithms as this
%sample does indicate that many
%stock pairings can benefit from frequent trading.
%Of course, it can be argued that identifying a ``profitable pair''
%is the real problem.


%We observe that $\uni$, $\EG$ and the other ``learn winners''
%algorithms  have no
%substantial advantage over $\SPLIT$.
%Previous expositions highlighted combinations of stocks where the
%returns were impressive; that is, where $\EG$ outperformed $\uni$ and
%significantly outperformed
%the best stock.
%But the same can be said for $\SPLIT$.
%%The most frequently cited pair is that of {\em
%Kin Ark} and {\em Iroquois}.
%[ Should we say more  about these pairs]

%it is at least 10\% better than
%$\SPLIT_2$ for 344 pairs. In fact, $\DELTA$ does at
%CBAL-OPT
%how to trade amongst these stocks.
%In the full version of this paper we
%will present several other algorithms, some that expand and some that
%\mnote{What exactly do we want to promise here???}
%limit the risk.
%that do seem to learn and (using this same data set)
%also exhibit good performance.

%\rnote{The discussion below is useful but may be beyond the scope
%of a short paper. In any case, it should be expanded to include
%the two new datasets DJIA (my version) and the SP500.}
%The TSE and DJIA data are quite different in nature from the NYSE data.
%In particular, while every stock made money in the NYSE data, 32 of the 88
%stocks in the TSE data lost money.
%%The best return (i.e.\ $\bahopt$) was
%%6.28 (Gentra Inc.) and the worst return was .12.
%%There were 3 stocks having non zero weight in $\cbalopt$.
%The DJIA was evenly split between stocks that made money (15 out of 30)
%and those that lost money.
%%The best return was 1.92 and
%%the worst return was 0.42.
%The $\cbalopt$ in this
%sample did not actively trade and was just the simple algorithm of buying
%and holding the best stock.


%\rnote{This discussion is to perhaps too minimal
%and may upset readers.
%At the very least we should be more accurate in the description of the algs and give refs
%for each one (M0 and LZ). Maybe its better to remove all these comparison algs at all.
%Without knowing what exactly they are and with their mediocre results this doesn't
%provide any useful information to the reader. So, maybe we should consider removing all the
%other algs from the short version (in a long version this should certainly be in)}
%The
%Markov and LZ (``Lempel-Ziv'') algorithms are simple
%generalizations of successful
%sequence learning algorithms and $\EG$ (``exponential gradiant'')
%is  a standard learning algorithm. ($\EG$ and $\M$ each have one parameter
%which we set according to values used in previous studies).
%In another contrived
%market where one stock consistently wins (e.g. say doubles) every day
%and all other stocks decline or stay fixed, it is clear that $\DELTA$ would
%perform poorly whereas any algorithm that learns this one winning stock will
%do well. Clearly the historical markets do not behave in this manner. However,
%if one wants to hedge between the $\DELTA$ and ``winners'' strategies (or
%between any set of strategies), then
%one can apply a buy and hold to the various strategies or
%use an ``expert learning algorithm'' to adaptively balance
%the portfolio allocation by viewing each competing algorithm as an expert.
%

%\rnote{The following paragraph can safely be rewritten. It should also relate to
%the new table (and of course, discuss and define the new ``annualized'' return, risk
%and Sharpe ratio.)}
Table~\ref{tab:returns}
%Table~\ref{tbl:master}
reports on the total returns of the various algorithms for all eight
datasets.
We see that prediction
algorithms such as $\LZ$ can do quite well
%\footnote{In a currency exchange market reported in \cite{BorodinEG00},
%$\LZ$ is able to beat $\cbal^*$.}
and the more aggressive $\anti^1$ and $\anti^2$ have excellent and sometimes
fantastic returns. Note that these active strategies beat the best stock and even
$\cbal^*$ in all markets with the exception of the TSX$^{-1}$ in which
case they still
significantly outperform the market. The reader may well be distrustful of what
appears to be such unbelievable returns for $\anti^1$ and $\anti^2$ especially when
applied to the NYSE dataset. However, recall that the NYSE dataset consists of $n =
5651$ trading days and
% and the perhaps more meaningful results in Table \ref{tab:risk_return}
%put the returns into better perspective.
%It is then instructive to compute the
%way to understand why
%uch returns are perhaps not so unbelievable is to express the returns
%in terms of
%average daily return needed to
%yield these total (compounded) NYSE returns; that is,
the $y$ such that $y^n$ = the total NYSE return is approximately 1.0029511 for
$\anti^1$ (respectively, 1.0074539 for $\anti^2$); that is, the average daily
increase is less than .3\% (respectively, .75\%).
%\bnote{Ran ; you might want to check my calculations. We used
%to know what fraction of the portfolio was traded every day on average.
%That would be good to know so as to explain how say 1% transaction costs
%can kill the profit even for these extremely high NYSE returns.}
%Thus a transaction cost of 1\% can present a significant challenge to such active
%trading strategies (see also Section~\ref{sec:caveats}).
We observe that learning algorithms such as  $\uni$
and $\EG$ have no substantial advantage over $\SPLIT$.
Some previous expositions of
these algorithms highlighted particular combinations of stocks where the returns
%were more noteworthy
%; for example,
significantly outperformed
%$\uni$ and
the best stock.
%\bnote{I took out the added comment about significantly
%outperfroming $\uni$. The previous sentence talks about $\uni$
%and including $\uni$ in this sentence is somewhat inconsistent. Alternatively
%we could take out the ref to $\uni$ in the previous sentence but
%then we seem to be just attacking $\EG$. I also qualified the
%previous sentence and referred to $\uni$ and $\EG$
%as examples of learning algorithms.
%Again I am trying to not make it appear that we are attacking
%particular algorithms.}
But the same can be said for
$\SPLIT$.

\begin{figure}[htb!]
\begin{center}
        \epsfig{file=eps/djia_cumret.eps,width=3in}
\end{center}
\label{fig:djia_cumret}
\caption{DJIA: Cumulative returns of of $\anti^1$, $\anti^2$,
the best stock and a uniform $\bah$ (the ``market'').}
\end{figure}

The total returns of $\anti^1$ and $\anti^2$
presented in Table~\ref{tab:returns}
are impressive but are far from telling a complete story.
Consider the graphs in figure~\ref{fig:sp_com}.
While both $\anti^1$ and $\anti^2$ perform well
with respect to the uniform market and
the best stock throughout most of the investment period,
there are some periods where the cumulative return of these
strategies decrease. This (not surprising) behavior indicates that
there is a certain degree of risk in using these investment
algorithms.




In finance the standard risk measure is the standard deviation of
the return. In Table~\ref{tab:risk_return} we provide
\emph{annualized returns} and \emph{risks} as well as
\emph{risk-adjusted returns} for all markets and algorithms
considered here.\footnote{The annualized return is estimated using
the geometric mean of the individual daily returns and the risk is
the standard deviation of these daily returns multiplied by
$\sqrt{252}$ where 252 is the assumed standard number of trading
days per year. These calculations are standard. The (annualized)
Sharpe ratio \cite{Sharpe75} is the ratio of annualized return
minus the risk-free return (taken to be 4\%) divided by the
(annualized) standard deviation.} For example, the annualized
return of the best stock in the DJIA set is 8.6\%, its annualized
risk (standard deviation) is 42\% and its annualized risk-adjusted
return (Sharpe ratio) is 11\%.






\begin{table}[h]
\begin{scriptsize}
\begin{center}
\begin{tabular}{l||r|r|r|r||r|r|r|r}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  Algorithm      & NYSE          & TSX  & SP500 & DJIA & NYSE$^{-1}$
  & TSX$^{-1}$ & SP500$^{-1}$ & DJIA$^{-1}$ \\
  \hline \hline
  \textsc{Market}          & $12 \pm 14\%$ & $10 \pm 12\%$ & $5\pm 24\%$ & $-12 \pm 24\%$ & $-9 \pm 15\%$
                 & $10 \pm 22\%$   & $-2\pm22\%$ & $19 \pm 25\%$ \\
         ($\ubah$)        & 58\%         & 46\%      & 8\%     & -67\%          & -86\%
                 & 29\%         & -28\%  & 61\% \\ \hline
  \textsc{Best Stock}     & $19 \pm 24\%$ & $44 \pm 55\%$ & $30\pm51\%$ & $8 \pm 42\%$   & $-4 \pm 21\%$
                 & $106 \pm 104\%$   & $10\pm32\%$& $65 \pm 114\%$ \\
                 & 63\%          & 73\%      & 50\%     & 11\%           & -41\%
                 & 98\%          & 20\%      & 54\% \\ \hline
  $\cbal^*$       & $27 \pm 30\%$ & $46 \pm 40\%$  & $31\pm42\%$ & $11 \pm 26\%$  & $4 \pm 40\%$
                 & $125 \pm 78\%$   & $13\pm27\%$ & $71 \pm 76\%$ \\
                 & 78\%          & 106\%    &65\%     & 27\%           & 1\%
                 & \textbf{156\%}         &  35\%  & 88\% \\ \hline
  \hline
  $\ucbal$  & $15 \pm 13\%$ & $9 \pm 13\%$  & $10\pm22\%$ & $-9 \pm 25\%$  & $-6 \pm 13\%$
                 & $3 \pm 13\%$   & $1\pm 21\%$ & $23 \pm 25\%$ \\
                 &  88\%         & 44\%   & 28\%       & -54\%          & -77\%
                 & -3\%          &-9\%  & 77\% \\ \hline
  $\anti^1$      & $110 \pm 28\%$& $93 \pm 45\%$ & $40\pm37\%$ & $26 \pm 35\%$  & $27 \pm 27\%$
                 & $48 \pm 41\%$   &$45\pm32\%$ & $90 \pm 31\%$ \\
                 & \textbf{367\%}          & \textbf{196\%}  & \textbf{95\%} & \textbf{62\%} & \textbf{86\%}
                 & 107\%         &\textbf{126\%}  & \textbf{277\%} \\ \hline
  $\anti^2$      & $136 \pm 35\%$& $108 \pm 60\%$& $41\pm 44\%$ & $50 \pm 39\%$  & $38 \pm 33\%$
                 & $48 \pm 46\%$   &$56\pm36\%$ & $113 \pm 35\%$ \\
                 & \textbf{370\%}        & \textbf{172\%} & \textbf{86\%} & \textbf{119\%} & \textbf{101\%}
                 & 96\%         & \textbf{143\%} &  \textbf{304\% }\\ \hline
 % M0             & $23 \pm 21\%$ & $4 \pm 20\%$  & $11\pm24\%$ & $-11 \pm 26\%$ & $-0.6 \pm 20\%$
 %                & $32 \pm 21\%$   &$2\pm26\%$  & $33 \pm 27\%$ \\
 %                & 89\%         & 4\%  & 29\%         & -59\%          & -22\%
 %                & \textbf{132\%}        &-3\% & 107\% \\ \hline
 $\LZ$             & $21 \pm 23\%$ & $5 \pm 25\%$  & $10\pm25\%$ & $-5 \pm 28\%$  & $7 \pm 21\%$
                 & $36 \pm 27\%$   &$3\pm26\%$ & $35 \pm 27\%$ \\
                 & 76\%          & 6\%   & 25\%        & -33\%          & 17
                 & \textbf{117\%}         &-0.8\% & 112\% \\ \hline
 $\EG$             & $15 \pm 13\%$ & $9 \pm 13\%$  & $ 10\pm22\%$ & $-9 \pm 25\%$  & $-6 \pm 13\%$
                 & $3 \pm 13\%$   & $1\pm 22\%$ & $23 \pm 25\%$ \\
                 & 88\%          & 44\%  & 28\%         & -54\%          & -77\%
                 & -2\%          &-9\% & 77\% \\ \hline
 $\uni$      & $15 \pm 13\%$& $9 \pm 13\%$  & $10\pm22\%$ & $-9 \pm 25\%$  & $-6 \pm 13\%$
                 & $3 \pm 13\%$  & $1\pm 22\%$ &  $23 \pm 25\%$ \\
                 & 87\%         & 44\%   & 27\%     & -55\%            & -77\%
                 & -2\%         & -11\% & 76\%\\
  \hline
\end{tabular}
\end{center}
\caption{Annualized returns and respective annualized volatilities
as well as annualized risk-adjusted returns (Sharpe Ratio)
 of the various algorithms over three datasets and their
 reversed versions.
The winner and runner-up Sharpe Ratio for each market appear in boldface.
All figures are truncated to two decimals. }
%An entry $0.00$ indicates that
%the algorithm crashed in
%the sense that the return
%was less than .005 times the starting value.}
\label{tab:risk_return}
\end{scriptsize}
\end{table}



%{\it However, the introduction of
%transaction costs changes the situation dramatically.}}

%\begin{figure}[h]
%\begin{center}
        %\epsfig{file=eps/djia_cumret.eps,width=3in}
%\end{center}
%\label{fig:djia_cumret}
%\caption{DJIA: Cumulative returns of of $\anti^1$, $\anti^2$,
%the best stock and a uniform $\bah$.}
%\end{figure}
%


%\rnote{
%As noted above
%The total returns of $\anti^1$ and $\anti^2$ presented in Table~\ref{tab:returns}
%are impressive but are far from telling a complete story.
%Consider the graphs in figure~\ref{fig:sp_com}.
%While both $\anti^1$ and $\anti^2$ perform well
%with respect to the uniform market and
%the best stock throughout most of the investment period,
%there are some periods where the cumulative return of these
%strategies decrease. This (not surprising) behavior indicates that
%there is a certain degree of risk in using these investment
%algorithms.
%In Table~\ref{tab:risk_return} we provide
%\emph{annualized returns} and \emph{risks} as well as
%\emph{risk-adjusted returns} for all markets and algorithms
%considered here.\footnote{The annualized return is estimated
%using the geometric mean of the individual daily returns and the
%risk is the standard deviation of these daily returns multiplied
%by $\sqrt{252}$
%where 252 is the assumed standard number
%of trading days per year.
%These calculations are standard.
%The (annualized) Sharpe ratio
%\cite{Sharpe75} is the ratio of annualized return minus
%the risk-free return (taken to be
%4\%). divided by the (annualized) standard deviation.}
%For example, the annualized return of the best stock
%in the DJIA set is 8\%, its annualized risk (standard deviation) is
%42\% and its annualized risk-adjusted return (Sharpe ratio)
%is 11\%.
%%} % end of rnote
%











%\begin{table}[h]
%\begin{scriptsize}
%\begin{center}
%\begin{tabular}{l||r|r|r|r||r|r|r|r}
  %\hline
  %% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  %Algorithm      & NYSE          & TSX  & SP500 & DJIA & NYSE$^{-1}$
  %& TSX$^{-1}$ & SP500$^{-1}$ & DJIA$^{-1}$ \\
  %\hline \hline
  %\textsc{Market} ($\ubah$)         & $12 \pm 14\%$ & $10 \pm 12\%$ & $5\pm 24\%$ & $-12 \pm 24\%$ & $-9 \pm 15\%$
                 %& $10 \pm 22\%$   & $-2\pm22\%$ & $19 \pm 25\%$ \\
                 %& 58\%         & 46\%      & 8\%     & -67\%          & -86\%
                 %& 29\%         & -28\%  & 61\% \\ \hline
  %\textsc{Best Stock}     & $19 \pm 24\%$ & $44 \pm 55\%$ & $30\pm51\%$ & $8 \pm 42\%$   & $-4 \pm 21\%$
                 %& $106 \pm 104\%$   & $10\pm32\%$& $65 \pm 114\%$ \\
                 %& 63\%          & 73\%      & 50\%     & 11\%           & -41\%
                 %& 98\%          & 20\%      & 54\% \\ \hline
  %$\cbal^*$       & $27 \pm 30\%$ & $46 \pm 40\%$  & $31\pm42\%$ & $11 \pm 26\%$  & $4 \pm 40\%$
                 %& $125 \pm 78\%$   & $13\pm27\%$ & $71 \pm 76\%$ \\
                 %& 78\%          & 106\%    &65\%     & 27\%           & 1\%
                 %& \textbf{156\%}         &  35\%  & 88\% \\ \hline
  %\hline
  %$\ucbal$  & $15 \pm 13\%$ & $9 \pm 13\%$  & $10\pm22\%$ & $-9 \pm 25\%$  & $-6 \pm 13\%$
                 %& $3 \pm 13\%$   & $1\pm 21\%$ & $23 \pm 25\%$ \\
                 %&  88\%         & 44\%   & 28\%       & -54\%          & -77\%
                 %& -3\%          &-9\%  & 77\% \\ \hline
  %$\anti^1$      & $110 \pm 28\%$& $93 \pm 45\%$ & $40\pm37\%$ & $26 \pm 35\%$  & $27 \pm 27\%$
                 %& $48 \pm 41\%$   &$45\pm32\%$ & $90 \pm 31\%$ \\
                 %& \textbf{367\%}          & \textbf{196\%}  & \textbf{95\%} & \textbf{62\%} & \textbf{86\%}
                 %& 107\%         &\textbf{126\%}  & \textbf{277\%} \\ \hline
  %$\anti^2$      & $136 \pm 35\%$& $108 \pm 60\%$& $41\pm 44\%$ & $50 \pm 39\%$  & $38 \pm 33\%$
                 %& $48 \pm 46\%$   &$56\pm36\%$ & $113 \pm 35\%$ \\
                 %& \textbf{370\%}        & \textbf{172\%} & \textbf{86\%} & \textbf{119\%} & \textbf{101\%}
                 %%& 96\%         & \textbf{143\%} &  \textbf{304\% }\\ \hline
 %% M0             & $23 \pm 21\%$ & $4 \pm 20\%$  & $11\pm24\%$ & $-11 \pm 26\%$ & $-0.6 \pm 20\%$
 %%%                & $32 \pm 21\%$   &$2\pm26\%$  & $33 \pm 27\%$ \\
 %%                & 89\%         & 4\%  & 29\%         & -59\%          & -22\%
 %%%                & \textbf{132\%}        &-3\% & 107\% \\ \hline
 %$\LZ$             & $21 \pm 23\%$ & $5 \pm 25\%$  & $10\pm25\%$ & $-5 \pm 28\%$  & $7 \pm 21\%$
                 %& $36 \pm 27\%$   &$3\pm26\%$ & $35 \pm 27\%$ \\
                 %& 76\%          & 6\%   & 25\%        & -33\%          & 17
                 %& \textbf{117\%}         &-0.8\% & 112\% \\ \hline
 %$\EG$             & $15 \pm 13\%$ & $9 \pm 13\%$  & $ 10\pm22\%$ & $-9 \pm 25\%$  & $-6 \pm 13\%$
                 %& $3 \pm 13\%$   & $1\pm 22\%$ & $23 \pm 25\%$ \\
                 %& 88\%          & 44\%  & 28\%         & -54\%          & -77\%
                 %& -2\%          &-9\% & 77\% \\ \hline
 %$\uni$      & $15 \pm 13\%$& $9 \pm 13\%$  & $10\pm22\%$ & $-9 \pm 25\%$  & $-6 \pm 13\%$
                 %& $3 \pm 13\%$  & $1\pm 22\%$ &  $23 \pm 25\%$ \\
                 %& 87\%         & 44\%   & 27\%     & -55\%            & -77\%
                 %& -2\%         & -11\% & 76\%\\
  %\hline
%\end{tabular}
%\end{center}
%\caption{Annualized returns and respective annualized volatilities
%as well as annualized risk-adjusted returns (Sharpe Ratio)
 %of the various algorithms over three datasets and their
 %reversed versions.
%The winner and runner-up Sharpe Ratio for each market appear in boldface.
%All figures are truncated to two decimals. }
%%An entry $0.00$ indicates that
%%the algorithm crashed in
%%the sense that the return
%%was less than .005 times the starting value.}
%\label{tab:risk_return}
%\end{scriptsize}
%\end{table}


\newcommand{\com}{\textsf{com}}
\section{On Commissions, Trading Friction and Other Caveats}
\label{sec:caveats}

 When handling a portfolio of $m$ stocks our algorithm may
perform up to $m$ transactions per day. A major concern is therefore the commissions
it will incur. Within the \emph{proportional commission} model
\cite<see e.g.>[Section 14.5.4]{BlumK98,BorodinE98} there exists a fraction $\gamma
\in (0,1)$ such that an investor pays at a rate of $ \gamma /2 $ for each buy and
for each sell. Therefore, the return of a sequence
$\bbb_1,\ldots,\bbb_n$ of
portfolios with respect to a market sequence
$\xxx_1,\ldots,\xxx_n$ is
$\prod_t
\left( \bbb_t \cdot \xxx_t
(1 - \sum_j \frac{\gamma}{2}|\bbb_t(j) - \hat{\bbb}_t(j)|) \right)$,
where $\hat{\bbb}_t = \frac{1}{\bbb_t \cdot \xxx_t}(\bbb_t(1)
\xxx_t(1),\ldots,\bbb_t(m) \xxx_t(m))$.\footnote{We note that
\citeA{BlumK98} showed that the performance guarantee of $\uni$ still holds
(and gracefully degrades) in the case of proportional commissions.}
Our investment algorithm in its simplest
form can tolerate very small proportional commission rates and still beat the best
stock.
The graphs in Figure~\ref{fig:sp_com} depict the total returns
of $\bah_{30}(\anticor)$ with proportional commission factor $\gamma =0.1\%,
0.2\%,\ldots,1\%$.
The strategy
can withstand
%is robust to
small commission factors.
For example, with $\gamma = 0.1\%$ the algorithm still beat the best stock
in all four markets we consider (and it beats the market with
$\gamma < 0.4\%$).
%(the
%annualized return
%of $\anticor$ in this case is 30\%, which is similar to the best stock,
%and its volatility is 38\% compared to 51\% for the best stock).
Moreover it still clearly beats the market whenever
$\gamma < 0.4\%$.
%However, with $\gamma > 0.5\%$ the strategy starts to lose.



\begin{figure}[h]
\begin{center}
        \epsfig{file=eps/commissions.eps,width=4.2in}
\end{center}
\label{fig:sp_com}
\caption{Total returns of $\bah_{30}(\anticor)$ with
proportional
commissions $\gamma =0.1\%,0.2\%,\ldots,1\%$.}
\end{figure}




However, some current
online brokers charge very small proportional commissions, perhaps
in addition to
a small
\emph{flat commission rate} for all trades.\footnote{For example,
on its USA site,  E*TRADE
(\texttt{https://us.etrade.com}) offers a flat fee of \$10 for any trade
up to 5000 shares and then \$.01/share thereafter.}
This means that a large investor can scale up the investment and suffer only
a small proportional transaction rate.

An additional caveat is our assumption that
all trades could be implemented using the closing price. While
in principle there is nothing special about the closing price
(i.e. our algorithms can
trade at any time during the trading day)
practical consideration related to dataset gathering and availability
dictated the use of these prices.\footnote{Specifically,
historical closing prices
are in the public domain and allow
for experimental \emph{reproducibility}. Historical intraday trading quotes can also
be gathered but such data is usually protected and can be costly to obtain.}
Our algorithms assume that
all portfolio adjustments are implemented
using the quoted prices they receive as inputs. This means that all
transactions are implemented simultaneously using the quoted
prices. With current online brokers a computerized system can issue
all transaction orders almost instantly but there is no guarantee that
they will be all implemented instantly. This trading
``friction'' will necessarily generate discrepancies
between the input prices and implementation prices.

A related problem that one must face when actually trading is the difference between
bid and ask prices. These bid-ask \emph{spreads} (and the availability of stocks for
both buying and selling) are functions of stock liquidity and are
typically small for large market capitalization stocks.
%We note that All the markets
We consider here only very large market cap stocks.
%As a final caveat, we note that
%needs to be mentioned.
%Namely, the entire theory of portfolio selection
%algorithms assumes
%we assume that any one portfolio selection algorithm has no impact on the market!
%But just like any goose laying golden eggs, widespread use will soon lead to the end
%of the goose; that is, the market will quickly react.
% and
%previously predictable components will disappear.
%In our case, the market will quickly react to
%any method which does consistently and substantially beat the market.


Any report of abnormal returns using historical markets should be suspected of
``data snooping''. In particular, all of our historical data sets
are conditioned on the fact that all stocks were traded every day
and there were no bankrupcies or stocks that became virtually worthless
in any of these data sets. Furthermore,
%Data snooping in this context means that
when a dataset is excessively mined by testing many strategies there is a
substantial chance that one of the strategies will be successful by simple
over-fitting.
%When using learning strategies which adapt
%themselves to the data this is especially dangerous
%and great care should be taken not to tune parameters and
%overfit the data.
Another data snooping hazard is stock selection. Our $\anticor$ algorithms were
fully developed using only the NYSE and TSX datasets.
The DJIA and SP500 sets were
obtained (from public domain sources) after the algorithms were fixed.
%In all markets there was no stock
%selection. \bnote{This is technically not true.}
%We used the entire collection in the NYSE set. The composition of
%the TSX dataset includes all stocks that traded every day during the
%trading period (and we have not chosen this dataset)
%%as well as the entire collections in all other datasets.
%There was no selection of stocks in
%the DJIA set (all 30 stocks are used) and the composition
%of stocks in the SP500 dataset (25 largest market cap stocks) was
%independent of the algorithm.
Finally, our algorithm has one parameter (the maximal window size $W$). Our
experiments clearly indicate that the algorithm's performance is robust with respect
to $W$ (see, for example,  Figure~\ref{fig:anti_3}).





















\section{Concluding Remarks}
\label{sec:concluding}

Traditional work in financial economics tend to focus on the understanding of
stock price determination. The main question there is:
Can we predict the stock market? Judging by the extensive but
inconclusive work done in financial forecasting, perhaps this is not the most
beneficial question to ask.
Rather, can a computer program consistently outperform the market?
Besides practicality, it is clear that any successful portfolio
selection algorithm is in itself a mathematical model that can
provide some new intuition on stock price formation.
For example, in our case, the algorithms suggest that some
stock price fluctuations are sufficiently ``periodic''
and anti-correlated.


A number of well-respected works report on statistically robust ``abnormal'' returns
for simple
%trading
%rules and especially
``technical analysis'' heuristics, which slightly beat the market. For example, the
landmark study of \citeA{Brock92} apply 26 simple trading
heuristics to the DJIA index from 1897 to 1986 and provide strong support for
technical analysis heuristics.
%Some of the rules tested could generate an extra average
%annualized 3.4\% return over the DJIA market.
While \emph{consistently} beating the market is considered a significant
(if not
impossible) challenge, our approach to portfolio selection
indicates that beating
the best stock is an achievable goal.
While we have mainly focused
on an idealized ``frictionless setting'', we believe that even
in such a frictionless setting
(which seems like a reasonable starting point) no such results
have been previously claimed in the literature.
%And, furthermore,
%it seems quite plausible that more extensive use of

The results presented here raise various interesting questions.
Since simple statistical relations such as correlation give rise to such
outstanding returns it is plausible that various other, perhaps
more sophisticated machine learning techniques, can give rise
to better portfolio selection algorithms capable of larger returns
and tolerating larger commissions fees.

On the theoretical side,
what is missing at this point of time is an
analytical model which better explains why our active trading strategies are so
successful. In this regard, we are investigating various ``statistical adversary''
models along the lines suggested by \citeA{Raghavan92}
and \shortciteA{ChouCEKL95}. Namely, we would
like to show that an algorithm performs well (relative to some benchmark) for any
market sequence that satisfies certain constraints on its empirical statistics.

One final caveat needs to be mentioned.
Namely, the entire theory of portfolio selection
algorithms assumes that any one portfolio selection algorithm has no impact on the
market! But just like any goose laying golden eggs, widespread
use will soon lead to
the end of the goose. In our case, the market will quickly react to
any method which does consistently and substantially beat the market.


\section*{Acknowledgments}
%We thank Rob Schapire, Yoram Singer and
We thank Michael Loftus for his helpful comments.
We also thank Izzy Nelken and Super Computing Inc. for
their help in validating the DJIA dataset.
%\rnote{I have a problem here. Izzy gave us the rates for the DJIA.
%I asked it because the dataset I downloaded from Yahoo! excluded
%a few days. It turned out that all the missing days were around
%Sept 11th.. so I didn't need his data after all, but he still
%gave it and conditioned it by acknowledging his company.
%I can't recall but I think the numbers we are using are his
%and not from Yahoo. So what do you think we should say here?}
%\bnote{Well once you explained it, then it made sense to me.
%Was the market closed those days? I think so. I slightly reworded it
%andm mentioned only the DJIA. I dont mind if we say
%"some of our data sets as you had it but
%why not be more accurate?}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55
% Science

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{How to expolit volatility}







%Once again, we could use a standard learning algorithm (by viewing
%each window $w$ as an expert) to adaptively learn and set the window size.
%%Or we could simply apply a uniform buy and hold strategy to the
%%windows and invest in each window uniformly.
%However, our experimental results suggest that trying to
%learn the winners directly  or even trying to learn a parameter such
%as the window size $w$ does not seem to be a generally successful
%approach. But we do observe excellent return when we apply
%a buy and hold (over the window sizes) to our $\DELTA$ algorithm.
%And  now we can apply a standard computer science idea and
%further compose algorithms. That is, rather than viewing stocks
%as experts, lets view stocks as algorithms (i.e. as the extreme buy and hold of
%that stock). Then any set of
%portfolio selection algorithms can be composed together as we are doing when we
%apply buy and hold to $\DELTA$ which in turn is being
%applied to the extreme buy and hold algorithms. We will denote
%this algorithm as $\ubah(\DELTA)$.
%And if $\ubah(\DELTA)$
%is successful, why not try $\ubah(\DELTA(\DELTA))$?  The
%impact of this compounding is to smooth out the anti-correlations
%(see figure~\ref{XXX})
%and the results obtained (see figure~\ref{YYY}) are quite impressive.
%


%When
%no stock has a claim on any other stock, the
%algorithm acts as a buy and hold.
%In Sections~\ref{sec:experimental} and \ref{sec:commissions}






















%\section{Concluding Remarks and Future Work}
%Active trading
%is criticized by many quantitative finance people.
%The main focus of this
%scrutiny are the
%%At the main focus of scrutiny are the
%\emph{technical traders}
%(also called ``chartists'') who advocate
%the use of heuristic rules for trading based on patterns
%in price (and volume) sequences.
%In his influential book \emph{A Random Walk Down Wall Street}, Malkiel
%\cite{Malkiel96} concludes that ``under scientific scrutiny,
%chart-reading must share a pedestal with alchemy''.
%
%In contrast, a number of well-respected works report
%on statistically robust abnormal returns of simple trading
%rules and especially ``technical analysis'' heuristics.
%For example, the landmark study
%of Brock \emph{et al.} \cite{Brock92} apply 26
%simple trading heuristics to the DJIA index from 1897 to 1986 and
%provide strong support for these technical analysis heuristics.
%Some of the rules tested could generate an extra average
%annualized 3.4\% return over the DJIA market.
%
%
%While the ability of trading algorithms
%to consistently ``beat the market''
%is considered a great (and some would claim impossible)
%challenge, our study and
%algorithmic approach to
%portfolio selection
%indicates that not only is beating the
%market possible, but beating
%the best stock is an achievable goal.
%These results stand in sharp contrast with
%traditional ``efficient market'' and ``random walk'' hypotheses
%and strongly support studies which reject these hypotheses
%(e.g. Lo and MacKinlay \cite{LoMacKinlay88,LoMacKinlay01}).
%
%
%
%
%
%As noted by Lo \emph{et al.} \cite{Lo00}
%is is plausible that much of the academic skepticism towards
%active trading algorithms and technical trading is a result
%of ``linguistic barriers between technical analysts and
%academic finance''. We believe that in addition to
%this barrier there are others such as
%the lack of rigor and in particular,
%deficient experimental methodology.
%
%From both a theoretical and experimental point of
%view, it is clear that a competitive based approach
%to portfolio selection is only just beginning to emerge.
%In contrast, the related topic of sequence prediction is
%much better developed and indeed the practice seems
%to closely follow the theory. There are, of
%course, at least two significant
%differences; namely that (first)  sequence prediction is a special
%case of portfolio selection and (second) that transaction costs
%(and additionally, bid-ask spreads) are
%a reality having a  significant  impact.
%%In the terminology
%%of Metrical Task Systems and competitive analysis
%%(see \cite{BorodinE98} and \cite{BlumB97}),
%%there is a cost to change states (i.e.\ portfolios) in addition
%%to a loss (or profit) of being in a state.
%%One other obviously
%%important difference is that stock market prices
%%are subject to the dictates of the human perception
%%(e.g as to the state of the economy) and world events
%%(e.g. natural disasters) and hence
%%can be viewed as being ``less predictable''.
%%As discussed above,
%%\mnote{Need to finish this subsection. Or we can just take it out.}
%%in the direct application of prediction algorithms for portfolio selection by
%%aplying these algorithms on the Kelly projections
%%we ignore much of the information in the market vectors.
%

%As previously suggested, any useful online algorithm should at least
%beat the market; that is, the algorithm should be able
%to consistently equal and frequently surpass the performance
%of the uniform buy and hold. In the absence of
%transaction costs, all of the online
%algorithms discussed in this paper were able to beat the market for
%the NYSE stock data. However, the same was not true for
%the other datasets.
%Furthermore, when
%even modest transaction costs (e.g. .1\%) were introduced
%many of the algorithms suffered significant (and sometimes
%catastrophic) losses on some datasets. This phenomena is most striking for
%the $\DELTA$ algorithm and for the $\LZ$ algorithm
%which is a very practical (and universal) algorithm
%in the sequence prediction setting. When trading every day,
%the $\LZ$ and
%$\DELTA$ algorithms are clearly very sensitive to transaction costs
%and indeed they seem to be
%recipes for disaster in the context of
%2\% transaction costs. More positive results can be obtained
%if these algorithms are constrained to trade less frequently, but
%it is still an open question if some online portfolio selection algorithm
%can consistently beat the market , or more ambitiously, beat the best stock
%when faced with modertae transaction costs.
%%We also note that the TSE data  seems to
%%be the most  challenging data set for our online algorithms.
%%On the compressed
%%TSE data, no online algorithm matched the performance of $\ubah$ even
%%without transaction costs.
%%We suspect that the TSE data is especially
%%problematic because of the large number of stocks with only 3
%%out of the 88 stocks having non-zero weight in $\cbalopt$. In some sense,
%%the ``portfolio selection problem'' is a misnomer and perhaps
%%``portfolio management problem'' would be a more appropriate name.
%%Choosing or selecting a good subset of stocks to manage may be
%%the real challenge.
%
%
%%More generally, we want to
%%understand the extent to which a competitive based theory
%%of online algorithms can predict performance with regard to
%%real stock market data and real transaction costs.
%%In particular, can such a theory ``learn'' to focus on a
%%promising subset of stocks.  And here we are
%%only talking about a theory that completely disregards
%%the feedback on the market of any successful algorithm! Whether
%%or not such a theory can influence practice, there are many
%%interesting theoretical questions which need to be answered.
%%


\bibliography{portfolios}
\bibliographystyle{theapa}

%\appendix
%\section{Some Graphs and Tables}
%
%\begin{figure}[h]
%\begin{center}
%\begin{tabular}{cc}
%        \epsfig{file=eps/window_anticor30_NYSE.eps,width=3in} &
%        \epsfig{file=eps/window_anticor30_TSE.eps,width=3in} \\
%        (a) & (b)\\
%        \epsfig{file=eps/window_anticor30_SP_5.eps,width=3in} &
%        \epsfig{file=eps/window_anticor30_DJA.eps,width=3in} \\
%        (c) & (d)
%\end{tabular}
%\end{center}
%\vspace{.5cm}
%\caption{\label{fig:return_vs_window}
%$\anticor$'s total return (per \$1 investment) vs. window size. (a) NYSE; (b) TSX; (c) SP500; (d) DJA.
%%The red lines represent the final return of the best stock and the blue
%%lines, the final return the (uniform) market.
%%In (c) the dash-dotted line depicts the return of the entire DJA index.
%Note that market return in figure (a) is too small to be
%clearly seen (it is 14.49).}
%\end{figure}
%
%
%\begin{figure}[h]
%\begin{center}
%\begin{tabular}{cc}
%        \epsfig{file=eps/max_win_NYSE.eps,width=2.7in} &
%        \epsfig{file=eps/max_win_DJA.eps,width=2.7in}
%\end{tabular}
%\end{center}
%\vspace{.5cm}
%\caption{\label{fig:return_max_win_NYSE}
%$\bah(\anticor)$'s total return (per \$1 investment) as a function
%of the maximal window $W$.}
%\end{figure}
%
%
%
%



\end{document}
