The symmetric Lovasz Local Lemma

If each bad event has probability at most \(p\) and is independent of all but at most \(d\) others, and \(e p (d+1) \le 1\), then with positive probability none occurs.

Usage

morie_lovasz_local_lemma(p, d)

Arguments

p

Event probability.

d

Dependency degree.

Value

A list with condition_value, applies, max_degree_at_p, max_probability_at_d.

Details

What makes it remarkable is that the union bound is useless once \(mp \ge 1\) however small the dependency, while the Local Lemma does not care how many events there are at all – only how entangled each one is.

References

Erdos P, Lovasz L (1975). Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets (Colloquia Mathematica Societatis Janos Bolyai, Vol. 10), North-Holland.

Examples

morie_lovasz_local_lemma(p = 0.5, d = 5L)
#> $condition_value
#> [1] 8.154845
#> 
#> $applies
#> [1] FALSE
#> 
#> $p
#> [1] 0.5
#> 
#> $d
#> [1] 5
#> 
#> $max_degree_at_p
#> [1] -1
#> 
#> $max_probability_at_d
#> [1] 0.06131324
#> 
#> $slack
#> [1] -7.154845
#> 
#> $n
#> [1] 5
#> 
#> $method
#> [1] "Lovasz Local Lemma (Erdos and Lovasz 1975)"
#>