En la teoría de la probabilidad , si un gran número de eventos son todos independientes entre sí y cada uno tiene una probabilidad menor que 1, entonces existe una probabilidad positiva (posiblemente pequeña) de que no ocurra ninguno de los eventos. El lema local de Lovász permite relajar ligeramente la condición de independencia: siempre que los eventos sean "en su mayoría" independientes entre sí y no sean demasiado probables individualmente, habrá una probabilidad positiva de que ninguno de ellos ocurra. Se utiliza con mayor frecuencia en el método probabilístico , en particular para dar pruebas de existencia .
Hay varias versiones diferentes del lema. La versión más simple y utilizada con mayor frecuencia es la simétrica que se proporciona a continuación. 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 hipergráficos tricromáticos y algunas preguntas relacionadas . Para otras versiones, consulte ( Alon & Spencer 2000 ). En 2020, Robin Moser y Gábor Tardos recibieron el Premio Gödel por su versión algorítmica del Lovász Local Lemma. [1] [2]
Declaraciones del lema (versión simétrica)
Sea A 1 , A 2 , ..., A k una secuencia de eventos tal que cada evento ocurra con probabilidad como máximo py tal que cada evento sea independiente de todos los demás eventos excepto como máximo d de ellos.
Lema I (Lovász y Erdős 1973; publicado 1975) Si
entonces existe una probabilidad distinta de cero de que no ocurra ninguno de los eventos.
Lema II (Lovász 1977; publicado por Joel Spencer [3] ) Si
donde e = 2.718 ... es la base de los logaritmos naturales, entonces existe una probabilidad distinta de cero de que no ocurra ninguno de los eventos.
En la actualidad, el lema II se suele denominar "lema local de Lovász".
Lema III (Shearer 1985 [4] ) Si
entonces existe una probabilidad distinta de cero de que no ocurra ninguno de los eventos.
El umbral en el Lema III es óptimo e implica que el límite
también es suficiente.
Lema local asimétrico de Lovász
Una declaración de la versión asimétrica (que permite eventos con diferentes límites de probabilidad) es la siguiente:
Lema (versión asimétrica) . Dejarser un conjunto finito de eventos en el espacio de probabilidad Ω. Para dejar denotar los vecinos de en el gráfico de dependencia (en el gráfico de dependencia, evento no es adyacente a eventos que son mutuamente independientes). Si existe una cesión de reales a los eventos tales que
entonces la probabilidad de evitar todos los eventos en es positivo, en particular
La versión simétrica sigue inmediatamente a la versión asimétrica estableciendo
para conseguir la condición suficiente
desde
Constructivo versus no constructivo
Tenga en cuenta que, como suele ocurrir con los argumentos probabilísticos, este teorema no es constructivo y no proporciona ningún método para determinar un elemento explícito del espacio de probabilidad en el que no ocurre ningún evento. Sin embargo, también se conocen versiones algorítmicas del lema local con condiciones previas más fuertes (Beck 1991; Czumaj y Scheideler 2000). Más recientemente, Robin Moser y Gábor Tardos dieron una versión constructiva del lema local que no requería condiciones previas más estrictas.
Prueba no constructiva
Demostramos la versión asimétrica del lema, de la cual se puede derivar la versión simétrica. Usando el principio de inducción matemática demostramos que para todos en y todos los subconjuntos de que no incluyen , . La inducción aquí se aplica sobre el tamaño (cardinalidad) del conjunto. Para el caso base la declaración obviamente se mantiene desde . Necesitamos mostrar que la desigualdad es válida para cualquier subconjunto dede cierta cardinalidad dado que se aplica a todos los subconjuntos de una cardinalidad inferior.
Dejar . Tenemos del teorema de Bayes
Unimos el numerador y el denominador de la expresión anterior por separado. Por esto, deja. Primero, explotando el hecho de que no depende de ningún evento en .
Expandiendo el denominador usando el teorema de Bayes y luego usando la suposición inductiva, obtenemos
El supuesto inductivo se puede aplicar aquí ya que cada evento está condicionado a un número menor de otros eventos, es decir, a un subconjunto de cardinalidad menor que . De (1) y (2), obtenemos
Dado que el valor de x siempre está en. Tenga en cuenta que esencialmente hemos probado. Para obtener la probabilidad deseada, la escribimos en términos de probabilidades condicionales aplicando el teorema de Bayes repetidamente. Por eso,
que es lo que pretendíamos demostrar.
Ejemplo
Suponga que se colocan 11 n puntos alrededor de un círculo y se colorean con n colores diferentes de tal manera que cada color se aplica exactamente a 11 puntos. En cualquiera de estos colores, debe haber un conjunto de n puntos que contengan un punto de cada color pero que no contengan ningún par de puntos adyacentes.
Para ver esto, imagine elegir un punto de cada color al azar, con todos los puntos con la misma probabilidad (es decir, con una probabilidad de 1/11) de ser elegidos. Los 11 n eventos diferentes que queremos evitar corresponden a los 11 n pares de puntos adyacentes en el círculo. Para cada par, nuestras probabilidades de elegir ambos puntos en ese par son como máximo 1/121 (exactamente 1/121 si los dos puntos son de diferentes colores, de lo contrario 0), por lo que tomaremos p = 1/121 .
Si un par dado ( un , b es elegido) de puntos depende sólo de lo que sucede en los colores de un y b , y en absoluto de si cualquier otra colección de puntos en la otra n - 2 se eligen colores. Esto implica el evento " una y b son ambos escogidos" depende sólo en aquellos pares de puntos adyacentes que comparten un color ya sea con una o con b .
Hay 11 puntos en el círculo que comparten un color con una (incluyendo una en sí), cada uno de los cuales está implicado con 2 pares. Esto significa que hay 21 pares distintos de ( a , b ) que incluyen el mismo color que a , y lo mismo es válido para b . Lo peor que puede pasar es que estos dos conjuntos sean disjuntos, por lo que podemos tomar d = 42 en el lema. Esto da
Según el lema local, existe una probabilidad positiva de que no ocurra ninguno de los eventos malos, lo que significa que nuestro conjunto no contiene un par de puntos adyacentes. Esto implica que debe existir un conjunto que satisfaga nuestras condiciones.
Notas
- ^ "El ex estudiante de doctorado Robin Moser recibe el prestigioso premio Gödel" . ethz.ch . Consultado el 20 de abril de 2020 .
- ^ "ACM SIGACT - Premio Gödel" . sigact.org . Consultado el 20 de abril de 2020 .
- ^ Spencer, J. (1977). "Límites inferiores asintóticos para funciones de Ramsey". Matemáticas discretas . 20 : 69–76. doi : 10.1016 / 0012-365x (77) 90044-9 .
- ^ Shearer, J (1985). "Sobre un problema de Spencer". Combinatorica . 5 (3): 241–245. doi : 10.1007 / BF02579368 .
Referencias
- Alon, Noga ; Spencer, Joel H. (2000). El método probabilístico (2ª ed.). Nueva York: Wiley-Interscience. ISBN 0-471-37046-0.
- Beck, J . (1991). "Una aproximación algorítmica al lema local de Lovász, I". Estructuras y algoritmos aleatorios . 2 (4): 343–365. doi : 10.1002 / rsa.3240020402 .
- Czumaj, Artur; Scheideler, Christian (2000). "Colorear hipergrafías no uniformes: un nuevo enfoque algorítmico para el lema local general de Lovász". Estructuras y algoritmos aleatorios . 17 (3–4): 213–237. doi : 10.1002 / 1098-2418 (200010/12) 17: 3/4 <213 :: AID-RSA3> 3.0.CO; 2-Y .
- Erdős, Paul ; Lovász, László (1975). "Problemas y resultados de los hipergráficos 3 cromáticos y algunas cuestiones relacionadas" (PDF) . En A. Hajnal; R. Rado; VT Sós (eds.). Conjuntos infinitos y finitos (a Paul Erdős en su 60 cumpleaños) . II . Holanda Septentrional. págs. 609–627.
- Moser, Robin A. (2008). "Una prueba constructiva del Lema Local de Lovasz". arXiv : 0810.4812 [ cs.DS ].