Bounding the diffuse adversary
Neal E. Young · 1998
Koutsoupias and Papadimitriou recently raised the question of how well deterministic on-line paging algorithms can do against a certain class of adversariallu biased random input> [3]. 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 6> 0. In this note, 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 fur-ther analyze randomized on-line strategies, obtaining upper and lower bounds within a factor of two. These estimates reveal the qualitative changes as E ranges continuously from 1 [the standard model) towards 0 (a severely handicauued adbersary). Our upper bounds usk an %&rance-b&id” charging scheme that reduces the analysis of the expected cost on an adversarially biased random input to the analysis of the “adjusted ” cost of a worst-case input. 1