<p>I think Yury's beautiful example actually answers my question. It shows that $\delta_0$ <em>does not</em> go to 0 as $n\to \infty$. One can probably also use a similar construction to show that the same holds for any $\delta&lt;1/2$.</p>

<p>Thanks Yury!</p>

CC BY-SA 3.0
2013-07-25T13:35:01.287Z
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
CC BY-SA 3.0
2013-07-25T04:03:16.593Z
2013-07-25T04:10:44.313Z
2013-07-25T04:10:44.313Z
Itai
<p>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)$. </p>

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

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

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

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

<p>A simple use of Lovaz local lemma says that if $\delta&gt;7/8$ then indeed $P_n&gt;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 &lt; (\sqrt{5}-1)/2 \simeq 0.61$.</p>

<p>Can you think of any method to attack this problem?</p>

CC BY-SA 3.0
2013-07-24T11:00:33.200Z
Using Shearer's bound (as quoted in http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma), $\delta>3/4$ suffices.
Colin McQuillan
CC BY-SA 3.0
2013-07-24T22:42:23.297Z
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
<reference-request><co.combinatorics><pr.probability><randomness>
correlation in an almost independent set of random variables
Itai
# correlation in an almost independent set of random variables

(Asked by: username_0 on 2013-07-24)

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 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?

**Tags:** reference-request, co.combinatorics, pr.probability, randomness

> **Comments:**
> **username_1**: Using Shearer's bound (as quoted in http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma), $\delta>3/4$ suffices.  
> **username_2**: 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$.  

---

## 1 answers

### Answer by username_0 on 2013-07-25. Score: 2

I think username_2'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$.

Thanks username_2!

> **Comments:**
> **username_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.  

---

