In
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
, the algorithmic Lovász local lemma gives an algorithmic way of constructing objects that obey a system of constraints with limited dependence.
Given a finite set of ''bad'' events in a probability space with limited dependence amongst the ''A
i''s and with specific bounds on their respective probabilities, the
Lovász local lemma In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur. The Lovász local lemma allows one ...
proves that with non-zero probability all of these events can be avoided. However, the lemma is non-constructive in that it does not provide any insight on ''how'' to avoid the bad events.
If the events are determined by a finite collection of mutually independent random variables, a simple
Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the ...
with
expected polynomial runtime proposed by
Robin Moser
Robin may refer to:
Animals
* Australasian robins, red-breasted songbirds of the family Petroicidae
* Many members of the subfamily Saxicolinae (Old World chats), including:
**European robin (''Erithacus rubecula'')
** Bush-robin
**Forest r ...
and
Gábor Tardos[
] can compute an assignment to the random variables such that all events are avoided.
Review of Lovász local lemma
The Lovász Local Lemma is a powerful tool commonly used in the
probabilistic method
The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects fr ...
to prove the existence of certain complex mathematical objects with a set of prescribed features. A typical proof proceeds by operating on the complex object in a random manner and uses the Lovász Local Lemma to bound the probability that any of the features is missing. The absence of a feature is considered a ''bad event'' and if it can be shown that all such bad events can be avoided simultaneously with non-zero probability, the existence follows. The lemma itself reads as follows:
Let be a finite set of events in the probability space Ω. For let denote a subset of such that is independent from the collection of events . If there exists an assignment of reals to the events such that
:
then the probability of avoiding all events in is positive, in particular
:
Algorithmic version of the Lovász local lemma
The Lovász Local Lemma is non-constructive because it only allows us to conclude the existence of structural properties or complex objects but does not indicate how these can be found or constructed efficiently in practice. Note that random sampling from the probability space Ω is likely to be inefficient, since the probability of the event of interest
: