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.