Lower Bound of H_k for the Randomized Competitiveness of the UMTS problem. Mar 20 15:14 2002 Let the states be called A_1, ... A_k. We use the notation (c_1, ... c_k) to denote the task where the cost of service is c_i if we are in state A_i. Theorem. There is an instance of the k state UMTS problem whose randomized competitiveness is at least H_k. Proof. Write T_i = (0,0,...,0,1,0, ... 0), i.e., c_i = 1 and c_j = 0 for all j not equal to i. Let calA be any randomized online algorithm. The worst case randomized adversary picks one of the T_i uniformly and independently at each step. The probability that calA is at that A_i is 1/k, regardless of calA's strategy. Thus, calA's expected cost of servicing the sequence is N/k, where N is the length of the sequence. The optimal service is to remain in the current state until the request which is bad for that state. At that time, move to the state which is good for the longest future time. We call that a phase. By the "coupon-collector's" result, the expected length of a phase is k*H_k. Thus, the expected cost, to the optimal offline algorithm, of servicing the request sequence, is N/(k*H_k), where N is the length of the request sequence. The theorem is thus proved.