A THRESHOLD FUNCTION FOR HARMONIC UPDATE

Harmonic update is a randomized on-line algorithm which, given a rando m rn-set of vertices U(m) subset of or equal to {-1, 1}(n) in the n-di mensional cube, generates a random vertex w is an element of {-1, 1}(n ) as a putative solution to the system of linear inequalities: Sigma(i =1)(n) w(i)u(i) greater than or equal to 0 for each u is an element of U(m). Using tools from large deviation multivariate normal approximat ion and Poisson approximation, we show that root n/root log n is a thr eshold function for the property that the vertex w generated by harmon ic update has positive inner product with each vertex in U(m). More ex plicitly, let P(n, rn) denote the probability that Sigma(i=1)(n) w(i)u (i) greater than or equal to 0 for each u is an element of U(m). Then, as n --> infinity, P(n, m) --> 0 or 1 according to whether m = m(n) v aries with n such that >> root n/root log n or m << root n/root log n, respectively. The analysis also exposes the fine structure of the thr eshold function.