@TechReport{Dartmouth:TR96-302,
  author = {Neal E. Young},
  title = {{Cross-input Amortization Captures the Diffuse Adversary}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {PCS-TR96-302},
  year = {1996},
  month = {December},
  URL = {http://www.cs.dartmouth.edu/reports/TR96-302.ps.Z},
  abstract = {
      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.
  }
}