Lema local de Lovász

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

Hay 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. László Lovász y Paul Erdős probaron una versión más débil en 1975 en el artículo Problemas y resultados sobre hipergrafías tricromáticas y algunas preguntas relacionadas . Para otras versiones, consulte (Alon y 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 compresión de entropía para proporcionar un algoritmo aleatorio eficiente para encontrar un resultado en el que no ocurre ninguno de los eventos. ^{[1] [2]}

Declaraciones del lema (versión simétrica)

Sea una secuencia de eventos tal que cada evento ocurra con una probabilidad como máximo p y tal que cada evento sea independiente de todos los demás eventos excepto 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.

El lema II hoy en día 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 Ω. Denotemos a 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 reales a los eventos tal 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 en 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 sigue 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

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 estrictas (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

Probamos la versión asimétrica del lema, de la cual se puede derivar la versión simétrica. Utilizando el principio de inducción matemática demostramos que para todos en y todos los subconjuntos de eso no incluyen ,. La inducción aquí se aplica al tamaño (cardinalidad) del conjunto . Para el caso base, la afirmación obviamente se cumple desde . Necesitamos demostrar que la desigualdad es válida para cualquier subconjunto 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}}}$

Dejar . 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)}}.}$

Vinculamos el numerador y el denominador de la expresión anterior por separado. Para esto, dejemos . Primero, aprovechando 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 usando el teorema de Bayes y luego usando 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 . Tenga en cuenta que esencialmente hemos demostrado . Para obtener la probabilidad deseada, la escribimos en términos de probabilidades condicionales aplicando repetidamente el teorema de Bayes. Por eso, ${\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 exactamente a 11 puntos. En cualquier coloración de este tipo, debe haber un conjunto de n puntos que contengan un punto de cada color pero que no contenga 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, nuestra probabilidad de elegir ambos puntos en ese par es 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 .

La elección de un determinado par ( a ,  b ) de puntos depende sólo de lo que sucede en los colores de a y b , y en absoluto de si  se elige cualquier otra colección de puntos en los otros n − 2 colores. Esto implica que el evento " a y b son elegidos" depende sólo 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 a mismo), 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 ocurre con 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 ninguno de los eventos malos ocurra, 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.

Ver 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 de funciones de Ramsey". Matemáticas discretas . 20 : 69–76. doi : 10.1016/0012-365x(77)90044-9 .
4. Esquilador, J (1985). "Sobre un problema de Spencer". Combinatoria . 5 (3): 241–245. doi :10.1007/BF02579368.

Referencias

• Alón, 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 aleatorias y algoritmos . 2 (4): 343–365. doi :10.1002/rsa.3240020402.
• Czumaj, Artur; Scheideler, cristiano (2000). "Colorear hipergrafías no uniformes: un nuevo enfoque algorítmico del lema local general de Lovász". Algoritmos y estructuras aleatorias . 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].