A Threshold Function for Harmonic Update
Shao C. Fang, Santosh S. Venkatesh · SIAM Journal on Discrete Mathematics · 1997
Harmonic update is a randomized on-line algorithm which, given a random m-set of vertices $U(m)\subseteq\{-1,1\}^n$ in the n-dimensional cube, generates a random vertex $\bw\in\{-1,1\}^n$ as a putative solution to the system of linear inequalities: $\sum_{i=1}^n w_i u_i\geq0$ for each $\bu\in U(m)$. Using tools from large deviation multivariate normal approximation and Poisson approximation, we show that $\sqrt{n}\big/\!\sqrt{\log n}$ is a threshold function for the property that the vertex $\bw$ generated by harmonic update has positive inner product with each vertex in $U(m)$. More explicitly, let $P(n,m)$ denote the probability that $\sum_{i=1}^n w_i u_i\geq 0$ for each $\bu\in U(m)$. Then, as $n\to\infty$, $P(n,m)\to 0$ or 1 according to whether $m=m_n$ varies with n such that $m\gg\sqrt{n}\big/\!\sqrt{\log n}$ or $m\ll\sqrt{n}\big/\!\sqrt{\log n}$, respectively. The analysis also exposes the fine structure of the threshold function.