Body

Suppose $(X_1,\ldots,X_n)$ are independent Bernoulli random variables with $\mathbb{E}(X_i)= p_i$, and we want to test the global null hypothesis that $p_i=\frac{1}{2}$ for all $i$, versus the alternative that there is a sparse set of size $s$ on which $p_i\ge \frac{1}{2}+A$. The detection boundary of this test in terms of $(s,A)$ is well understood, both in the case when the signal is arbitrary, and when the signal is present in a segment. We study the above questions when the Bernoullis are dependent, and the dependence is modeled by a graphical model (Ising model). In this case, contrary to what typically happens, dependence can allow detection of smaller signals than the independent case. This phenomenon happens over a wide range of graphs, for both arbitrary signals and segment signals. This talk is based on joint work with Nabarun Deb, Rajarshi Mukherjee, and Ming Yuan.