Lema local de Lovász

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.​​

Variantes del lema (Versión simétrica)

Sea $A_{1},A_{2},\ldots ,A_{k}$ una secuencia de eventos tal que cada uno de ellos ocurre con probabilidad a lo sumo $p$ y tal que cada evento es independiente de todos los otros, excepto como máximo $d$ de ellos.

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

$4pd\leq 1$

entonces la probabilidad que ninguno de los eventos ocurra es mayor que cero.

Lema II (Lovász 1977; publicado por Joel Spencer​) Si

$ep(d+1)\leq 1,$

donde e = 2.718... es la base de los logaritmos naturales, entonces la probabilidad que ninguno de los eventos ocurra es mayor que cero.

Lema II es normalmente referido hoy como el 'Lema Local de Lovász'.

Lema III (Shearer 1985​) Si

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

entonces la probabilidad que ninguno de los eventos ocurra es mayor que cero.

El umbral en Lema III es optimal, y esto implica que la cuota

$epd\leq 1$

Es además suficiente.

Asimétrico Lovász lema local

Una formulación más general que aquella de la versión asimétrica (la cual permite que los eventos tengan distintas cuotas de probabilidad) es la siguiente:

Lema (versión asimétrica). Sea ${\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}$ un conjunto finito de eventos en un espacio de probabilidad Ω. Para $A\in {\mathcal {A}}$ , denotamos $\Gamma (A)$ los vecinos de $A$ en el grafo de dependencia (en dicho grafo de dependencia, un evento $A$ es solamente adyacente a aquellos que dependen de este, o de los cuales depende). Si existe una asignación de números reales a los acontecimientos $x:{\mathcal {A}}\to [0,1)$ tal que

$\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 acontecimientos en ${\mathcal {A}}$ es positivo; en particular

$\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 sigue inmediatamente de la versión asimétrica al asignar los valores:

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

de lo que conseguimos la condición suficiente

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

ya que

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

Constructivo versus no-constructivo

Notemos que, como a menudo en el caso de argumentos probabilistas, este teorema es no constructivo , y no nos proporciona ningún método de determinar un elemento explícito del espacio de probabilidad en el que ningún acontecimiento ocurra. Aun así, versiones algorítmicas del lema local con precondiciones más fuertes también son sabidas (Beck 1991; Czumaj y Scheideler 2000). Más recientemente, una versión constructiva del lema local fue probada por Robin Moser y Gábor Tardos, la cual no requiere preconditiones fuertes.

Prueba no constructiva

Probamos la versión asimétrica del lema, de la cual la versión simétrica puede ser derivada. Usando el principio de inducción matemática , probamos que para todo $A$ en ${\mathcal {A}}$ y todos los subconjuntos $S$ de aquel ${\mathcal {A}}$ que no incluyen a $A$, tenemos que$\Pr \left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)\leq x(A)$ La inducción la hacemos con respecto al tamaño (cardinalidad) del conjunto $S$. Para el caso base $S=\emptyset$, la condición sigue trivialmente ya que $\Pr(A_{i})\leq x\left(A_{i}\right)$. Necesitamos mostrar que la desigualdad cumple para cualquier subconjunto de ${\mathcal {A}}$ de cierta cardinalidad, dado que cumple para todos aquellos conjuntos de menos cardinalidad.

Sea $S_{1}=S\cap \Gamma (A),S_{2}=S\setminus S_{1}$ . Por el Teorema de Bayes, tenemos

$\Pr \left(A\mid \bigwedge _{B\in S}{\overline {B}}\right)={\frac {\Pr \left(A\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)}}.$

Encontramos una cuota para el numerador y el denominador de la expresión arriba por separado. Para esto, denotamos. $S_{1}=\{B_{j1},B_{j2},\ldots ,B_{jl}\}$ Primero, explotando el hecho que $A$ no depende de nungún acontecimiento en $S_{2}$:

${\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)$

Expandiendo el denominador usando el Teorema de Bayes, y luego usando la hipótesis inductiva, conseguimos

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

La hipótesis inductiva puede ser aplicada aquí desde cada acontecimiento tiene dependencia con un número pequeño de otros eventos, i.e. en un subconjunto de cardinalidad menor que la de $|S|$ . De (1) y (2), obtenemos

$\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)$

Como el valor de $x$ está siempre en $[0,1)$, notemos que hemos esencialmente probado$\Pr \left({\overline {A}}\mid \bigwedge _{B\in S}{\overline {B}}\right)\geq 1-x(A)$. Para obtener la probabilidad deseada, la escribimos en términos de probabilidades condicionales aplicando el Teorema de Bayes repetidamente. De ahí,

${\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 buscábamos probar.

Ejemplo

Supongamos que $11n$ puntos están colocados alrededor de un círculo y se colorean con $n$ colores diferentes de tal manera que cada color está aplicado a exactamente $11$ puntos. En cualquier tal coloración, tiene que haber un conjunto de $n$ puntos que contienen un punto de cada color, pero ningún par de puntos adyacentes.

Para ver esto, imaginemos que elegimos un punto de cada color aleatoriamente, teniendo todos los puntos igual probabilidad (i.e., $1/11$) para ser escogidos. Los $11n$ acontecimientos diferentes que queremos evitar corresponden a los $11n$ pares de puntos adyacentes en el círculo. Para cada par, nuestras probabilidades de elegir ambos puntos en aquella pareja es como máximo $1/121$ (exactamente $1/121$ si los dos puntos son de colores diferentes, de otro modo $0$), así que tomaremos $p=1/121$.

Si una pareja de puntos $(a,b)$ es escogida depende solamente en lo que ocurre en los colores de $a$ y $b$, y no depende en absoluto en si cualquier otra colección de puntos en los otros $n-2$ colores es escogida. Esto implica que el acontecimiento "$a$ y $b$ son ambos escogidos" depende sólo en 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$ (incluyendo el mismo punto), cada uno de los cuales está implicado con 2 pares. Esto significa que hay 21 pares además de $(a,b)$ los cuales incluyen el mismo color que $a$, y los mismos cumple para $b$. Lo peor que puede ocurrir es que estos dos conjuntos sean disjuntos, así que podemos tomar $d=42$ en el lema. Esto nos da

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

Por el lema local, hay una probabilidad positiva que ninguno de los acontecimientos malos ocurra, por lo que nuestro conjunto no contiene ningún par de puntos adyacentes. Esto implica que un conjunto que satisface nuestras condiciones tiene que existir.

Notas

1. ↑ ​
2. ↑​
3. ↑​
4. ↑

Referencias

• Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2nd edición). New York: Wiley-Interscience. ISBN 0-471-37046-0. 
• Beck, J. (1991). «An algorithmic approach to the Lovász local lemma, I». Random Structures and Algorithms 2 (4): 343-365. doi:10.1002/rsa.3240020402. 
• Czumaj, Artur; Scheideler, Christian (2000). «Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma». 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. 
• Erdos, Paul; Lovász, László (1975) 'Problems and results on 3-chromatic hypergraphs and some related questions' (PDF) En A. Hajnal, ed. (1975). II. pp. 609-627. 
•  Moser, Robin A. (2008). 'Una prueba constructiva del Lema Local de Lovasz'. arXiv:0810.4812 [cs.DS]

• Datos: Q831721