The Lovász Local Lemma (or **LLL**) concerns itself with the probability of avoiding a collection of "bad" events **A**, given that the set of events is "nearly independent" (each bad event *A* ∈ **A** has probability which is bounded above in terms of the number of other events *A*', *A*'', etc. from which it is not independent), there is a non-zero probability of avoiding all of the bad events simultaneously. The original presentation seems to be the Lemma on page 8 of this pdf (the link to which can be found on Wikipedia's page on the LLL); several other papers present it in a similar fashion.

In the article [arXiv:0903.0544], restricting to the setting where the "bad events" of the LLL are defined in terms of a probability space of independently distributed bits, Moser and Tardos present a probabilistic algorithm for sampling from the event space until an event is found which avoids all bad events, which requires at most polynomially many samples with high probability. However, their characterization of the LLL is significantly different from any presentation of it that I have seen elsewhere. Their version of the LLL is as follows:

Theorem.LetAbe a finite set of events in a probability space. ForA∈Alet Γ(A) be a subset ofAsatisfying thatAis independent from the collection of eventsA\ ({A} ∪ Γ(A)). If there exists an assignment of reals x :A→ (0,1) such that $$ \forall A \in \mathbf A : \Pr[A] \;\leqslant\; \mathrm x(A) \prod_{B \in \Gamma(A)} (1-\mathrm x(B))$$then the probability of avoiding all events in A is at least $\prod\limits_{A \in \mathbf A} \;(1 \;−\; \mathrm x(A))$, in particular it is positive.

The proof that their sampling algorithm works seems to depend substantially upon this presentation of the LLL, but I cannot decipher the exact relationship between this and more common presentations of it. It looks as though the product over Γ(*A*) in the bounding condition "wants to be" a bound on the conditional probabilities for events *A*, but I haven't been able to make the link. Could someone help me with the connection between this statement and more familar versions of the LLL?