Lovász-Local-Lemma

Das Lovász-Local-Lemma ist ein Hilfssatz aus der Wahrscheinlichkeitstheorie. Es verallgemeinert das Argument, dass die stochastische Unabhängigkeit von Ereignissen mit positiver Wahrscheinlichkeit eine positive Wahrscheinlichkeit für das Eintreten aller Ereignisse impliziert, auf Situationen, in denen nicht alle Ereignisse unabhängig sind. Sein Name beruht darauf, dass es lokale Eigenschaften zu einem globalen Ergebnis zusammensetzt. Es findet am häufigsten Anwendung in probabilistischen Ansätzen, um Existenzbeweise zu führen. 1975 wurde es von László Lovász und Paul Erdős bewiesen.

Einen konstruktiven Beweis und eine algorithmische Version gaben Robin A. Moser und Gábor Tardos 2008/09 und erhielten dafür den Gödel-Preis (2020). Zusätzlich konnten sie die Algorithmen für die Verwendung von LLL vollständig de-randomisieren.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.