Contents pg01: Metrical task systems, work functions, and deterministic potentials. Apr 3 07:06 2002 pg02: A deterministic lower bound of 2n-1 for any metric space of n points. Apr 3 08:42 2002 pg03: The WFA for metrical task systems. Apr 3 12:04 2002 pg04: Distribution potentials. Apr 9 16:49 2002 pg05: Behavioral potentials I. Apr 10 13:57:36 PDT 2002 pg06: Behavioral potentials II. Apr 10 13:15:53 PDT 2002 pg07: An optimally competitive randomized online algorithm for the ice-cream problem. Feb 28 06:12 2002 pg08: A lower bound of H_k For the randomized competitiveness of the UMTS problem with k states. Mar 20 15:14 2002 pg09: The randomized competitiveness of the UMTS problem for k = 2. Apr 9 17:42:20 PDT 2002 pg10: The randomized competitiveness of the UMTS problem for k >= 3. Apr 9 18:00:55 PDT 2002 Potentials for Metrical Task Systems Apr 3 07:06 2002 Let M = (M,calT) be a MTS. M is a metric space, and calT is a set of task vectors, i.e., a set of functions from M to Reals + {infinity}. Write ||x,y|| for the distance from x to y in M. We call the elements of M "states." (In some applications it would be confusing to call a state a "point" as the word "point" is reserved for something else. For example, in the k-server problem, a "state" is an unordered k-tuple of "points.") Let W be the set of all work functions on M. Each w in W is a function from M to Reals, which satisfies the 1-Lipschitz condition, namely that w(x) <= w(y) + ||x,y|| for any x,y. We say that w is "supported" by a set S subseteq M if, for any x in M, there exists y in S such that w(x) = w(y) + ||x,y||. If M is finite (and in most practical applications even if M is infinite) there is a unique "minimal support" for any work function. If the minimal support of w consists of a single state x, we say that w is a "cone at x." Sometimes we say that w is "the cone at x," meaning that it is supported by x and that w(x) = 0. If w is a work function and r in calT is a request, the work function w' = w update r is defined by: w'(x) = min_{y in M}(w(y) + ||y,x||). The initial work function w^0 is the cone at the start state. The traditional definition of the work function at step t is w^t = w^{t-1} update r^t. Theorem: Given a request sequence of length n, the optimal cost to service that request sequence is min_{x in M}w^n(x). Proof: Standard dynamic programming. We define a "C-potential" to be a function Phi(w,x) in Reals, defined for every work function w and every state x, such that the following two conditions hold: 1. Update condition. For any work function w, state x, and request r, let w' = w update r. Then there exists a state y such that: Phi(w,x) >= ||x,y|| + r(y) + Phi(w',y) 2. Offset condition. For any work function w, state x, and constant K: Phi(w,x) = Phi(w+K,x) + C*K Theorem: There exists a C-competitive deterministic online algorithm for M if and only if there exists a C-potential. Warning: Technically, we need additional conditions on M. If M is finite, there is no problem. The Theorem also usually holds for classic applications, such as the server problem. In practice, you don't have to worry about those conditions. Lower Bound for the Deterministic Competitiveness of a Metrical Task System Apr 3 08:42 2002 Theorem. Let M be any metric space of cardinality n. Then there is a set of tasks calT on M such that there is no deterministic online algorithm which is less than 2n-1 competitive for (M,calT). Proof: Let x_1, ... x_n be the states. Assume that x_1 is the start state. Let calT be the set of all non-negative functions from M to Reals. Let calA be any deterministic online algorithm for M. Without loss of generality, all distances in M are at least 1. Let epsilon be a small positive number. Let {iota_i} be the request vector where iota_i(x_i) = epsilon, and iota_i(x_j) = 0 for all j not equal to i. We define the "cruel request sequence" to be the request sequence which requests the task iota_i if the current state of calA is x_i. We will now define 2n-1 offline algorithms, calB_1 ... calB_{2n-1}. Except for the very first request, the total cost for all of these offline algorithm algorithms is equal to the cost for calA. It follows that, asymptotically, calA pays at least 2n-1 times as much as some calB_i. We call calB_1 ... calB_n the "stubborn" offline algorithms, and the others the "movable" offline algorithms. The first request will be iota_1. For 1 <= i <= n, calB_i moves immediately to x_i upon the first request, and then never leaves that state. For n < i <= 2n-1, calB_i moves to x_{i-n+1} upon the first request, and afterwards behaves so as to maintain the following invariant: At the end of each step, there are exactly two algorithms in each state. In particular, there is one stubborn offline algorithm in each state, and there is one movable offline algorithm in each state except for calA's current state. This invariant can be realized as follows. If, in response to a request, calA does not change state, then none of the calB_i change state. If calA changes state from x_i to x_j in response to the request iota_i, then the one movable offline algorithm that was at state x_j first serves the request, then moves to x_i. Note that, except for the initial step where the calB_i get into position, the total cost of all the calB_i at each step is precisely the cost of calA at that step. The theorem follows. The Work Function Algorithm for metrical task systems. Apr 3 12:04 2002 Let M be a metrical task system. The work function algorithm (WFA) is a deterministic online algorithm, defined as follows. If r^t is the request at step t, and if w^t is the work function at step t, and if x^{t-1} is the state of WFA at step t-1, then WFA chooses x^t so that: 1. x^t is in the support of w^t 2. ||x^{t-1} + x^t|| + w^t(x^t) is minimized We remark that this definition of WFA agrees with the classic definition of WFA for the server problem. It is known that, for the k-server problem, WFA is 2k-1 competitive, regardless of the cardinality of the metric space. For k = 2, WFA is 2-competitive. WFA is k-competitive for certain specific classes of metric spaces, as well. The competitiveness of WFA for the k-server problem is conjectured to be k in general. Theorem: If M has n states, then WFA is 2n-1 competitive. Proof: Let x_1, ... x_n be the states. Let Phi be the potential defined by Phi(w,x_i) .... (Unfinished) Distribution Potentials. Apr 9 16:49 2002 Let M be a metrical task system. We say that Phi is a "distribution C-potential" if the following two conditions hold. 1. If w' = w update r, and if P is a distribution, then there exists a distribution Q such that Phi(w,P) >= ||P,Q|| + r(Q) + Phi(w',Q). 2. If K is a constant, Phi(w,P) = Phi(w+K,P) + C*K. Note: it is understood that r(Q) is defined to be an expected value. That is, if Q = lambda_1 x_1 + ... + lambda_n x_n, then r(Q) is defined to be lambda_1 r(x_1) + ... + lambda_n r(x_n). Note: ||P,Q|| is the "minimal transport distance" between two distributions. Theorem: There is a randomized online algorithm for M which is C-competitive against the oblivious adversary if and only if there exists a distribution C-potential for M. Proof: (incomplete) Given a distribution C-potential Phi, define a randomized distribution based online algorithm calA as follows. If w is the current work function, P is the current distribution, and r is the next request, move to a distribution Q which satisfies condition 1. in the definition above. Behavioral Potentials I. Apr 10 13:57:36 PDT 2002 Note dated Sun Oct 19 15:13:13 PDT 2003: This is what is now called a "mixed potential." Let M be a metrical task system. We define a "behavioral C-potential" as to be a partial function Phi, whose domain is a set of pairs of the form (w,x) which we call "special pairs," where w is a work function and x is a state such that 1. There is a special pair (w^0,x^0), where x^0 is the start state. 2. For any special pair (w,x) and any state z, Phi(w,x)> = 0 and w(z) >= 0. 3. If (w,x) is any special pair and r is a request and if w' = w update r, then there exist special pairs (w_1,x_1), ... (w_n,x_n) and probabilities lambda_1 , ... lambda_n, where Sum_i lambda_i = 1, and a constant K such that 3(a). For any state z, Sum_i lambda_i w_i(z) + K <= w'(z). 3(b). Phi(w,x) >= Sum_i lambda_i*{||x,x_i||+r(x_i)+Phi(w_i,x_i)} - K*C. Remark: To verify Condition 3(a), it suffices to consider only z which are in the support of w'. Proof of Remark: Suppose that z is not in the support of w'. Then w'(z) = w'(z') + ||z,z'|| for some z' which is in the support of w'. By the Lipschitz condition for work functions, w_i(z) <= w_i(z') + ||z,z'|| for each i. Since, by hypothesis, the inequality holds for z', we have: Sum_i lambda_i w_i(z) + K <= Sum_i lambda_i(w_i(z)+||z,z'||) = Sum_i lambda_i w_i(z) + ||z,z'|| <= w'(z') + ||z,z'|| = w'(z), as required. Theorem: If there is a behavioral C-potential for a metrical task system M, then there is a randomized online algorithm for M which is C-competitive against the adaptive online adversary. Proof: Suppose that Phi is a behavioral C-potential for M. We will define the current state x^t of the algorithm after t steps, as well as a work function w^t which we call the "Las Vegas work function at step t," in such a way that (w^t,x^t) is always a special pair. Initially, the calA's state is x^0, and the Las Vegas work function is w^0. Suppose that x^{t-1} and w^{t-1} are the state and the Las Vegas work function at step t-1. Let r^t be the request at step t. We describe how to pick the next state x^t and the next Las Vegas work function w^t. Let w' = w^{t-1} update r^t. Then choose special pairs (w_1,x_1), ... (w_n,x_n) and probabilities lambda_1 , ... lambda_n, where Sum_i lambda_i = 1, and a constant K^t, such that for any state z, Sum_i lambda_i w_i(z) + K^t <= w'(z), and such that Phi(w^{t-1},x^{t-1}) >= Sum_i lambda_i*{||x^{t-1},x_i||+r(x_i)+Phi(w_i,x_i)} - K^t*C. Then randomly choose some i, where each i is chosen with probability lambda_i. Let x^t = x_i, and let w^t = w_i. We now need to verify C-competitiveness. Let calR be any adaptive online adversary. Let z^t be calR's state after t steps. For each step t, let Phi^t = Phi(w^t,x^t). Let cost^t_calA be the cost incurred by calA during all steps from 1 to t. Let cost^t_calR be the cost incurred by calR during all steps from 1 to t. Since calA is randomized, Phi^t, cost^t_calA and cost^t_calR are random variables. Let "E" denote expected value. We now prove the following claims. Claim 1: E(cost^t_calA) <= C*E(Sum_{j<=t}K^j) + Phi^0 - E(Phi^t). Claim 2: E(cost^t_calR) >= E(w^t(z^t)+Sum_{j<=t}K^j) - w^0(x^0). Behavioral Potentials II. Apr 10 13:15:53 PDT 2002 Claim 1: E(cost^t_calA) <= C*E(Sum_{j<=t}K^j) + Phi^0 - E(Phi^t). Claim 2: E(cost^t_calR) >= E(w^t(z^t)+Sum_{j<=t}K^j) - w^0(x^0). We prove both claims by induction on t. For t = 0, they are trivial. For t = 0, Claim 1 simply states that 0 <= 0. For t = 0, Claim 2 is trivial since z^0 = x^0. Now suppose both claims hold for t-1. Let w' = w^{t-1} update r^t, and let {lambda_i}, {w_i}, and K be as given in the description of calA. The adversary calR must choose z^t without knowing which w_i will be selected to be w^t. We have (a) E(cost^t_calA) = E(cost^{t-1}_calA) + E(||x^{t-1},x^t||) + E(r^t(x^t)). By the inductive hypothesis, we have: (b) E(cost^{t-1}_calA) <= C*E(Sum_{j= E(w'(z^t)). By the inductive hypothesis, we have: (f) E(cost^{t-1}_calR) >= E(w^{t-1}(z^{t-1})) + E(Sum_{j= E(w^t(z^t)) + E(K^t). Simply adding (d), (e), (f), and (g) and cancelling terms, we obtain the statement of Claim 2. We now complete the proof of the theorem. Let n be the number of requests. By Claim 1: (h) E(cost_calA) <= C*E(Sum_{j<=n}K^j) + Phi^0 - E(Phi^t). By Claim 2: (i) E(cost_calR) >= E(w^n(z^n)) + E(Sum_{j<=n}K^j) - w^0(x^0). By property 2 of Phi: (j) E(w^n(z^n)) >= 0, and (k) E(Phi^n) >= 0. Combining the inequalities (h), (i), (j), and (k) and cancelling terms, we obtain: E(cost_calA) <= C*E(cost_calR) + C*w^0(x^0). Since w^0(x^0) is constant, we have verified C-competitiveness. 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. 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. Drunkard's walk in a 1-dimensional box Tue Apr 9 17:42:20 PDT 2002 A drunkard is confined to a walkway that is two miles long, and has a wall at each end. The drunkard's walk is in phases, where in each phase he walks for a while in one direction. At each phase, the drunkard picks a direction uniformly at random. He also picks a distance d to walk using an exponential distribution with mean 1; i.e., for any given t >= 0, the probability that he chooses d > t is e^{-t}. The drunkard then attempts to walk that distance in the chosen direction. When he has walked that distance he stops, ending the phase. If the drunkard encounters the wall at the end of the walkway during a phase, he doesn't notice, but just keeps marching in place for the appropriate number of steps, then stops, ending the phase. Problems. 1. Let pi^i be the distribution of the drunkard after i phases. Prove that, as i goes to infinity, pi^i converges to a unique stationary distribution pi that does not depend on the initial distribution pi^0. 2. What is the probability (in the long run) that the drunkard will end a given phase at a wall? 3. The walkway consists of a sequence of stones one step apart. Prove that, except for the two stones at the ends, the drunkard steps on all stones equally often in the long run. 4. In the long run, how often does the drunkard step on a given end stone (measured as a proportion of the total number of steps)? The answer should be given in a limiting sense, i.e., as a constant times epsilon, where epsilon is the size of one stone in miles, which is taken as infinitesimal. 5. In the long run, what proportion of the time is the drunkard is trying to walk into a wall? Drunkard's walk in a 2-dimensional box Apr 9 18:00:55 PDT 2002 A drunkard is confined to a walled hexagonal patio two miles in diameter, thus one mile on each side. Each corner is marked with a white or black flag, alternating around the boundary. The patio is paved with hexagonal flagstones. Each flagstone is marked with three arrows, colored red, blue, and green. All the arrows of a given color are parallel. The arrows on the center stone point to the white corners. At each black corner, one arrow points toward the the white corner two miles away on the opposite side, and the other two point toward the adjacent walls. At each white corner, one arrow points into the corner, and the other two are parallel to the adjacent walls, that is, point toward the neighboring black corners one mile away. The drunkard's walk is in phases, where in each phase he walks for a while in one direction. At the beginning of each phase, he picks a color at random, each with probability 1/3, and follows the arrows of that color throughout that phase. Also at the beginning of each phase, the drunkard picks a positive number d, using an exponential distribution with mean 1; i.e., for any given t >= 0, the probability that he chooses d > t is e^{-t}. The drunkard then attempts to walk d miles in the chosen direction. When he has walked that distance he stops, ending the phase. If the drunkard encounters a wall during a phase, he doesn't notice, but just keeps marching in place for the appropriate number of steps, then stops, ending the phase. Problems. 1. Let pi^i be the distribution of the drunkard after i phases. Prove that, as i goes to infinity, pi^i converges to a unique stationary distribution pi that does not depend on the initial distribution pi^0. 2. For any given flagstone, how often, in the long run, does the drunkard step on that stone? The answer must be in the form of a positive constant times a power of epsilon, where epsilon is the diameter of one flagstone. Since we are interested in the limiting behavior as epsilon goes to zero, only the highest order term counts. If the stone is at a corner, the answer will be a positive constant. If the stone is along a wall but not in a corner the answer will be a positive constant times epsilon. If the stone is in the interior of the patio, the answer will be a positive constant times either epsilon or epsilon^2. 3. As a specific instance of the above question, prove that the drunkard will be at a black corner 2e^{4/3} times as often as at a white corner. 4. In the long run, what proportion of the time is the drunkard is trying to walk into a wall? 5. Derive a simple formula for the randomized competitiveness of the UMTS problem for k = 3, as a function of the answer to problem 4 above. 6. Generalize the drunkard's walk in a box so that it applies to the UMTS problem for arbitrary k.