14
$\begingroup$

The Lovász Local Lemma gives a probability bound in a context where there are many events that are "not quite" independent.

What other theorems exist in this genre? That is, what other theorems have a hypothesis of the form "Let events E_1, E_2, ... satisfy [relaxed form of independence]" and a conclusion of the form "Then the probability of [compound event] satisfies [inequality]"?

(I hope this question isn't too broad. I frequently encounter problems with events that are "almost independent", either in the sense that most subsets are independent or in the sense that the probabilities of compound events are well-approximated by assuming independence, and I am looking for general tools that may be helpful when these situations come up.)

$\endgroup$
2

3 Answers 3

12
$\begingroup$

A large number of results for sums $W$ of possibly dependent indicators of events (that is, for sums of possibly dependent Bernoulli random variables) $X_i$ have been obtained by the Chen--Stein method. See e.g. Theorem 1, which gives an upper bound on the total variation distance between the distribution of such a sum $W$ and a corresponding Poisson distribution in terms of certain characteristics $b_1,b_2,b_3$ of the strength of the dependence between the $X_i$'s (defined in formulas (4)--(6) of that paper).

$\endgroup$
3
$\begingroup$

Here's a connection that I found interesting.

A positive solution to the Kadison-Singer problem would follow from a positive solution to a stronger conjecture I called ${\rm KS}_2$ (and the eventual solution found by Marcus, Spielman, and Srivastava did do it this way).

The ${\rm KS}_2$ conjecture states that there exist universal constants $\delta < 1/2$ and $\epsilon > 0$ such that, for any $n$ and $k$, if vectors $v_1, \ldots , v_n \in \mathbb{C}^k$ have euclidean norm at most $\epsilon$ and satisfy $\sum_{1 \leq i \leq N} |\langle u, v_i\rangle|^2 \leq 1$ for every unit vector $u$, then there is a subset $X \subseteq \{1, \ldots, n\}$ such that $\sum_{i \in X} |\langle u, v_i\rangle|^2 \in [\frac{1}{2} - \delta, \frac{1}{2} + \delta]$ for every unit vector $u$.

The first comment is that we don't need to consider all unit vectors $u$, only finitely many $u_j$ forming a $\sigma$-net in the unit sphere of $\mathbb{C}^k$. Depending on how small $\delta$ is, $\sigma$ might not even need to be very small. So fix unit vectors $u_1, \ldots, u_M$ and choose $X \subseteq \{1, \ldots, n\}$ randomly. For each $1 \leq j \leq M$ let $E_j$ be the event that we get $\sum_{i \in X} |\langle u_j, v_i\rangle|^2 \in [\frac{1}{2} - \delta, \frac{1}{2} + \delta]$ for that $j$.

If we could say that the compound event $E_1 \cap \cdots \cap E_M$ has positive probability, the problem would be solved. The connection to the Lovász local lemma is that if the $u_j$'s aren't too close together, then the $E_j$ should be approximately independent in some sense. I guess the intuition here is that the $v_i$'s that matter the most for one $u_j$ are those nearly parallel to that $u_j$, so if the $u_j$ are sufficiently far apart then success on one $u_j$ shouldn't have too much effect on success on some other $u_j$.

I got this idea from Nets Katz and John Shareshian, and we weren't able to make it work, but I still wonder if there is some form of the local lemma which would succeed. Conversely, I guess you could say that since ${\rm KS}_2$ was actually proved, we do have something resembling the local lemma in this setting.

$\endgroup$
2
$\begingroup$

Does exchangeability qualify as a "relaxed form of independence"? There are a number of results for exchangeable sequences, for example Hong & Lee for a Weak Law of Large Numbers or Fortini, Ladelli & Regazzini for a Central Limit Theorem;

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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