Models of Randomized Algorithms.

Here is the definition of the competitiveness of a radomized online algorithm.

Definition: A randomized online algorithm calA is C-competitive if there
exists a constant K such that, for any request sequence rho, the expected
cost of calA for rho does not exceed K plus C times the optimal cost for
rho.

Note that the words "adversary," "oblivious," and "game," do not occur in
this definition.

calA is assumed to be encoded somehow, using a programming language which
allows randomized branching.  For a given rho, expected cost could be thought
of as the limit, as N goes to infinity, of the average cost of N runs of
that program with input rho.

Since the definition quantifies rho inside, that means that, for a given
calA (i.e., program that implements calA) rho is the worst possible input,
without loss of generality.  Thus, we can model the situation by saying
that the adversary looks at the code of the program, then picks rho, using
unlimited computational power.  This adversary does not have the ability
to predict which branches the program will take, as those will be chosen
randomly during the actual run, which happens after the adversary picks rho.

The model where calA is a program is the behavioral model.  The model
where calA is a distribution on deterministic algorithms (as, for example,
in the barely random case) is actually a special case of the behavioral
model, where all the random branching occurs before reading any input.

The Distributional Model is a reduction of the problem to a deterministic
game.  In reality, you could never implement calA using the distributional
model.  (How could you send of an order to a tank saying, "Be at A with
probability 1/2 and be at B with probability 1/2.")  Instead, we prove
that the two models are equivalent.  If we have a C-competitive distributional
algorithm, we then convert it to a C-competitive behavioral algorithm, which
we can then implement.  (Flip a coin, then send a definite order to the tank.)

A "distribution" on a set S is defined to be a measure p on S such that
p(S) = 1.

