%T Cross-input Amortization Captures the Diffuse Adversary
%A Neal E. Young
%R Technical Report PCS-TR96-302
%I Dartmouth College, Computer Science
%C Hanover, NH
%D December 1996
%U http://www.cs.dartmouth.edu/reports/TR96-302.ps.Z
%X
   Koutsoupias and Papadimitriou recently raised the question of how well
 deterministic on-line paging algorithms can do against a certain class of
 adversarially biased random inputs.  Such an input is given in an on-line
 fashion; the adversary determines the next request probabilistically, subject
 to the constraint that no page may be requested with probability more than a
 fixed $\epsilon>0$.
   In this paper, we answer their question by estimating, within a factor of
 two, the optimal competitive ratio of any deterministic on-line strategy
 against this adversary.  We further analyze randomized on-line strategies,
 obtaining upper and lower bounds within a factor of two.  These estimates
 reveal the qualitative changes as $\epsilon$ ranges continuously from 1 (the
 standard model) towards 0 (a severely handicapped adversary).
   The key to our upper bounds is a novel charging scheme that is appropriate
 for adversarially biased random inputs.  The scheme adjusts the costs of each
 input so that the expected cost of a random input is unchanged, but working
 with adjusted costs, we can obtain worst-case bounds on a per-input basis.
 This lets us use worst-case analysis techniques while still thinking of some of
 the costs as expected costs.