A 12/11 competitive randomized algorithm for the ice cream problem. Feb 28 06:12 2002 We first give the algorithm as a distribution on deterministic algorithms. D_1: Go to V the first time v is requested, and stay there. D_2: Go to V each time v is requested, go to C each time c is requested. D_3: Go to V each time v is requested and the previous request was also v. Go to C each time c is requested. D_4: Go to C the first time c is requested, and stay there. Define A to be {1/11}D_1 + {3/11}D_2 + {6/11}D_3 + {1/11}D_4. That is, pick one of the D_i at the very beginning, and stick to it. We now give a distributional description. Initially, the algorithm is at the start state (either V or C) and remains there until a contrary request is made. After that, the distribution depends on the offset function as follows. 1. If the offset function is (0,1) the distribution is {10/11}V + {1/11}C. 2. If the offset function is (0,0) the distribution is {4/11}V + {7/11}C. 3. If the offset function is (1,0) the distribution is {1/11}V + {10/11}C. We now give an equivalent behavioral description. 1. If the initial state is V, stay there until c is requested, at which move to C with probability 10/11. 2. If the initial state is C, stay there until v is requested, at which move to V with probability 4/11. All other cases assume that there has been at least one request that is contrary to the initial state. The current offset function is used as a guide. 3. For any offset function, if in state V and v is requested, stay in state V. 4. For any offset function, if in state C and c is requested, stay in state C. 5. If the offset function is (0,1), the state is C, and v is requested, stay in state C. 6. If the offset function is (1,0), the state is V, and c is requested, stay in state V. 7. If the offset function is (0,1), the state is V, and c is requested, go to state C with probability 9/10, else stay in state V. 8. If the offset function is (1,0), the state is C, and v is requested, go to state V with probability 3/10, else stay in state C. 9. If the offset function is (0,0), the state is V, and c is requested, go to state C with probability 3/4, else stay in state V. 10. If the offset function is (0,0), the state is C, and v is requested, go to state V with probability 6/7, else stay in state C.