Randomization

The official definition of "algorithm" includes the requirement that it
be deterministic.  We define a "randomized algorithm" to be a process
that satisfies all the other criteria, but which can use randomization
to make decisions.  The probability of each choice must be fixed in
advance.

The best way to think of a randomized algorithm is to imagine a programming
language that allows all the usual statements, plus one other that looks
like this:

   with probability p do choice1 else do choice2;

where p is some expression whose value is a real number between 0 and 1,
and choice1 and choice2 are statements.

For many problems, randomization can be used to speed up an algorithm without
sacrificing accuracy.  The paper, "Las Vegas is better than determinism,"
shows this for the row-matching problem for a square bit matrix.  Given
an n by n matrix of zeros and ones, the question is, are there two identical
rows?  For example, the answer is yes for the first matrix shown below,
and no for the second:

                       0000                   0000
                       0101                   0101
                       0011                   1010
                       0101                   0110

An algorithm that solves this problem is required to present a "certificate,"
that is, a message (usually a subset of the input data) that certifies the
answer.  For example, the second and fourth rows of the first matrix certify
that the answer is yes, while the second and third columns of the second
matrix certify that the answer is no.  In the row-matching problem, although
the input data have size Theta(n^2), there is always a certificate of size
O(n log n).  But can that certificate be found in less than quadratic time?

The paper shows that the worst case time for any algorithm for the
row-matching problem takes Theta(n^2) time, and in fact, in the worst case,
must look at every entry of the matrix.  What this means is that, given
any row-matching algorithm A, and given any n, there is an n by n matrix M
such that A looks at every entry of M before finding a certificate.  We
say that M is the "worst case" for A.  There is no universal worst case,
i.e., for any M, there is some choice of A that finds a certificate quickly.

The key to the result is that the worst cases for different algorithms are
different, and that there are many algorithms which have very few worst
cases.  Suppose, for example, that A_1, ... A_N (for some huge N, much
larger than n) are algorithms, each of which finds a certificate for most
possible choices of M.  Suppose, also, that any fixed M is bad for very
few of the A_i.  A randomized algorithm could then consist of a single
choice, where one of the A_i is picked at random, and then A_i is used
to (deterministically) find a certificate.  For the row-matching problem
this can be done in such a way that, for any fixed M, the expected
(i.e., average) time complexity to find a certificate is O(n log n).
We then say that there is a randomized algorithm for the row-matching
problem with expected time complexity O(n log n).



Do not confuse randomization with "average case" analysis.  When we say that
Quicksort takes O(n log n) time to sort a list of length n "in the average
case," we are not referring to randomization.  In this statement, quicksort
is deterministic, and the list is picked at random.  Analysis of randomized
algorithms makes no assumption about how the input data are chosen.  For
example, in the row-matching problem, there is no assumption that M is
chosen randomly.  We can assume that there is an "adversary" that looks
at our code (which contains those randomized branching statements) and then
picks M.  That is, the adversary knows the probability that we will make a
given choice but does not know what the choice will be before picking M.

Randomized optimization.

Randomization can be used to improve an algorithm's performance in situations
where the goal is to maximize gain or minimize cost.  For example, suppose
that you are a contestant on a game show.  You are shown two boxes, and must
pick one.  One box contains a valuable gift; the other is worthless.

Further, suppose that the person who chooses which box to put the valuable
gift in is your worst enemy.  This person knows exactly how you think, and
thus knows what algorithm you will use to choose a box.  If you use a
deterministic algorithm, you'll get nothing, because that person will put
the gift in the box that you will not choose.  But if your algorithm is to
flip a coin to decide, you will get the valuable gift with probability
one half, regardless of what your worst enemy does.  If the gift is worth
one dollar, say, then the gain from any deterministic algorithm is 0, but
the expected gain from the coin-flipping algorith is 1/2.

Should you carry your umbrella today?

Suppose that you do not know whether it will rain today, and you must
decide whether to carry your umbrella.  Let's say that you always carry
your briefcase.  We assign a cost of 1 to each object you carry, and a
cost of 4 for the discomfort of getting wet because you don't have your
umbrella.  Thus, if you carry your umbrella, your cost is 2.  If you
do not carry your umbrella, the cost is 1 if it does not rain, but 5
if it does.

The obvious thing to do is the check the weather forecast, and make your
decision based on the probability of rain today.  But let's assume that
you couldn't get a forecast, and you have no idea what that probability
is.

Define "competitiveness" to be the ratio of your cost to optimal cost.
If it rains, the optimal cost is 2, while if it does not rain, the
optimal cost is 1.  If you carry your umbrella all the time, your
competitiveness is 2, because, in the worst case, it never rains.  On
the other hand, suppose that you carry your umbrella with probability p.
What is the meaning of "competitiveness" in that situation?

The optimal cost is defined the same way, namely 1 or 2.  Our cost
is defined in terms of expected value, namely, (5-3p) if it rains,
(1+p) if it does not.  (Do you see how those expressions were obtained?)
The competitiveness is then defined to be (5-3p)/2 if it rains,
(1+p) if it does not.  We then always take the worst case, namely
the larger value.  For p = 1 (umbrella) the competitiveness is 2,
while for p = 0 (no umbrella) the competitiveness is 5/2.  Can we
do better by picking a value of p between 0 and 1?
