Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

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

1 Answer

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!

share|improve this answer
 
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 at 13:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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