# correlation in an almost independent set of random variables

Suppose I have a set of $n$ binary random variables $X_1, \ldots, X_n$ that sit on a line, and assume that $\Pr(X_i=0)=\delta$ for all $i$. In addition, assume that any two subsets of variables that are separated by at least one site are completely independent. For example: $P(X_1, X_2, X_4, X_7) = P(X_1,X_2)\cdot P(X_4, X_7) = P(X_1,X_2)\cdot P(X_4)\cdot P(X_7)$.

In other words, whenever we look at a multi-variable dist', we can "break" it into blocks of contiguous variables.

Finally, assume that for any subset of $k<n$ variables, $\{X_{i_1}, \ldots, X_{i_k}\}$, we have $\Pr(X_{i_1}=X_{i_2}=\ldots=X_{i_k}=0) > 0$.

In that case, can I find a lower bound on $P_n\equiv \Pr(X_1=X_2=\ldots=X_n=0)$ ?

In particular, I would like to know, if there is a threshold $\delta_0$, such that for every $\delta>\delta_0)$, it must be that also $P_n>0$, and how this threshold depends on $n$.

A simple use of Lovaz local lemma says that if $\delta>7/8$ then indeed $P_n>0$. But I think that it can be improved. For example, for $n=3$, a direct calculation shows that for $n=3$, it is impossible that $P_3=0$ unless $\delta < (\sqrt{5}-1)/2 \simeq 0.61$.

Can you think of any method to attack this problem?

• Using Shearer's bound (as quoted in en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma), $\delta>3/4$ suffices. – Colin McQuillan Jul 24 '13 at 11:00
• There is a simple lower bound on $\delta_0$: $\delta_0 \geq 1/2$. Let $Y_1, \dots, Y_{n-1}$ be i.i.d. r.v. uniformly sampled from $\{0,1\}$. Let $X_1 = Y_1 \oplus_2 1$, $X_2 = Y_1 \oplus_2 Y_2$, $X_3 = Y_2 \oplus_2 Y_3$, ..., $X_{n-1} = Y_{n-2} \oplus_2 Y_{n-1}$, and $X_n = Y_{n-1}$. Then $X_i$ satisfy the desired properties; $X_i = 0$ w.p. $1/2$. But $X_1\oplus_2 \dots \oplus_2 X_n = 1$ and thus $\Pr(X_1=X_2=\dots=X_n = 0) = 0$. – Yury Jul 24 '13 at 22:42

I think Yury's beautiful example actually answers my question. It shows that $\delta_0$ does not go to 0 as $n\to \infty$. One can probably also use a similar construction to show that the same holds for any $\delta<1/2$.
• To get this construction for $\delta < 1/2$, just define $X'_i = X_i$ w.p. $2\delta$ and $X'_i=1$ w.p. $1-2\delta$ (independently for all $i$). Then $\Pr(X_i' = 0) = \delta$ and $X_1',\dots,X_n'$ satisfy all the required properties. – Yury Jul 25 '13 at 13:35