Theorems like the Lovász Local Lemma?

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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;