| dbo:abstract
|
- 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. (de)
- 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 to relax the independence condition slightly: As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs. It is most commonly used in the probabilistic method, in particular to give existence proofs. There are several different versions of the lemma. The simplest and most frequently used is the symmetric version given below. A weaker version was proved in 1975 by László Lovász and Paul Erdős in the article Problems and results on 3-chromatic hypergraphs and some related questions. For other versions, see. In 2020, Robin Moser and Gábor Tardos received the Gödel Prize for their algorithmic version of the Lovász Local Lemma, which uses entropy compression to provide an efficient randomized algorithm for finding an outcome in which none of the events occurs. (en)
- En teoría de probabilidad, si una cantidad grande de eventos es tal que cualquier pareja de ellos es tal que uno es independiente del otro, y además cada evento tiene probabilidad menor que 1, entonces hay una probabilidad positiva -posiblemente pequeña-. que ninguno de los acontecimientos ocurra. El Lema local de Lovász relaja la condición de independencia ligeramente: Siempre y cuando los acontecimientos sean "mayoritariamente" independientes uno del otro, y no sean demasiado probables individualmente, entonces aún se puede concluir que hay una probabilidad positiva que ninguno de ellos ocurra. Este lema es utilizado mayoritariamente en el método probabilista, en particular para dar pruebas de existencia. Hay varias versiones diferentes del lema. La más sencilla y más frecuentemente utilizada es el la versión simétrica. Una versión más débil fue probada en 1975 por László Lovász y Paul Erdős en el artículo Problemas y resultados sobre hipergrafos 3-cromáticos y preguntas relacionadas. Otras versiones se encuentran en ( Alon & Spencer 2000 ). En 2020, Robin Moser y Gábor Tardos recibieron el Premio Gödel gracias a su versión algorítmica del Lema Local de Lovász. (es)
- Le lemme local de Lovász (parfois abrégé LLL[réf. nécessaire]) est un résultat de théorie des probabilités discrètes, dû à László Lovász et Paul Erdős. Il généralise le fait que la probabilité que des événements indépendants arrivent en même temps est égale au produit des probabilités de ces événements. Il existe plusieurs versions de ce résultat. Le lemme local est utilisé dans plusieurs domaines, notamment en combinatoire et en informatique théorique. Dans ces domaines il est parfois énoncé informellement de la manière suivante : étant donné un ensemble de mauvais événements, n'ayant pas de grande dépendances les uns avec les autres, il est possible d'éviter tous ces événements à la fois. (fr)
- Lokalny lemat Lovásza – twierdzenie w rachunku prawdopodobieństwa podające warunek wystarczający istnienia w danej przestrzeni probabilistycznej zdarzenia elementarnego, które jest niezależne względem ustalonej, skończonej liczby innych zdarzeń. Twierdzenie to jest uogólnieniem trywialnego warunku mówiącego, iż takie zdarzenie istnieje, gdy prawdopodobieństwo każdego z pozostałych rozważanych zdarzeń jest mniejsze od 1 i zdarzenia te są niezależne. Twierdzenie to zostało udowodnione w 1975 roku przez Paula Erdősa i László Lovásza. (pl)
- Локальная лемма Ловаса — лемма теории вероятностей. Если некоторое количество событий не зависит друг от друга и вероятность каждого меньше 1, то вероятность того, что ни одно из событий не произойдет, положительна. Локальная лемма Ловаса позволяет ослабить условие независимости: пока события «не сильно зависимы» друг от друга и не слишком вероятны по отдельности, вероятность того, что ни одно из них не произойдет, положительна. Этот результат чаще всего используется в вероятностном методе, в частности для доказательства существования. Существует несколько версий леммы. Симметричная версия, приведённая ниже, является самой простой и наиболее часто используемой. Более слабая версия была доказана в 1975 году Ласло Ловасом и Палом Эрдёшом в статье «Проблемы и результаты по 3-хроматическим гиперграфам и некоторые смежные вопросы». Другие версии см.. В 2020 году и получили премию Гёделя за алгоритмическую версию локальной леммы Ловаса. (ru)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11857 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Le lemme local de Lovász (parfois abrégé LLL[réf. nécessaire]) est un résultat de théorie des probabilités discrètes, dû à László Lovász et Paul Erdős. Il généralise le fait que la probabilité que des événements indépendants arrivent en même temps est égale au produit des probabilités de ces événements. Il existe plusieurs versions de ce résultat. Le lemme local est utilisé dans plusieurs domaines, notamment en combinatoire et en informatique théorique. Dans ces domaines il est parfois énoncé informellement de la manière suivante : étant donné un ensemble de mauvais événements, n'ayant pas de grande dépendances les uns avec les autres, il est possible d'éviter tous ces événements à la fois. (fr)
- Lokalny lemat Lovásza – twierdzenie w rachunku prawdopodobieństwa podające warunek wystarczający istnienia w danej przestrzeni probabilistycznej zdarzenia elementarnego, które jest niezależne względem ustalonej, skończonej liczby innych zdarzeń. Twierdzenie to jest uogólnieniem trywialnego warunku mówiącego, iż takie zdarzenie istnieje, gdy prawdopodobieństwo każdego z pozostałych rozważanych zdarzeń jest mniejsze od 1 i zdarzenia te są niezależne. Twierdzenie to zostało udowodnione w 1975 roku przez Paula Erdősa i László Lovásza. (pl)
- 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. (de)
- En teoría de probabilidad, si una cantidad grande de eventos es tal que cualquier pareja de ellos es tal que uno es independiente del otro, y además cada evento tiene probabilidad menor que 1, entonces hay una probabilidad positiva -posiblemente pequeña-. que ninguno de los acontecimientos ocurra. El Lema local de Lovász relaja la condición de independencia ligeramente: Siempre y cuando los acontecimientos sean "mayoritariamente" independientes uno del otro, y no sean demasiado probables individualmente, entonces aún se puede concluir que hay una probabilidad positiva que ninguno de ellos ocurra. Este lema es utilizado mayoritariamente en el método probabilista, en particular para dar pruebas de existencia. (es)
- 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 to relax the independence condition slightly: As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs. It is most commonly used in the probabilistic method, in particular to give existence proofs. (en)
- Локальная лемма Ловаса — лемма теории вероятностей. Если некоторое количество событий не зависит друг от друга и вероятность каждого меньше 1, то вероятность того, что ни одно из событий не произойдет, положительна. Локальная лемма Ловаса позволяет ослабить условие независимости: пока события «не сильно зависимы» друг от друга и не слишком вероятны по отдельности, вероятность того, что ни одно из них не произойдет, положительна. Этот результат чаще всего используется в вероятностном методе, в частности для доказательства существования. (ru)
|
| rdfs:label
|
- Lovász-Local-Lemma (de)
- Lema local de Lovász (es)
- Lemme local de Lovász (fr)
- Lovász local lemma (en)
- Lokalny lemat Lovásza (pl)
- Локальная лемма Ловаса (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
