\documentclass[11pt,letter]{article}
\pagestyle{plain}
\usepackage{latexsym}
%\textwidth15cm
%\newtheorem{lemma}{Lemma}
\newtheorem{statement}{Proposition}
\newtheorem{exercise}{Exercise}
%\newtheorem{theorem}{Theorem}
%\newtheorem{prop}{Proposal}
%\newtheorem{property}{Property}
%\newtheorem{corollary}{Corollary}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%% comments and stuff / temporary %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\lastcorrections}%
{{\vskip  0.2in
\begin{sloppypar}
    \baselineskip -0.2in
    \tiny\bf\noindent Last Corrections:\\   %%%%% keep this info
                                            %%%%% current

larry: Tue Sep  2 14:08:23 PDT 2003
\end{sloppypar}
}}

\newcommand{\margincomment}[1]%
    {{%
      \marginpar{{\tiny\begin{minipage}{0.5in}
                       \begin{flushleft}
                          {#1}
                       \end{flushleft}
                       \end{minipage}
                }}
    }}

%\renewcommand{\cite}[1]{{[{\sf #1}]}}  % temporary, to avoid latex complaints
%\renewcommand{\ref}[1]{{[{\sf #1}]}}  % temporary, to avoid latex complaints

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% useful editing macros %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\etal}{{\em et al.~\/}}
\newcommand{\tH}{{\rm th}}
\newcommand{\etc}{{\em etc.\/}}
\newcommand{\ie}{{\em i.e.\/}}
\newcommand{\eg} {{\em e.g.\/}}
\newcommand{\larry}{$\calL^3$}
\newcommand{\mch}{\mbox{${\cal MC}h$}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% lengths and sizes %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\setlength{\evensidemargin}{0.1in}
%\setlength{\oddsidemargin}{0.1in}
%\setlength{\textwidth}{6.7in}
%\setlength{\topmargin}{0.2in}
%\setlength{\textheight}{8.7in}
%\setlength{\headheight}{0in}
%%\setlength{\headsep}{0in}
%\setlength{\topsep}{0in}
%\setlength{\itemsep}{0in}

%\parskip=.080in
%\setlength{\evensidemargin}{0.0in}
%\setlength{\oddsidemargin}{0.0in}
%\setlength{\textwidth}{6.5in}
%\setlength{\topmargin}{0.0in}
%\setlength{\textheight}{8.8in}
%%\setlength{\headheight}{0in}
%\setlength{\headsep}{0in}
%\setlength{\topsep}{0in}
%\setlength{\itemsep}{0in}
\addtolength{\textheight}{1.0in}
\addtolength{\topmargin}{-0.6in}
\addtolength{\textwidth}{1.0in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\evensidemargin}{-0.5in}
%\addtolength{\textheight}{0.6in}
%\addtolength{\topmargin}{-0.4in}
%\addtolength{\textheight}{0.0in}
%\addtolength{\topmargin}{-0.6in}
%\addtolength{\textwidth}{1.0in}
%\addtolength{\oddsidemargin}{-0.5in}
%\addtolength{\evensidemargin}{-0.5in}
%\renewcommand{\baselinestretch}{1.16}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% all sorts of letters %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bfx}{{\bf x}}

\newcommand{\bara}{{\bar a}}
\newcommand{\barm}{{\bar m}}
\newcommand{\barA}{{\bar A}}

\newcommand{\barx}{{\bar x}}
\newcommand{\bary}{{\bar y}}
\newcommand{\barz}{{\bar z}}
\newcommand{\barr}{{\bar r}}

\newcommand{\calA}{{\cal A}}
\newcommand{\calB}{{\cal B}}
\newcommand{\calC}{{\cal C}}
\newcommand{\calD}{{\cal D}}
\newcommand{\calE}{{\cal E}}
\newcommand{\calF}{{\cal F}}
\newcommand{\calG}{{\cal G}}
\newcommand{\calH}{{\cal H}}
\newcommand{\calI}{{\cal I}}
\newcommand{\calJ}{{\cal J}}
\newcommand{\calK}{{\cal K}}
\newcommand{\calL}{{\cal L}}
\newcommand{\calM}{{\cal M}}
\newcommand{\calN}{{\cal N}}
\newcommand{\calO}{{\cal O}}
\newcommand{\calP}{{\cal P}}
\newcommand{\calQ}{{\cal Q}}
\newcommand{\calR}{{\cal R}}
\newcommand{\calS}{{\cal S}}
\newcommand{\calT}{{\cal T}}
\newcommand{\calU}{{\cal U}}
\newcommand{\calV}{{\cal V}}
\newcommand{\calW}{{\cal W}}
\newcommand{\calX}{{\cal X}}
\newcommand{\calY}{{\cal Y}}
\newcommand{\calZ}{{\cal Z}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% maly %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\maly}[1]{{\scriptscriptstyle#1}}
\newcommand{\malyz}{{\maly{0}}}
\newcommand{\malyone}{{\maly{1}}}
\newcommand{\malytwo}{{\maly{2}}}
\newcommand{\malythree}{{\maly{3}}}
\newcommand{\malyhalf}{{\mbox{$\maly{\frac{1}{2}}$}}}
\newcommand{\malylambdahalves}{{\mbox{$\maly{\frac{\lambda}{2}}$}}}
\newcommand{\malyA}{{\scriptscriptstyle A}}
\newcommand{\malyB}{{\scriptscriptstyle B}}
\newcommand{\malyC}{{\scriptscriptstyle C}}
\newcommand{\malyD}{{\scriptscriptstyle D}}
\newcommand{\malyE}{{\scriptscriptstyle E}}
\newcommand{\malyF}{{\scriptscriptstyle F}}
\newcommand{\malyG}{{\scriptscriptstyle G}}
\newcommand{\malyH}{{\scriptscriptstyle H}}
\newcommand{\malyI}{{\scriptscriptstyle I}}
\newcommand{\malyJ}{{\scriptscriptstyle J}}
\newcommand{\malyK}{{\scriptscriptstyle K}}
\newcommand{\malyL}{{\scriptscriptstyle L}}
\newcommand{\malyM}{{\scriptscriptstyle M}}
\newcommand{\malyN}{{\scriptscriptstyle N}}
\newcommand{\malyO}{{\scriptscriptstyle O}}
\newcommand{\malyP}{{\scriptscriptstyle P}}
\newcommand{\malyQ}{{\scriptscriptstyle Q}}
\newcommand{\malyR}{{\scriptscriptstyle R}}
\newcommand{\malyS}{{\scriptscriptstyle S}}
\newcommand{\malyT}{{\scriptscriptstyle T}}
\newcommand{\malyU}{{\scriptscriptstyle U}}
\newcommand{\malyV}{{\scriptscriptstyle V}}
\newcommand{\malyW}{{\scriptscriptstyle W}}
\newcommand{\malyX}{{\scriptscriptstyle X}}
\newcommand{\malyY}{{\scriptscriptstyle Y}}
\newcommand{\malyZ}{{\scriptscriptstyle Z}}
\newcommand{\smallworkfs}{{\scriptstyle\workfs{}}}
\newcommand{\smalld}{{b}}
\newcommand{\smallrm}{{\rm\small}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% delimiters %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\parend}[1]{{\left( #1  \right) }}
\newcommand{\spparend}[1]{{\left(\, #1  \,\right) }}
\newcommand{\angled}[1]{{\left\langle #1  \right\rangle }}
\newcommand{\brackd}[1]{{\left[ #1  \right] }}
\newcommand{\spbrackd}[1]{{\left[\, #1  \,\right] }}
\newcommand{\braced}[1]{{\left\{ #1  \right\} }}
\newcommand{\leftbraced}[1]{{\left\{ #1  \right. }}
\newcommand{\floor}[1]{{\left\lfloor #1\right\rfloor}}
\newcommand{\ceiling}[1]{{\left\lceil #1\right\rceil}}
\newcommand{\barred}[1]{{\left|#1\right|}}
\newcommand{\doublebarred}[1]{{\left|\left|#1\right|\right|}}
\newcommand{\spaced}[1]{{\ #1\ }}
\newcommand{\suchthat}{{\spaced{:}}}

\newcommand{\bracedtwo}[2]{\braced{\begin{array}{c}
                                        #1 \\ #2
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedtwo}[2]{\left\{\begin{array}{l}
                                        #1 \\ #2
                                    \end{array}\right.
                           }
\newcommand{\bracedthree}[3]{\braced{\begin{array}{c}
                                        #1 \\ #2 \\ #3
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedthree}[3]{\left\{\begin{array}{l}
                                        #1 \\ #2 \\ #3
                                    \end{array}\right.
                           }
\newcommand{\bracedfour}[4]{\braced{\begin{array}{c}
                                        #1 \\ #2 \\ #3 \\ #4
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedfour}[4]{\left\{\begin{array}{l}
                                        #1 \\ #2 \\ #3 \\ #4
                                    \end{array}\right.
                           }
%%%%%%%%%%%%%%% DO NOT ALLOW ANY LINE TO GO BEYOND THIS LINE %%%%%%%%%%%%%%%%%%
\newcommand{\bracedfive}[5]{\braced{\begin{array}{c}
                                        #1 \\ #2 \\ #3 \\ #4 \\ #5
                                    \end{array}
                                  }
                           }
\newcommand{\leftbracedfive}[5]{\left\{\begin{array}{l}
                                        #1 \\ #2 \\ #3 \\ #4 \\ #5
                                    \end{array}\right.
                           }

\newcommand{\mycase}[1]{\smallskip\noindent \mbox{Case #1:}}

\newcommand{\ignore}[1]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% environments %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}
\newtheorem{observation}{Observation}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{conjecture}{Conjecture}
\newenvironment{proof}{{\it Proof:\/}}{$\Box$\vskip 0.1in}
\newenvironment{example}{\medskip\noindent{\it Example:\/}}{$\Box$\vskip 0.1in}
\newenvironment{problem}{\medskip\noindent{\it Problem:\/}}{$\Box$\vskip 0.1in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% some general mathematical symbols %%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\half}{{\mbox{$\frac{1}{2}$}}}
\newcommand{\onehalf}{{\half}}
\newcommand{\threehalves}{{\mbox{$\frac{3}{2}$}}}
\newcommand{\onethird}{{\mbox{$\frac{1}{3}$}}}
\newcommand{\twothirds}{{\mbox{$\frac{2}{3}$}}}
\newcommand{\fourthirds}{{\mbox{$\frac{4}{3}$}}}
\newcommand{\fivethirds}{{\mbox{$\frac{5}{3}$}}}
\newcommand{\seventhirds}{{\mbox{$\frac{7}{3}$}}}
\newcommand{\onefourth}{{\mbox{$\frac{1}{4}$}}}
\newcommand{\fivefourths}{{\mbox{$\frac{5}{4}$}}}
\newcommand{\onesixth}{{\mbox{$\frac{1}{6}$}}}
\newcommand{\fivesixths}{{\mbox{$\frac{5}{6}$}}}
\newcommand{\sevensixths}{{\mbox{$\frac{7}{6}$}}}
\newcommand{\onetwelfth}{{\mbox{$\frac{1}{12}$}}}

\newcommand{\Comp}{{\parend{1+e^{-\malyhalf}}}}

\newcommand{\update}{{\wedge}}
\newcommand{\opt}{{\mbox{\it opt}}}
\newcommand{\cost}{{\mbox{\it cost}}}
\newcommand{\offset}{{\mbox{\it offset}}}
\newcommand{\back}{{\mbox{\it back}}}
\newcommand{\lood}{{\mbox{\it load}}}
\newcommand{\congestion}{{\mbox{\it congestion}}}
%%%%%%%%%%%%%%% DO NOT ALLOW ANY LINE TO GO BEYOND THIS LINE %%%%%%%%%%%%%%%%%%
\newcommand{\malyopt}{{\mbox{\tiny\it opt}}}
\newcommand{\adv}{{\mbox{\it adv}}}
\newcommand{\malyadv}{{\mbox{\tiny\it adv}}}

\newcommand{\eps}{\epsilon}
\newcommand{\adversary}{{\mbox{\it R}}}
\newcommand{\Exp}{{\mbox{\it Exp}}}
\newcommand{\reals}{{\bf R}}
\newcommand{\tendsto}{{\rightarrow}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%% Temporary macros %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%  \newcommand{\Ref}[1]{\ref{#1} {\rm \{#1\}}}
  \newcommand{\Ref}[1]{\ref{#1}}
%  \newcommand{\Cite}[1]{\cite{#1} {\rm \{#1\}}}
  \newcommand{\Cite}[1]{\cite{#1}}
% \newcommand{\Label}[1]{\label{#1} \mbox{$\backslash$ {\rm label\{#1\}}}}
  \newcommand{\Label}[1]{\label{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\renewcommand{\today}{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{Work Functions}
\author{Lawrence L Larmore}
%\maketitle
%\begin{abstract}
%potentials for online algorithms
%\end{abstract}
%{\bf Keywords:} online, competitiveness, potential \\

This version {\tt
Fri Nov 14 03:23:31 PST 2003
 }, and still under
construction.
%{\bf There are no changes from yesterday in the first eleven pages.
%There will be further changes before class today.}
%{\bf There will be further changes this weekend.}
{\bf There are no changes, as yet, from the Nov 7 version,
except for correction of typos found in class Thursday evening.}

\section*{Work Functions, Offsets, and Estimators}

Throughout, we assume that we are
given an online problem whose set of configurations is $\calX$,
whose set of requests is $\calR$, and whose start state is $s^\malyz$.
Recall that, for configurations $x,y\in\calX$ and request $r\in\calR$, we
let $\cost^r(x,y)$ denote the cost of servicing $r$ starting in configuration
$x$ and ending in configuration $y$.

\paragraph{The distance function.}
We assume that a {\em distance\/} $d(x,y)$ is defined for all
$x,y\in\calX$, satisfying the following conditions:
\begin{itemize}
\item
$d(x,x)=0$ for all $x\in\calX$.
\item
$d(x,z)\le d(x,y)+d(y,z)$
for all $x,y,z\in\calX$.
\item
$\cost^r(u,v)\le d(u,x)+\cost^r(x,y)+d(y,v)$
for all $u,x,y,v\in\calX$, and all $r\in\calR$.
\end{itemize}
In many, but not all, of our applications, the distance function is symmetric.

\paragraph{Connected.}
We say that the online problem is {\em connected\/} if $d(x,y)<\infty$
for all $x,y\in\calX$.

\paragraph{Finitely many choices.}
We say that the online problem {\em has finitely many choices in all
situations\/} if, for any state $x\in\calX$ and any $r\in\calR$, there
exists a finite set $Y$, which we call the {\em support of the configuration
request pair $(x,r)$}, such that, for any $z\in\calX$, there exists
$y\in Y$ such that $\cost^r(x,z) = \cost^r(x,y)+d(y,z)$.

\paragraph{Example: the distance function for the cache problem.}
Consider the $k$-cache problem, where $\calX$ is the set of all
subsets of order $k$ of some set of all possible pages.
If $x,y\in\calX$, define $d(x,y)$ to be the number of pages that
are in $x$ and not in $y$.  If $r$ is a request and $x,y\in\calX$,
we then define

\begin{eqnarray*}
\cost^r(x,y)=\leftbracedtwo{d(x,y)
{\mbox{\rm\ if\ }}r\in x {\mbox{\rm\ or\ }}r\in y}
{d(x,y)+1 {\mbox{\rm\ otherwise\ }}}
\end{eqnarray*}

\begin{exercise}{\rm
In the $k$-cache problem, prove that the cardinality of the minimal
support set for a configuration request pair is 1 if the
request is a hit, and is $k$ if the request is a fault.
}
\end{exercise}

\paragraph{Estimators.}
If $x,y\in\calX$, and if $\varrho\in\calR^*$ is a request sequence,
we let $\cost^\varrho_\malyopt(x,y)$ denote the minimum cost of servicing
$\varrho$ starting in configuration $x$ and ending at configuration $y$.
An {\em estimator\/} is a function $\omega:\calX\to\reals^*$ which
estimates total cost of servicing a given request sequence, where
$\reals^*$ denotes the real numbers together with $\infty$.
We say that an estimator $\omega$ has {\em zero minimum\/} if
$\min_{x\in\calX}\omega(x) = 0$.

A classic example of an estimator is the {\em work function\/} of a request
sequence.
If $\varrho$ is a request sequence, the classic {\em work function\/}
$\omega^\varrho:\calX\to\reals^*$ is defined by
$\omega^\varrho(x) = \cost^\varrho_\malyopt(s^\malyz,x)$.
If $\varrho$ is a request sequence, the classic {\em offset function\/} is
defined to be
$\bar\omega^\varrho = \omega^\varrho - \cost^\varrho_\malyopt(s^\malyz)$,
a zero minimum estimator.

\paragraph{The update operator.}
If $f:\calX\to\reals^*$ and if $r\in\calR$
is a request, we define
$f\update r(y) = \min_{x\in\calX} \braced{f(x) + \cost^r(x,y)}$.

\begin{lemma}\label{lem: update uses only support}
If $f$ is supported by $S$, then
$f\update r(y) = \min_{x\in S} \braced{f(x) + \cost^r(x,y)}$.
\end{lemma}

\begin{exercise}{\rm 
Prove Lemma \ref{lem: update uses only support}.
}
\end{exercise}

\begin{observation}\label{obs: update work}
If $\varrho = r^1\ldots r^n$, let $\varrho^t = r^1\ldots r^t$.
Then
\begin{enumerate}
\item
$\omega^\malyz(x)=d(s^\malyz,x)$ for all $x\in\calX$.
\item
$\omega^{\varrho^t} = \omega^{\varrho^{t-1}}\update r^t$
for all $t > 0$.
\end{enumerate}
\end{observation}
We call $\omega^\malyz$ the {\em initial work function\/}.

% \begin{exercise}{\rm 
% If $x,y,v\in\calX$ and $r\in\calR$,
% then $\inf_{u\in\calX}\braced{\cost^r(x,u)+d(u,v)}\le d(x,y)+\cost^r(y,v)$.
% }
% \end{exercise}

\begin{observation}\label{obs: opt}
If $x,y\in\calX$ and $\varrho$ is a request sequence, then
$\cost^\varrho_\malyopt(y) \le \cost^\varrho_\malyopt(x)+d(x,y)$
\end{observation}

We say that a function $f:\calX\to\reals^*$ is {\em Lipschitz\/} if
$f(y)\le f(x)+d(x,y)$ for all $x,y\in\calX$.
%Write $L(f)$ for the unique maximal Lipschitz function with $L(f)\le f$.
We say that a function $f:\calX\to\reals^*$ is {\em supported by\/}
$S\subseteq\calX$ if $f(y)\ge\inf_{x\in S}\braced{f(x)+ d(x,y)}$
for all $y\in\calX$.  We say that $f$ {\em has finite support\/} if
it is supported by a finite set.  If $f$ has finite support, then there
is a unique minimal finite set $S$ which supports $f$.


\begin{exercise}{\rm
For any request sequence $\varrho$, the work function $\omega^\varrho$
is Lipschitz.
}
\end{exercise}

\begin{exercise}{\rm
If the problem has finitely many choices in all situations, then,
for any request sequence $\varrho$, the work function $\omega^\varrho$
has finite support.
}
\end{exercise}

\begin{exercise}\label{ex: abcde}{\rm
Consider the 3-cache problem.  Assume that the initial cache is
$\braced{a,b,c}$.  Let $\varrho = dbcebacb$.
\begin{enumerate}
\item
Compute the work function at each step.
(Your answer should be a table with 9 rows and 10 columns.)
\item
Compute the classic offset function and the offset at each step.
(Your answer should be a table with 9 rows and 11 columns.)
\item
Write the bar notation for the classic offset function at each step.
(See Exercise \ref{ex: bar abcde} below.)
\end{enumerate}
}
\end{exercise}

\subsection*{Work Function Algorithms are Optimal}
There are two major theorems involving work functions, both of which
say, in essence, that the work function is all that an online algorithm
needs to remember.

\begin{theorem}\label{thm: work all det}
Let $\calA$ be a $C$-competitive deterministic online algorithm.
Then, there is a $C$-competitive deterministic online algorithm $\calA'$
such that, after serving any request sequence $\varrho$, the memory state of
$\calA'$ is $\omega^\varrho$.
\end{theorem}

\begin{theorem}\label{thm: work all dist}
Let $\calA$ be a $C$-competitive distributional online algorithm.
Then, there is a $C$-competitive distributional online algorithm $\calA'$
such that, after serving any request $\varrho$, the memory state of
$\calA'$ is $\omega^\varrho$.
\end{theorem}

In both Theorem \ref{thm: work all det} and \ref{thm: work all dist},
note that $\calA'$ need only remember the values of the work function on
its support.  The support set of the classic work function is always
finite if the problem allows only finitely many choices, although its
size can grow with the length of the request sequence.

\subsubsection*{WFA}
The {\em work function algrithm\/}, usually written WFA, is defined as
follows.  Let $\varrho = r^1\ldots r^t$ be the request sequence of to
step $t$.  If $s^{t-1}$ is the configuration at step $t-1$, WFA chooses
$s^t$, the configuration at step $t$, so as to minimize
$\cost^{r^t}(s^{t-1},s^t)+\omega^\varrho(s^t)$.  In case there is more than
one choice of $s^t$, WFA chooses one arbitrarily.\footnote{In the analysis,
we must assume that the adversary makes that choice.}

\subsection*{Estimators and Offsets}

We use {\em estimators\/} and {\em offsets\/} to analyze the competitiveness
of an online algorithm $\calA$.  More specifically, the combination of
estimators and offsets allows us to estimate the optimal cost, or
the adversary's cost, as the case may be.  An online algorithm does not
know the adversary's cost at any given time, but can keep track of
the estimator, and use it as a guide.  The estimator is a real-valued
function on configurations that is updated at every step, while the
offset is a real number that is computed at every step.  Both the
estimator and the offset can be calculated using randomization.
We now give the formal definitions.

An {\em estimator-offset system\/} is a behavioral online algorithm
that reads a request sequence $\varrho$ and computes an estimator
$\omega^t:\calX\to\reals$ and an offset $\offset^t\in\reals$ at each step.
Since the system may use randomization, both $\omega^t$ and $\offset^t$
are random variables.

Let $r^t$ be the request at step $t$.
Let $\omega^{t-1}$ be the estimator after $t-1$ steps.
The estimator-offset system must satisfy the following two conditions:
\begin{enumerate}
\item
$\omega^\malyz$ must be the initial work function.
\item
For each $x\in\calX$, the following must hold:
\begin{eqnarray}
E\parend{\omega^t(x)}+\offset^t&\le&
(\omega^{t-1}\update r^t)(x)
\label{eqn: las vegas update}
\end{eqnarray}
\end{enumerate}
Note that the expected value used in
(\ref{eqn: las vegas update}) is in fact a conditional expected value.
We do not write the expected value of $\offset^t$, since that quantity
is deterministicly computed from $\omega^{t-1}$ and $r^t$.

\begin{theorem}\label{thm: est-opt}
Given an estimator-offset system, and given a request sequence
$\varrho = r^1\ldots r^n$, then for all $x\in\calX$
\begin{eqnarray*}
E\parend{\omega^n(x)+\sum^n_{t=1}\offset^t}
&\le&
\cost_\malyopt^\varrho(s^\malyz,x)
\label{eqn: total opt}
\end{eqnarray*}
\end{theorem}

\begin{proof}
Let
$\varrho = r^1\dots r^n$ be any request sequence, and let
 $s^\malyz=x^\malyz,x^\malyone,\ldots x^n=x\in\calX$ be the optimal service
of $\varrho$ that ends in $x$.
\begin{eqnarray*}
 {\mbox{\rm Thus:}}&&\\
 \sum^n_{t=1}\cost^{r^t}(x^{t-1},x^t)
 &=&\cost_\opt(s^\malyz,x)\\
 {\mbox{\rm By (\ref{eqn: las vegas update}):}}&&\\
 E\parend{\omega^t(x^t)+\offset^t}
 &\le&
 E\parend{\parend{\omega^{t-1}\update r^t}(x^t)}{\mbox{\rm\ for all\ }}t\\
%{\mbox{\rm Since $\calA$ is $C$-competitive}}
%&&{\mbox{\rm as a knowledge state algorithm:}}\\
%E(\sum^n_{t=1}\cost^t_\calA
%&\le&
%C\cdot E(\sum^n_{t=1}\offset^t+
%C\cdot E(\omega^n(x^n))+K\\
 {\mbox{\rm By the definition of the update operator:}}
 &&\\
E\parend{\parend{\omega^{t-1}\update r^t}(x^t)}
 &\le&
 E\parend{\omega^{t-1}(x^{t-1})}+\cost^{r^t}(x^{t-1},x^t)
{\mbox{\rm\ for all\ }}t
\end{eqnarray*}
Summing the inequalities over all $t$, and adding to the equation,
we obtain the result.
\end{proof}

\subsubsection*{Knowledge State Algorithms}

A {\em knowledge state algorithm\/} is a mixed online algorithm
that also maintains an update-offset system, and uses the current estimator
as its memory state.  More formally, if
$\calA$ is a knowledge-state algorithm, then:
\begin{itemize}
\item
At any given time, the full state of $\calA$ is a pair $(\pi,\omega)$,
where $\pi$ is a distribution on $\calX$ and $\omega:\calX\to\reals$
is the current estimator.  We call that pair the {\em current knowledge
state.}
\item
If $(\pi,\omega)$ is the current knowledge state and $x\in\calX$,
then $\omega(x)\ge 0$.
\item
If $(\pi,\omega)$ is the knowledge state and the next request is $r$,
then $\calA$ computes an offset $\offset$ and uses randomization to pick
a new knowledge state
$(\pi',\omega')$.  In particular, there are knowledge state
$(\pi_i,\omega_i)$ and probabilities $\lambda_i$ for $i=1,\ldots m$
such that
\begin{enumerate}
\item
For each $i$, $\calA$ chooses $(\pi_i,\omega_i)$ to be its new knowledge state
with probability $\lambda_i$.
\item
$(\omega\update r)(x) \ge \offset + \sum^m_{i=1}\lambda_i\omega_i(x)$
\item
Define the {\em cost\/} of that step to be
$\cost^r(\pi,\sum^m_{i=1}\lambda_i\pi(x))$.
\end{enumerate}
We refer to the $\braced{(\pi_i,\omega_i)}$ as the {\em subsequents\/}
and to $\braced{\lambda_i}$ as the {\em distribution on the subsequents}.
\end{itemize}

\paragraph{Support.}
If $S\subseteq\calX$, we say that a knowledge state $(\pi,\omega)$
is {\em supported by $S$} if $\omega$ is supported by $S$ and $\pi(S)=1$.
Note that, if $S$ is finite, $(\pi,\omega)$ can be represented by the finite
set of triples $\braced{(x,\pi(x),\omega(x)}_{x\in S}$.  We say that a
knowledge state algorithm {\em has finite support\/} if, for some $k$,
each of its knowledge states is supported by a set of cardinality at most $k$.


\paragraph{Competitiveness.}
%Let $\calA$ be a knowledge state algorithm.
We say that {\em $\calA$ is $C$-competitive as a knowledge state algorithm\/}
if there is a constant $K$ such that
$E\parend{\sum^n_{t=1}\cost^t}\le
C\cdot{}E\parend{\sum^n_{t=1}\offset^t+\omega^n(x)}+K$
for any request sequence $\varrho = r^1\dots r^n$ and any $x\in\calX$,
where $\cost^t$, $\offset^t$, and $\omega^t$
are the cost, offset, and estimator, respectively,
of $\calA$ at step $t$ given that $\varrho$ is the request sequence.
Note that $\cost^t$ and $\offset^t$ are
real-valued random variables.

We say that {\em $\calA$ is $C$-competitive as a knowledge state algorithm\/}
against an adversary $\adv$
if there is a constant $K$ such that
$E\parend{\sum^n_{t=1}\cost^t}\le
C\cdot{}E\parend{\sum^n_{t=1}\offset^t+\omega^n(x)}+K$
for any $x\in\calX$,
where $\cost^t$, $\offset^t$, and $\omega^t$
are the cost, offset, and estimator, respectively,
of $\calA$ at step $t$ given the adversary $\adv$.
Note that $\cost^t$ and $\offset^t$ are
real-valued random variables.

\begin{theorem}
\begin{enumerate}
\item
\label{thm case: opt}
If a knowledge state algorithm $\calA$ is $C$-competitive
as a knowledge state algorithm, then $\calA$ is $C$-competitive as a
mixed online algorithm.
\item
\label{thm case: adv}
If a knowledge state algorithm $\calA$ is $C$-competitive
as a knowledge state algorithm against a given adversary $\adv$,
then $\calA$ is $C$-competitive as a mixed online algorithm against $\adv$.
\end{enumerate}
\end{theorem}

\begin{proof}
We do part \ref{thm case: opt} first.
Let $K$ be the constant given in the definition of $C$-competitiveness
for a knowledge state algorithm.
Let
$\varrho = r^1\dots r^n$ be any request sequence, and let
 $s^\malyz=x^\malyz,x^\malyone,\ldots x^n\in\calX$ be the optimal service
of $\varrho$.
% Let $\cost_\opt^t=\cost^{r^t}(x^{t-1},x^t)$, the cost of
% the optimal offline algorithm at step $t$.
\begin{eqnarray*}
% {\mbox{\rm Since $\calA$ is a knowledge state algorithm:}}&&\\
% E\parend{\parend{\omega^{t-1}\update r^t}(x^t)}
% &\ge&
% E\parend{\omega^t(x^t)}{\mbox{\rm\ for all\ }}t\\
{\mbox{\rm Since $\calA$ is $C$-competitive}}
&{\mbox{\rm\hskip-2mm as a\hskip-2mm}}&
{\mbox{\rm knowledge state algorithm:}}\\
E\parend{\sum^n_{t=1}\cost^t_\calA}
&\le&
C\cdot E\parend{\sum^n_{t=1}\offset^t}+
C\cdot E\parend{\omega^n(x^n))}+K\\
{\mbox{\rm By Theorem \ref{thm: est-opt}:}}&&\\
E\parend{\sum^n_{t=1}\offset^t+\omega^n(x^n)}
&\le&
\cost_\opt^\varrho\\
{\mbox{\rm Combining the above, we obtain:}}
&&\\
E\parend{\sum^n_{t=1}\cost^t_\calA}
&\le&
C\cdot\cost_\opt+K
\end{eqnarray*}
\end{proof}

In our discussion, we simply say ``$\calA$ is $C$-competitive," to mean that
$\calA$ is $C$-competitive as a knowlege state algorithm.

\paragraph{Absolute competitiveness and potentials.}
We say that $\calA$ is {\em absolutely $C$-competitive\/} if
$\cost\le C\cdot\offset$.  Note the absence
of expected value in this inequality; it means that, for all $t$, the random
variable $C\cdot\offset^t-\cost^t$ is non-negative with probability 1, not
merely that it has a non-negative expected value.  Trivially, if
$\calA$ is absolutely $C$-competitive it is $C$-competitive.

We now define a {$C$-potential\/} for a knowledge state algorithm $\calA$.
Let $\Phi$ be a real-valued function on knowledge states.
If $(\pi,\omega)$ is the current knowledge state and $r$ is the next request,
$\braced{(\pi_i,\omega_i)}$ are the {\em subsequents\/}, and
$\braced{\lambda_i}$ is the {\em distribution on the subsequents}, write
$\Delta\Phi = \sum^m_{i=1}\lambda_i\Phi(\pi_i,\omega_i)-\Phi(\pi,\omega)$.
Given a request sequence, let $\Delta^t\Phi$ be the value of $\Delta\Phi$
at step $t$, a random variable.
Then we say that $\Phi$ is a {\em knowlege state $C$-potential for $\calA$\/}
if
\begin{itemize}
\item
$\Phi(\omega,\pi)+C\cdot\omega(x)\ge 0$ for any knowledge state
$(\omega,\pi)$ and for any $x\in\calX$.
\item
 $cost+\Delta\Phi\le C\cdot\offset$.
\end{itemize}
As above, we do not use expected values.
Instead, the second condition means that, for all $t$, the random variable
$C\cdot\offset^t-\cost^t-\Delta^t\Phi$ is non-negative with probability 1.

\begin{theorem}
If a knowledge state algorithm $\calA$ has a knowledge state $C$-potential,
then $\calA$ is $C$-competitive as a knowledge state algorithm.
\end{theorem}

% \begin{proof} [By reduction to absolute competitiveness.]
% Let $\Phi$ be a knowledge state $C$-potential for $\calA$.
% Define a knowledge state algorithm $\calA'$ as follows: if
% $(\pi,\omega)$ is the current knowledge state of $\calA$, and if
% $\Phi = \Phi(\pi,\omega)$ is the current potential, then
% the current knowledge state of $\calA'$ is
% $(\pi,\omega+\frac{\Phi}{C})$.
% It is easily verified that $\calA'$ is absolutely $C$-competitive.
%   Since $\calA'$ has the same distributions
% as $\calA$, it has the same costs as $\calA$.
% Let $\Phi^t$ be the value of $\Phi$ at step $t$, a random variable.
% Then, by collapsing the series, we have that
% $C\cdot E\parend{\sum^n_{t=1}(\offset^t-(\offset')^t)}\ge E(\Phi^n)-\Phi^0$.
% Note that $\Phi^0$ is a constant.
% It follows immediately that $\calA$ is $C$-competitive, where $\Phi^0$
% is used for $K$ in the definition.
% {\sc Is there an error in this proof?}
% \end{proof}

\begin{proof}% [Direct proof.]
Let $\Phi^t$ be the value of $\Phi$ at step $t$, a random variable.
Note that $\Phi^0$ is a constant.  Let $\Delta^t\Phi$
be the value of $\Delta\Phi$ at step $t$, a random variable.
Let $x\in\calX$.  Then
\begin{eqnarray*}
C\cdot E\parend{\omega^n(x)+\sum^n_{t=1}\offset^t}
-E\parend{\sum^n_{t=1}\cost^t}&=&\\
E\parend{C\cdot\omega^n(x)+\sum^n_{t=1}\parend{C\cdot\offset^t-\cost^t}}&=&\\
E\parend{C\cdot\omega^n(x)+\Phi^n+\sum^n_{t=1}\parend{C\cdot\offset^t-\cost^t
-\Delta^t\Phi}}-\Phi^0&\ge&\\
E\parend{C\cdot\omega^n(x)+\Phi^n}-\Phi^0&\ge&-\Phi^0
\end{eqnarray*}
It follows that
$E\parend{\sum^n_{t=1}\cost^t}\le
C\cdot E\parend{\omega^n(x)+\sum^n_{t=1}\offset^t}+\Phi^0$,
and we are done.
{\sc Need to check over this proof once more.}
\end{proof}

\subsection*{Forgiveness}

We can define a {\em forgiveness\/} online algorithm to be a knowledge
state algorithm with the special restriction that there is always
exactly one subsequent.\footnote{Historically, forgiveness came first,
so we can think of the knowledge state approach as being a generalization
of forgiveness.}  A forgiveness algorithm can be deterministic,
such as EQUIPOISE, a deterministic online 11-competitive algorithm for the
3-server problem (that was the best known competitiveness for that problem at
that time), or distributional, such as EQUITABLE, an $H_k$-competitive
distributional online algorithm for the $k$-cache problem.

\subsubsection*{Stable Distribution Algorithms}
Prior to the introduction of knowledge state algorithms, a {\em
stable distribution algorithm\/} was defined to be a function
which assigned to every classic offset function $\omega$ a
distribution $\pi^\omega$.  This function specifies a distributional
online algorithm $\calA$ as follows.  The memory state of $\calA$
is always the classic offset function, namely $\bar{\omega^\varrho}=
\omega^\varrho - \min_{x\in\calX}\omega^\varrho(x)$, where $\varrho$
is the request sequence so far.  The distribution of $\calA$ is always
$\pi^{\bar{\omega^\varrho}}$.

The definition of a stable distribution algorithm naturally extends
to knowledge state algorithms, as follows.  The rule then is that
for each zero minimum estimator $\omega$ there is a given distribution
$\pi^\omega$, and that every knowledge state is of the form
$(\omega,\pi^\omega)$ for some zero minimum estimator $\omega$.

\subsection*{A $\frac{3}{2}$-Competitive Knowledge State Algorithm
for the 2-Cache Problem}
We now show how the use of knowledge states simplifies the definition,
and in fact the memory requirement, of an optimally competitive
randomized algorithm for the 2-cache problem.

Recall that PARTITION is optimally competitive for the $k$-cache problem,
but uses unbounded memory to achieve the optimal competitiveness of $H_k$.
The memory state of PARTITION is, in fact, the classic work function,
which, in the worst case, requires keeping track of every past request.

We define here a knowledge state algorithm $K_2$ for the 2-cache problem.
Each knowledge state of $K_2$ is supported by a set of cardinality at
most 2.

For the $k$-cache problem, the distance function is the number of
different pages.  That is, if $x,y\in\calS$ are $k$-sets,
$d(x,y)$ is the number of pages in $x$ which are not in $y$.

\subsubsection*{Knowledge States of $K_2$. [Absolutely Competitive Version]}

As we saw above,
any knowledge state algorithm with a potential can be replaced by an
equivalent knowledge state algorithm which is absolutely competitive.
We will use the absolutely competitive version of $K_2$ in order to
simplify the proofs.

If there are infinitely many pages,
$K_2$ has infinitely many knowledge states, but, up to
symmetry, it has only two.

\begin{enumerate}
\item
If $a,b$ are pages, define
 $A^{a,b}=(\alpha^{a,b},[a,b])$ to be the knowledge state supported by 
by the configuration $\braced{a,b}$, where $\alpha^{a,b}(\braced{a,b})=0$.
Note that $[a,b]$ is the distribution concentrated on $\braced{a,b}$.
\item
If $a,b,c$ are pages, let
$B^{a,b,c}=(\beta^{a,b,c},\onehalf[a,b]+\onehalf[a,c])$, a knowledge
state supported by $\braced{\braced{a,b},\braced{a,c}}$, where
$\beta^{a,b,c}(\braced{a,b})=\beta^{a,b,c}\braced{a,c}=\onethird$.
\end{enumerate}
Note that $A^{a,b}=A^{b,a}$ and $B^{a,b,c}=B^{a,c,b}$.

\subsubsection*{Action of $K_2$. [Absolutely Competititive Version]}

\begin{itemize}
\item
If $\braced{a,b}$ is the initial cache,
the initial knowledge state is $A^{a,b}$, 
\item
If the current knowledge state is $A^{a,b}$ and the new request
is $a$, the new knowledge state is $A^{a,b}$, 
$\offset = 0$, and $\cost=0$.
\item
If the current knowledge state is $A^{a,b}$ and the new request is some
page $c\notin\braced{a,b}$, then the new knowledge state is $B^{c,a,b}$,
$\offset = \twothirds$, and $\cost=1$.
\item
If the current knowledge state is $B^{a,b,c}$ and the new request
is $a$, the new knowledge state is $B^{a,b,c}$, $\offset = 0$, and $\cost=0$.
\item
If the current knowledge state is $B^{a,b,c}$ and the new request
is $b$, the new knowledge state is $A^{b,a}$, $\offset = \onethird$,
and $\cost=\onehalf$.
\item
If the current knowledge state is $B^{a,b,c}$ and the new request is some
page $d\notin\braced{a,b,c}$, then there are three subsequents, namely
$A^{d,a}$, $A^{d,b}$, and $A^{d,c}$.  The distribution
on these subsequents is uniform, \ie, each is chosen with probability
$\onethird$. Then $\offset = \twothirds$ and $\cost=1$.
\item All other actions are symmetric to one of the above.
\end{itemize}

\begin{theorem}\label{thm: k2 abs comp}
$K_2$ is absolutely $\threehalves$-competitive.
\end{theorem}

\begin{proof}
We first note that, for distinct pages $a$, $b$, $c$, $d$:
(Recall that $\alpha^{a,b}=\alpha^{b,a}$ and $\beta^{a,b,c}=\beta^{a,c,b}$.)
\begin{eqnarray*}
\alpha^{a,b}\update a&=&\alpha^{a,b}\\
\alpha^{a,b}\update b&=&\alpha^{a,b}\\
\alpha^{a,b}\update c&=&\beta^{c,a,b}+\twothirds\\
\beta^{a,b,c}\update a&=&\beta^{a,b,c}\\
\beta^{a,b,c}\update b&=&\alpha^{a,b}+\onethird\\
\beta^{a,b,c}\update c&=&\alpha^{a,c}+\onethird\\
\beta^{a,b,c}\update d&\ge&\onethird\alpha^{a,d}+
\onethird\alpha^{b,d}+\onethird\alpha^{c,d}+\twothirds
\end{eqnarray*}
The last inequality need only be verified for configurations
in $\braced{\braced{a,d},\braced{b,d},\braced{b,d}}$, the support
set of $\beta^{a,b,c}\update d$.

Let $K$ be the current knowledge state and $r$ the new request.

\mycase{$K=A^{a,b}$ and $r=a$ or $r=b$}.

This case is trivial since the new knowledge state is $K$, $\cost = 0$ and
$\offset = 0$.

\mycase{$K=B^{a,b,c}$ and $r=a$}.

This case is trivial since the new knowledge state is $K$, $\cost = 0$ and
$\offset = 0$.

\mycase{$K=A^{a,b}$ and $r=c\notin\braced{a,b}$}.

$\alpha^{a,b}\update c = \beta^{c,a,b}+\twothirds$, thus $\offset =
\twothirds$. Since $\cost = 1$, we are done.

\mycase{$K=B^{a,b,c}$ and $r=b$ or $r=c$}.

Without loss of generality, $r=b$.  Since $\beta^{a,b,c}\update b =
\alpha^{b,a}+\onethird$, we can let $\offset = \onethird$.
Since $\cost=\onehalf$, we are done.

\mycase{$K=B^{a,b,c}$ and $r=d\notin\braced{a,b,c}$}.

$\beta^{a,b,c}\update d$ is supported by the three configurations
$\braced{d,a}$,
$\braced{d,b}$, and
$\braced{d,c}$, and takes on the value $\fourthirds$ on each of those.
Since $\offset=\twothirds$ and $\cost=1$, we are done.

This completes the proof of all cases.
\end{proof}

\subsubsection*{Knowledge States of $K_2$. [Zero Minimum Version]}

We will follow the classic rule that, at each step, the offset is
as large as possible, so that the minimum of the estimator will always
be zero.  This guarantees that any potential will always be non-negative.
In this description, $K_2$ is a stable distribution algorithm.

If there are infinitely many pages,
$K_2$ has infinitely many knowledge states, but, up to
symmetry, it has only two.

\begin{enumerate}
\item
If $a,b$ are pages, define
 $A^{a,b}=(\alpha^{a,b},[a,b])$ to be the knowledge state supported by 
by the configuration $\braced{a,b}$, where $\alpha^{a,b}(\braced{a,b})=0$.
Note that $[a,b]$ is the distribution concentrated on $\braced{a,b}$.
\item
If $a,b,c$ are pages, let
$B^{a,b,c}=(\beta^{a,b,c},\onehalf[a,b]+\onehalf[a,c])$, a knowledge
state supported by $\braced{\braced{a,b},\braced{a,c}}$, where
$\beta^{a,b,c}(\braced{a,b})=\beta^{a,b,c}\braced{a,c}=0$.
\end{enumerate}
Note that $A^{a,b}=A^{b,a}$ and $B^{a,b,c}=B^{a,c,b}$.

\subsubsection*{Action of $K_2$. [Zero Minimum Version]}

\begin{itemize}
\item
If $\braced{a,b}$ is the initial cache,
the initial knowledge state is $A^{a,b}$, 
\item
If the current knowledge state is $A^{a,b}$ and the new request
is $a$, the new knowledge state is $A^{a,b}$, $\offset = 0$,
and $\cost=0$.
\item
If the current knowledge state is $A^{a,b}$ and the new request is some
page $c\notin\braced{a,b}$, then the new knowledge state is $B^{c,a,b}$,
$\offset = 1$, and $\cost=1$.
\item
If the current knowledge state is $B^{a,b,c}$ and the new request
is $a$, the new knowledge state is $B^{a,b,c}$, $\offset = 0$,
and $\cost=0$.
\item
If the current knowledge state is $B^{a,b,c}$ and the new request
is $b$, the new knowledge state is $A^{b,a}$, $\offset = 0$,
and $\cost=1$.
\item
If the current knowledge state is $B^{a,b,c}$ and the new request is some
page $d\notin\braced{a,b,c}$, then there are three subsequents, namely
$A^{d,a}$, $A^{d,b}$, and $A^{d,c}$.  The distribution
on these subsequents is uniform, \ie, each is chosen with probability
$\onethird$. Then $\offset = \onethird$.
\item All other actions are symmetric to one of the above.
\end{itemize}

\begin{theorem}\label{thm: k2 comp pot}
$K_2$ is $\threehalves$-competitive.
\end{theorem}

\begin{proof}
Define $\Phi(A^{a,b})=0$ and $\Phi(B^{a,b,c})=\onehalf$.  We will
show that $\Phi$ is a $\threehalves$-potential for $K_2$.
Let $K$ be the current knowledge state and $r$ the new request.
We will show that $\cost+\Delta\Phi \le \threehalves\offset$
in all cases.

We first note that, for distinct pages $a$, $b$, $c$, $d$:
(Recall that $\alpha^{a,b}=\alpha^{b,a}$ and $\beta^{a,b,c}=\beta^{a,c,b}$.)
\begin{eqnarray*}
\alpha^{a,b}\update a&=&\alpha^{a,b}\\
\alpha^{a,b}\update b&=&\alpha^{a,b}\\
\alpha^{a,b}\update c&=&\beta^{c,a,b}+1\\
\beta^{a,b,c}\update a&=&\beta^{a,b,c}\\
\beta^{a,b,c}\update b&=&\alpha^{a,b}\\
\beta^{a,b,c}\update c&=&\alpha^{a,c}\\
\beta^{a,b,c}\update d&\ge&\onethird\alpha^{a,d}+
\onethird\alpha^{b,d}+\onethird\alpha^{c,d}+\onethird
\end{eqnarray*}
The last inequality need only be verified for configurations
in $\braced{\braced{a,d},\braced{b,d},\braced{b,d}}$, the support
set of $\beta^{a,b,c}\update d$.

\mycase{$K=A^{a,b}$ and $r=a$ or $r=b$}.

This case is trivial since the new knowledge state is $K$, $\cost = 0$,
$\offset = 0$, and $\Delta\Phi=0$.

\mycase{$K=B^{a,b,c}$ and $r=a$}.

This case is trivial since the new knowledge state is $K$, $\cost = 0$,
$\offset = 0$, and $\Delta\Phi=0$.

\mycase{$K=A^{a,b}$ and $r=c\notin\braced{a,b}$}.

$\alpha^{a,b}\update c = \beta^{c,a,b}+1$, thus $\offset = 1$.
Note $\cost = 1$ and $\Delta\Phi = \onehalf$, and we are done.

\mycase{$K=B^{a,b,c}$ and $r=b$ or $r=c$}.

Without loss of generality, $r=b$.  Since $\beta^{a,b,c}\update b =
\alpha^{b,a}$, we can let $\offset = 0$.
Note $\cost=\onehalf$ and $\Delta\Phi= -\onehalf$, and we are done.

\mycase{$K=B^{a,b,c}$ and $r=d\notin\braced{a,b,c}$}.
since $\beta^{a,b,c}\update d\ge\onethird\alpha^{a,d}+
\onethird\alpha^{b,d}+\onethird\alpha^{c,d}+\onethird$,
we can let $offset=\onethird$.
Note $\cost=1$ and $\Delta\Phi = -\onehalf$, and we are done.

This completes the proof of all cases.
\end{proof}

\subsection*{Bar Notation for the Cache Problem}

We consider the $k$-cache problem.  The ``bar notation," developed
by [{\sc names}] is a form of notation used to describe certain estimators
for that problem.

If $\omega$ is an estimator, we say that a page $a$ is {\em active for
$\omega$} (or just ``active" if $\omega$ is understood)
if $a$ is a member of some member of the support of $\omega$.
A bar description is a string of symbols, each of which is either
the name of a page or a bar.  We call a maximal substring of page
names in a bar description a {\em block\/}.
A bar description must satisfy the following rules:
\begin{itemize}
\item
The page names are distinct.
\item
There are exactly $k$ bars.
\item
The last symbol is a bar.
\item
There are at least $i$ page names before the $i^\tH$ bar.
\item
If the first $i$ symbols are page names, the next $i$ symbols are bars.
\item
If there are exactly $i$ page names in a block, and if the block is
preceded by a bar, then the block cannot be followed by $i$ consecutive bars.
\end{itemize}

In the examples below, we let lower case letters represent page names.

Examples for $k=2$: $ab||$, $a|bc|$, $a|bcd|$, $a|bcde|$, \ldots\ .
Examples for $k=3$: $abc|||$, $ab||cd|$, $ab||cde|$, $ab||cdef|$, \ldots\ ,
$a|bcd||$, $a|bcde||$, \ldots, $a|bc|de|$, $a|bc|def|$, \ldots\ ,
$a|bcd|ef|$, $a|bcd|efg|$, \dots\ .
Examples for $k=6$: $abcdef||||||$, $abc|||def||gh|$, $a|bcde|fgh||ij|klmn|$.

\paragraph{The meaning of the bar notation.}
Each bar description is the name of an estimator $\omega$
with finite support $S$, defined as follows.
\begin{itemize}
\item
$\omega(x) = 0$ for each $x\in S$.
\item
Define $S_i$ to be the set of all pages whose names appear before
the $i^\tH$ bar in the in the bar description.
If $x$ is a set of $k$ pages, then $x\in S$ if and only if $x\cap S_i$
has cardinality at least $i$, for each $i$.
\end{itemize}
Note that A page is active for $\omega$ if and only if its name appears in
the bar description.

Note that the page names in any given block can be permuted, for
example, $ab||cde| = ab||ced| = ba||dec| \ldots $.

Example for $k=3$: Let $\omega=a|bc|de|$.  Then $S_1=\braced{a}$,
$S_2=\braced{a,b,c}$, and $S_3=\braced{a,b,c,d,e}$.
Then $S=\braced{\braced{a,b,c},\braced{a,b,d},\braced{a,b,e},
\braced{a,c,d},\braced{a,c,e}}$.

\begin{exercise}\label{ex: bar k2}{\rm
Give bar descriptions of the estimators used for $K_2$.
}
\end{exercise}

\begin{exercise}\label{ex: bar abcde}{\rm
Write bar descriptions for all the offset functions you computed
for Exercise \ref{ex: abcde}.
}
\end{exercise}

\begin{exercise}\label{ex: programming bar}{\rm
Write a computer program that works Exercise \ref{ex: bar}
automatically; \ie, with input a bar description and a request,
it computes the new bar description.
}
\end{exercise}

The following theorem guarantees that the bar notation is sufficient
to describe any work function for the $k$-cache problem.

\begin{theorem}\label{thm: bar}
Let $\varrho$ be any request sequence for the $k$-cache problem.
then $\omega^\varrho = \omega' + \cost^\varrho_\opt$,
where $\omega'$ is an estimator which has a bar description.
\end{theorem}

Theorem \ref{thm: bar} follows immediately from the following lemma.

\begin{lemma}\label{lem: bar one step}
Suppose that $\omega$ is an estimator for the $k$-cache problem which
has a bar description, and suppose $r$ is a page.  Let $\offset=0$
if $r$ is active for $\omega$, and let $\offset = 1$ otherwise.
then $\omega\update r = \omega'+\offset$
where $\omega'$ is an estimator which has a bar description.
\end{lemma}

The proof of Theorem \ref{thm: bar} is given in the original paper
which introduces PARTITION.  {\sc Need to give a citation here.}

To ``confirm" Lemma \ref{lem: bar one step}, work the following
exercise.

\begin{exercise}\label{ex: bar}{\rm
For each of the examples given above, write the bar notation
for $\omega\update r$ for each active page $r$.
For instance, $a|bc|de|\update d = ad||bc|$.

For each of the examples given above, write the bar notation
for $\omega\update r - 1$ if $r$ is not an active page.
For instance, $a|bc|de|\update f = f|abc|de| + 1$ .
}
\end{exercise}

\begin{exercise}\label{ex: partition stable}{\rm
For $k=2$ and $k=3$ only, describe PARTITION as a stable
distribution algorithm by giving the distribution $\pi^\omega$ for
each $\omega$ which has a bar description.   (There are infinitely
many such $\omega$, even up to symmetry.)  We actually did the case
$k=2$ in class.  For $k=3$, you might want to consult the original paper.
}
\end{exercise}


\subsection*{An Optimally Competitive Knowledge State Algorithm
for the 3-Cache Problem}
We define a knowledge state algorithm $K_3$ which is $H_3$-competitive
for the 3-cache problem.  Recall that $H_3=\frac{11}{6}$.

Up to symmetry, $K_3$ has seven knowledge states.  The number of active
pages, \ie, pages contained in a support configuration, is never more
than five.  The number five is minimal in the following sense:
no knowledge state algorithm for the 3-cache problem which
always has fewer than five active pages can be $\frac{11}{6}$-competitive
as a knowledge state algorithm.

\paragraph{Knowledge states of $K_3$.}
The knowledge states of $K_3$ will be defined as follows.
\begin{enumerate}
\item
$A^{a,b,c}=\parend{abc||,[abc]}$ for any three pages $a,b,c$.
\item
$B^{a,b,c,d}=\parend{a|bcd||,\onethird[abc]
+\onethird[abd]+\onethird[acd]}$ for any four pages $a,b,c,d$.
\item
$C^{a,b,c,d}=\parend{ab||cd|,\onehalf[abc]
+\onehalf[abd]}$ for any four pages $a,b,c,d$.
\item
$D^{a,b,c,d,e}=\parend{a|bcde||,\onesixth[abc]+\onesixth[abd]
+\onesixth[abe]+\onesixth[acd]+\onesixth[ace] +\onesixth[ade]}$
for any five pages $a,b,c,d,e$.
\item
$E^{a,b,c,d,e}=\parend{ab||cde|,\onethird[abc]+\onethird[abd]
+\onethird[abe]}$
for any five pages $a,b,c,d,e$.
\item
$F^{a,b,c,d,e}=\parend{ab||cde|,\twothirds[abc]+\onesixth[abd]
+\onesixth[abe]}$
for any five pages $a,b,c,d,e$.
\item
$G^{a,b,c,d,e}=\parend{a|bc|de|,\twothirds[abc]
+\onetwelfth[abd]+\onetwelfth[abe]+\onetwelfth[acd] +\onetwelfth[ace]}$
for any five pages $a,b,c,d,e$.
\end{enumerate}
Note that $A^{a,b,c}=A^{b,a,c}=A^{a,c,b}$.  There are many other symmetries.

 \paragraph{Action of $K_3$.}
 Let $K$ be the old knowledge state and $r$ the request.
 \begin{enumerate}
 \item\label{first easy}
 If $K=A^{a,b,c}$ and $r=a$, then the new knowledge
state is $A^{a,b,c}$.%, the cost is zero, and the offset is zero.
\item
If $K=B^{a,b,c,d}$ and $r=a$, then the new knowledge
state is $B^{a,b,c,d}$.%, the cost is zero, and the offset is zero.
\item
If $K=C^{a,b,c,d}$ and $r=a$, then the new knowledge
state is $C^{a,b,c,d}$.%, the cost is zero, and the offset is zero.
\item
If $K=D^{a,b,c,d,e}$ and $r=a$, then the new knowledge
state is $D^{a,b,c,d,e}$.%, the cost is zero, and the offset is zero.
\item
If $K=E^{a,b,c,d,e}$ and $r=a$, then the new knowledge
state is $E^{a,b,c,d,e}$.%, the cost is zero, and the offset is zero.
\item
If $K=F^{a,b,c,d,e}$ and $r=a$, then the new knowledge
state is $F^{a,b,c,d,e}$.%, the cost is zero, and the offset is zero.
\item
If $K=G^{a,b,c,d,e}$ and $r=a$, then the new knowledge
state is $F^{a,b,c,d,e}$.%, the cost is zero, and the offset is zero.
\item
If $K=A^{b,c,d}$ and $r=a$, then the new knowledge
state is $B^{a,b,c,d}$.%, the cost is $1$, and the offset is $1$.
\item
If $K=B^{a,b,c,d}$ and $r=b$, then the new knowledge
state is $C^{a,b,c,d}$.%, the cost is $\onethird$, and the offset is zero.
\item\label{last easy}
If $K=C^{a,b,c,d}$ and $r=c$, then the new knowledge
state is $A^{a,b,c}$.%, the cost is $\onehalf$, and the offset is zero.
\item\label{first medium}
If $K=D^{a,b,c,d,e}$ and $r=b$, then the new knowledge
state is $E^{a,b,c,d,e}$.%, the cost is $\onehalf$, and the offset is zero.
\item
If $K=E^{a,b,c,d,e}$ and $r=c$, then the new knowledge
state is $A^{a,b,c}$.%, the cost is $\twothirds$, and the offset is zero.
\item
If $K=F^{a,b,c,d,e}$ and $r=c$, then the new knowledge
state is $A^{a,b,c}$.%, the cost is $\onethird$, and the offset is zero.
\item
If $K=F^{a,b,c,d,e}$ and $r=d$, then the new knowledge
state is $A^{a,b,d}$.%, the cost is $\fivesixths$, and the offset is zero.
\item
If $K=G^{a,b,c,d,e}$ and $r=b$, then the new knowledge
state is $E^{a,b,c,d,e}$.%, the cost is $\onesixth$, and the offset is zero.
\item\label{last medium}
If $K=G^{a,b,c,d,e}$ and $r=d$, then the new knowledge
state is $C^{a,d,b,c}$.%, the cost is $\fivesixths$, and the offset is zero.
\item\label{first hard}
If $K=D^{b,c,d,e,f}$ and $r=a$, then the new knowledge
is chosen uniformly among the ten knowledge states $A^{a,b,c}$, $A^{a,b,d}$,
$A^{a,b,e}$, $A^{a,b,f}$, $A^{a,c,d}$, $A^{a,c,e}$, $A^{a,c,f}$,
$A^{a,d,e}$, $A^{a,d,f}$, and $A^{a,e,f}$.
%The cost is $XXX$, and the offset is $YYY$.
\item
If $K=E^{b,c,d,e,f}$ and $r=a$, then the new knowledge state is $A^{a,b,c}$.
%The cost is $XXX$, and the offset is $YYY$.
\item
If $K=F^{b,c,d,e,f}$ and $r=a$, then the new knowledge state is $A^{a,b,c}$.
%The cost is $XXX$, and the offset is $YYY$.
\item\label{last hard}
If $K=G^{b,c,d,e,f}$ and $r=a$, then the new knowledge
is chosen uniformly among the six knowledge states
$C^{a,b,c,d}$, $C^{a,c,b,d}$, $C^{a,b,e,f}$,
$C^{a,b,e,f}$, $C^{a,c,e,f}$, and $C^{a,d,e,f}$.
%The cost is $XXX$, and the offset is $YYY$.
\item All other actions are symmetric to one of the above.
\end{enumerate}

\begin{exercise}{\rm
Write down all the symmetries of the knoweldge states of $K_3$.
(For example, $B^{a,b,c,d} = B^{a,b,d,c}$.)
}
\end{exercise}

\begin{exercise}{\rm
Compute $\offset$ for Actions \ref{first easy}
through \ref{last easy}, so as to satisfy the definition of
knowledge state algorithm, such that $\offset$ is as large
as possible in each case.
}
\end{exercise}

\begin{exercise}{\rm
Compute $\offset$ for Actions \ref{first medium}
through \ref{last medium}, so as to satisfy the definition of
knowledge state algorithm, such that $\offset$ is as large
as possible in each case.
}
\end{exercise}

\begin{exercise}{\rm
Compute $\offset$ for Actions \ref{first hard}
through \ref{last hard}, so as to satisfy the definition of
knowledge state algorithm, such that $\offset$ is as large
as possible in each case.
}
\end{exercise}

\begin{exercise}{\rm
Compute $\cost$ for Actions \ref{first easy}
through \ref{last easy}, so as to satisfy the definition of
knowledge state algorithm.
}
\end{exercise}

\begin{exercise}{\rm
Compute $\cost$ for Actions \ref{first medium}
through \ref{last medium}, so as to satisfy the definition of
knowledge state algorithm.
}
\end{exercise}

\begin{exercise}{\rm
Compute $\cost$ for Actions \ref{first hard}
through \ref{last hard}, so as to satisfy the definition of
knowledge state algorithm.
}
\end{exercise}

\paragraph{Potential for $K_3$.}
Define a potential $\Phi$ on the knowledge states of $K_3$ as follows.
\begin{enumerate}
\item $\Phi(A^{a,b,c}) = 0$.
\item $\Phi(B^{a,b,c,d}) = \fivesixths$.
\item $\Phi(C^{a,b,c,d}) = \onehalf$.
\item $\Phi(D^{a,b,c,d,e}) = \fivethirds$.
\item $\Phi(E^{a,b,c,d,e}) = \sevensixths$.
\item $\Phi(F^{a,b,c,d,e}) = \sevensixths$.
\item $\Phi(G^{a,b,c,d,e}) = \fourthirds$.
\end{enumerate}


\begin{exercise}{\rm
Prove that  $\Phi$ satisfies the conditions of an $\frac{11}{6}$-potential
for Actions \ref{first easy} through \ref{last easy}.
}
\end{exercise}

\begin{exercise}{\rm
Prove that  $\Phi$ satisfies the conditions of an $\frac{11}{6}$-potential
for Actions \ref{first medium} through \ref{last medium}.
}
\end{exercise}

\begin{exercise}{\rm
Prove that  $\Phi$ satisfies the conditions of an $\frac{11}{6}$-potential
for Actions \ref{first hard} through \ref{last hard}.
}
\end{exercise}

\begin{exercise}{\rm
Is $K_3$ a stable distribution algorithm?
}
\end{exercise}

\begin{exercise}{\rm
Prove that there is no knowledge state algorithm for the 3-cache
problem that is $\frac{11}{6}$-competitive as a knowledge state algorithm,
and which never has more than four active pages.
}
\end{exercise}

\end{document}
