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?

  • 2
    $\begingroup$ Using Shearer's bound (as quoted in en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma), $\delta>3/4$ suffices. $\endgroup$ – Colin McQuillan Jul 24 '13 at 11:00
  • 2
    $\begingroup$ 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$. $\endgroup$ – 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$.

Thanks Yury!

  • $\begingroup$ 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. $\endgroup$ – Yury Jul 25 '13 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.