Lema local de Lovász

En teoría de la probabilidad , si una gran cantidad 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 ninguno de los eventos ocurra. 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 individualmente demasiado probables, entonces seguirá existiendo una probabilidad positiva de que ninguno de ellos ocurra. Se utiliza más comúnmente en el método probabilístico , en particular para proporcionar pruebas de existencia .

Existen varias versiones diferentes del lema. La más simple y utilizada con más frecuencia es la versión simétrica que se muestra a continuación. Una versión más débil fue demostrada en 1975 por László Lovász y Paul Erdős en el artículo Problemas y resultados en hipergrafos 3-cromá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 Lema Local de Lovász, que utiliza la compresión de entropía para proporcionar un algoritmo aleatorio eficiente para encontrar un resultado en el que ninguno de los eventos ocurre. ^{[1] [2]}

Enunciados del lema (versión simétrica)

Sea una secuencia de eventos tal que cada evento ocurre con una probabilidad de como máximo p y tal que cada evento es independiente de todos los demás eventos excepto de como máximo d de ellos. ${\displaystyle A_{1},A_{2},\dots ,A_{k}}$

Lema I (Lovász y Erdős 1973; publicado en 1975) Si

${\displaystyle 4pd\leq 1}$

entonces existe una probabilidad distinta de cero de que ninguno de los eventos ocurra.

Lema II (Lovász 1977; publicado por Joel Spencer ^[3] ) Si

${\displaystyle ep(d+1)\leq 1,}$

donde e = 2,718... es la base de los logaritmos naturales, entonces existe una probabilidad distinta de cero de que ninguno de los eventos ocurra.

Hoy en día el lema II se suele denominar "lema local de Lovász".

Lema III (Shearer 1985 ^[4] ) Si

${\displaystyle {\begin{cases}p<{\frac {(d-1)^{d-1}}{d^{d}}}&d>1\\p<{\tfrac {1}{2}}&d=1\end{cases}}}$

entonces existe una probabilidad distinta de cero de que ninguno de los eventos ocurra.

El umbral en el Lema III es óptimo e implica que el límite

${\displaystyle epd\leq 1}$

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) . Sea un conjunto finito de eventos en el espacio de probabilidad Ω. Para sea denotar los vecinos de en el gráfico de dependencia (en el gráfico de dependencia, el evento no es adyacente a eventos que son mutuamente independientes). Si existe una asignación de números reales a los eventos tales que ${\displaystyle {\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}}$ ${\displaystyle A\in {\mathcal {A}}}$ ${\displaystyle \Gamma (A)}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle x:{\mathcal {A}}\to [0,1)}$

${\displaystyle \forall A\in {\mathcal {A}}:\Pr(A)\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}$

entonces la probabilidad de evitar todos los eventos es positiva, en particular ${\displaystyle {\mathcal {A}}}$

${\displaystyle \Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)\geq \prod _{i\in \{1,\cdot \cdot \cdot ,n\}}(1-x(A_{i})).}$

La versión simétrica se deriva inmediatamente de la versión asimétrica estableciendo

${\displaystyle \forall A\in {\mathcal {A}}:x(A)={\frac {1}{d+1}}}$

Para obtener la condición suficiente

${\displaystyle p\leq {\frac {1}{d+1}}\cdot {\frac {1}{e}}}$

desde

${\displaystyle {\frac {1}{e}}\leq \left(1-{\frac {1}{d+1}}\right)^{d}.}$

Constructivo versus no constructivo

Obsérvese que, como suele ocurrir con los argumentos probabilísticos, este teorema no es constructivo y no ofrece ningún método para determinar un elemento explícito del espacio de probabilidad en el que no se produce ningún evento. Sin embargo, también se conocen versiones algorítmicas del lema local con precondiciones 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 requiere precondiciones más fuertes.

Prueba no constructiva

Demostramos la versión asimétrica del lema, de la que se puede derivar la versión simétrica. Utilizando el principio de inducción matemática demostramos que para todo en y todos los subconjuntos de que no incluyen , . La inducción aquí se aplica al tamaño (cardinalidad) del conjunto . Para el caso base, la afirmación es válida obviamente ya que . Necesitamos demostrar que la desigualdad es válida para cualquier subconjunto de de una determinada cardinalidad dado que es válida para todos los subconjuntos de una cardinalidad inferior. ${\displaystyle A}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle A}$ ${\displaystyle \Pr \left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)\leq x(A)}$ ${\displaystyle S}$ ${\displaystyle S=\emptyset }$ ${\displaystyle \Pr(A_{i})\leq x\left(A_{i}\right)}$ ${\displaystyle {\mathcal {A}}}$

Sea . Tenemos del teorema de Bayes ${\displaystyle S_{1}=S\cap \Gamma (A),S_{2}=S\setminus S_{1}}$

${\displaystyle \Pr \left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)={\frac {\Pr \left(A\wedge \bigwedge _{B\in S_{1}}{\overline {B}}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)}{\Pr \left(\bigwedge _{B\in S_{1}}{\overline {B}}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)}}.}$

