Solution to Test Problem 2. Consider the metrical task system consisting of two states, 1 and 2, where the distance between the states is 1; and two tasks, (0,2) and (1,0). The deterministic competitiveness of this MTS is 3/2. Find the randomized competitiveness against the oblivious adversary, and prove your answer, both as an upper and a lower bound. The answer is 4/3. We first note that there are only three offset functions, namely (0,1), (0,0), and (1,0). We give a 4/3 competitive distribution based algorithm as follows. If the offset function is (0,1), then the state is 1. If the offset function is (1,0), then the state is 2. If the offset function is (0,0), then the distribution is 2/3 in state 1, 1/3 in state 2. Lemma A: The above algorithm is 4/3 competitive. Proof: Let Phi = 1/3 if the offset function is (0,1). Let Phi = 2/3 if the offset function is (0,0). Let Phi = 0 if the offset function is (1,0). We need only show that the update inequality Phi >= Phi' + cost - 4/3 * offset for each move, where Phi' is the value of Phi after the move. Let w be the offset function before the move, w' after. If w = (0,1) and r = (0.2), then cost = 0, offset = 0, and Phi = Phi' = 1/3. If w = (0,1) and r = (1.0), then movement cost = 1/3 and service cost = 2/3, offset = 1, Phi = 1/3, and Phi' = 2/3. If w = (0,0) and r = (1.0), then movement cost = 1/3 and service cost = 0, offset = 0, Phi = 2/3, and Phi' = 1/3. If w = (0,0) and r = (0.2), then movement cost = 2/3 and service cost = 0, offset = 0, Phi = 2/3, and Phi' = 0. If w = (1,0) and r = (1.0), then cost = 0, offset = 0, and Phi = Phi' = 0. If w = (1,0) and r = (0.2), then movement cost = 1 and service cost = 0, offset = 1, Phi = 2/3, and Phi' = 1/3. Thus, the update inequality holds for each case. Lemma B: There is no online randomized algorithm that is less than 4/3 competitive against the oblivious adversary. Proof. Let calA be an online randomized algorithm. For simplicity, we write a for the request (0,2) and b for the request (1,0). We assume that the initial state is 1. Claim 1. Without loss of generality, calA is in state 1 if the last request was a. Proof of Claim 1: Let calA' be the following randomized online algorithm. If the request is a, move to state 1 and serve, then stay there. If the request is b, then move to the same state as calA, either before or after serving the request, whichever costs less. Let cost^t be the cost of calA for the first t steps, and let cost'^t be the cost of calA' for the first t steps. We say that t is "regular" if calA and calA' are in the same state after t steps, and we say that t is "irregular" if calA is in state 2 and calA' is in state 1 after t steps. There are no other possibilities. The following invariant then holds: If t is regular, then cost'^t <= cost^t. If t is irregular, then then cost'^t <= cost^t - 1. The invariant is proved by induction on t. 0 is regular, and both costs are 0. If t-1 is regular and t is regular, then calA' does exactly the same thing as calA for step t, so the invariant is preserved. If t-1 is regular and t is irregular and both algorithms are at state 1 after step t-1, then calA' pays 0 and calA pays at least 1 for step t. If t-1 is regular and t is irregular and both algorithms are at state 2 after step t-1, then calA' pays 1 and calA pays at least 2 for step t. If t-1 and t are both irregular, then calA' pays 0 and calA' pays 2 for step t. If t-1 is irregular and t is regular and the request at step t is a, then calA' pays 0 and calA pays 1 at step t. If t-1 is irregular and t is regular and the request at step t is b, then calA' pays 1 and calA pays 0 at step t. In all cases the invariant is preserved. This completes the proof of Claim 1. We now define a randomized adversary calR. The adversary requst sequence is rho = sigma^1 sigma^2 ... sigma^N, where each sigma^i is called a "phase." Each phase is either ba or bbba, and calR chooses each possibility with probability 1/2, and the choices for the phases are independent. calR is in state 1 at the end of each phase. calR serves ba at cost 1 by staying in state 1, and serves bbba at cost 2, by moving to state 2 immediately, then moving back to state 1 for the fourth step. Thus, calR's expected cost is 3/2 for each phase. By Claim 1, calA is in state 1 at the beginning and at the end of each phase. Consider the behavior of calA at phase sigma^i. We say that calA is "eager" at phase i if it moves to state 2 to service the initial request b. We say that calA is "cautious" at phase i if it stays in state 1 to service the initial request b. calA must make the choice between eager and cautious before knowing whether the phase will be ba or bbba. If calA is eager at phase i, it will pay 2 if the request is ba, and will pay at least 2 if the request is bbba. If calA is cautious at phase i, it will pay 1 if the request is ba, and will pay at least 3 if the request is bbba. Thus, calA will pay an average of at least 2 for each phase. calR will pay an average of 3/2 for each phase. Thus, the competitiveness of calA against calR is at least 2 / (3/2), which is 4/3. This completes the proof of Lemma B.