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?