Acotamos por separado el numerador y el denominador de la expresión anterior. Para ello, sea . Primero, aprovechamos el hecho de que no depende de ningún evento en . ${\displaystyle S_{1}=\{B_{j1},B_{j2},\ldots ,B_{jl}\}}$ ${\displaystyle A}$ ${\displaystyle S_{2}}$

${\displaystyle {\text{Numerator}}\leq \Pr \left(A\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)=\Pr(A)\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B)).\qquad (1)}$

Desarrollando el denominador utilizando el teorema de Bayes y luego utilizando el supuesto inductivo, obtenemos

${\displaystyle {\begin{aligned}&{\text{Denominator}}\\={}&\Pr \left({\overline {B}}_{j1}\mid \bigwedge _{t=2}^{l}{\overline {B}}_{jt}\wedge \bigwedge _{B\in S_{2}}{\overline {B}}\right)\cdot \Pr \left({\overline {B}}_{j2}\mid \bigwedge _{t=3}^{l}{\overline {B}}_{jt}\wedge \bigwedge _{B\in S_{2}}{\overline {B}}\right)\cdots \Pr \left({\overline {B}}_{jl}\mid \bigwedge _{B\in S_{2}}{\overline {B}}\right)\geq \prod _{B\in S_{1}}(1-x(B))\qquad (2)\end{aligned}}}$

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 ${\displaystyle |S|}$

${\displaystyle \Pr \left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)\leq x(A)\prod _{B\in \Gamma (A)-S_{1}}(1-x(B))\leq x(A)}$

Dado que el valor de x siempre está en , observe que hemos demostrado esencialmente . Para obtener la probabilidad deseada, la escribimos en términos de probabilidades condicionales aplicando el teorema de Bayes repetidamente. Por lo tanto, ${\displaystyle [0,1)}$ ${\displaystyle \Pr \left({\overline {A}}\mid \bigwedge _{B\in S}{\overline {B}}\right)\geq 1-x(A)}$

${\displaystyle {\begin{aligned}&\Pr \left({\overline {A_{1}}}\wedge \cdots \wedge {\overline {A_{n}}}\right)\\={}&\Pr \left({\overline {A_{1}}}\mid {\overline {A_{2}}}\wedge \cdots {\overline {A_{n}}}\right)\cdot \Pr \left({\overline {A_{2}}}\mid {\overline {A_{3}}}\wedge \cdots {\overline {A_{n}}}\right)\cdots \Pr \left({\overline {A_{n}}}\right)\\\geq {}&\prod _{A\in {\mathcal {A}}}(1-x(A)),\end{aligned}}}$

que es lo que pretendíamos demostrar.

Ejemplo

Supongamos 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 a exactamente 11 puntos. En cualquier coloración de este tipo, debe haber un conjunto de n puntos que contenga un punto de cada color pero que no contenga ningún par de puntos adyacentes.

Para comprobarlo, imaginemos que elegimos un punto de cada color al azar, y que todos los puntos tienen la misma probabilidad de ser elegidos (es decir, una probabilidad de 1/11). Los 11 n eventos diferentes que queremos evitar corresponden a los 11 n pares de puntos adyacentes en el círculo. Para cada par, nuestra probabilidad de elegir ambos puntos de ese par es como máximo de 1/121 (exactamente 1/121 si los dos puntos son de colores diferentes, de lo contrario, 0), por lo que tomaremos p = 1/121 .

La elección de un par de puntos dado ( a ,  b ) depende únicamente de lo que ocurra con los colores de a y b , y no de si se elige cualquier otro conjunto de puntos de los otros n  − 2 colores. Esto implica que el evento " a y b son elegidos" depende únicamente de aquellos pares de puntos adyacentes que comparten un color con a o con b .

Hay 11 puntos en el círculo que comparten un color con a (incluido el propio a), cada uno de los cuales está involucrado 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

${\displaystyle ep(d+1)\approx 0.966<1.}$

Según el lema local, existe una probabilidad positiva de que no ocurra ninguno de los eventos negativos, lo que significa que nuestro conjunto no contiene ningún par de puntos adyacentes. Esto implica que debe existir un conjunto que satisfaga nuestras condiciones.

Véase también

• Desigualdad de Shearer

Notas

1. "El ex estudiante de doctorado Robin Moser recibe el prestigioso premio Gödel". ethz.ch . Consultado el 20 de abril de 2020 .
2. "ACM SIGACT - Premio Gödel". sigact.org . Consultado el 20 de abril de 2020 .
3. 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 .
4. 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). "Un enfoque algorítmico para el lema local de Lovász, I". Estructuras aleatorias y algoritmos . 2 (4): 343–365. doi :10.1002/rsa.3240020402.
• Czumaj, Artur; Scheideler, Christian (2000). "Coloración de hipergrafos no uniformes: un nuevo enfoque algorítmico para el lema local general de Lovász". Random Structures & Algorithms . 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 sobre hipergrafías tricromáticas 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) . vol. II. Holanda del Norte. págs. 609–627.
• Moser, Robin A. (2008). "Una prueba constructiva del lema local de Lovasz". arXiv : 0810.4812 [cs.DS].