# Theorems like the Lovász Local Lemma?

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.)

• Mar 14, 2019 at 17:53
• Talagrand’s concentration inequality in particular is very powerful for this kind of thing. Mar 14, 2019 at 18:09

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).

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.

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;