  We introduce a novel method for the rigorous quantitative evaluation of
online algorithms that relaxes the "radical worst-case" perspective of classic
competitive analysis. In contrast to prior work, our method, referred to as
randomly infused advice (RIA), does not make any probabilistic assumptions
about the input sequence and does not rely on the development of designated
online algorithms. Rather, it can be applied to existing online randomized
algorithms, introducing a means to evaluate their performance in scenarios that
lie outside the radical worst-case regime. More concretely, an online algorithm
ALG with RIA benefits from pieces of advice generated by an omniscient but not
entirely reliable oracle. The crux of the new method is that the advice is
provided to ALG by writing it into the buffer B from which ALG normally reads
its random bits, hence allowing us to augment it through a very simple and
non-intrusive interface. The (un)reliability of the oracle is captured via a
parameter 0 {\le} {\alpha} {\le} 1 that determines the probability (per round)
that the advice is successfully infused by the oracle; if the advice is not
infused, which occurs with probability 1 - {\alpha}, then the buffer B contains
fresh random bits (as in the classic online setting).
  The applicability of the new RIA method is demonstrated by applying it to
three extensively studied online problems: paging, uniform metrical task
systems, and online set cover. For these problems, we establish new upper
bounds on the competitive ratio of classic online algorithms that improve as
the infusion parameter {\alpha} increases. These are complemented with (often
tight) lower bounds on the competitive ratio of online algorithms with RIA for
the three problems.
