Lema local de Lovász

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

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

${\displaystyle 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^[3]) Si

${\displaystyle 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^[4]) Si

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

${\displaystyle epd\leq 1}$

Es además suficiente.

Summarize Timeline Fact Check

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 ${\displaystyle {\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}}$ un conjunto finito de eventos en un espacio de probabilidad Ω. Para ${\displaystyle A\in {\mathcal {A}}}$ , denotamos ${\displaystyle \Gamma (A)}$ los vecinos de ${\displaystyle A}$ en el grafo de dependencia (en dicho grafo de dependencia, un evento ${\displaystyle 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 ${\displaystyle x:{\mathcal {A}}\to [0,1)}$ tal que

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

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

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

de lo que conseguimos la condición suficiente

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

ya que

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

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.

Summarize Timeline Top Qs Fact Check

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 ${\displaystyle A}$ en ${\displaystyle {\mathcal {A}}}$ y todos los subconjuntos ${\displaystyle S}$ de aquel ${\displaystyle {\mathcal {A}}}$ que no incluyen a ${\displaystyle A}$, tenemos que${\displaystyle \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 ${\displaystyle S}$. Para el caso base ${\displaystyle S=\emptyset }$, la condición sigue trivialmente ya que ${\displaystyle \Pr(A_{i})\leq x\left(A_{i}\right)}$. Necesitamos mostrar que la desigualdad cumple para cualquier subconjunto de ${\displaystyle {\mathcal {A}}}$ de cierta cardinalidad, dado que cumple para todos aquellos conjuntos de menos cardinalidad.

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

${\displaystyle \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. ${\displaystyle S_{1}=\{B_{j1},B_{j2},\ldots ,B_{jl}\}}$ Primero, explotando el hecho que ${\displaystyle A}$ no depende de nungún acontecimiento en ${\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)}$

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

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

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 ${\displaystyle |S|}$ . De (1) y (2), obtenemos

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

Como el valor de ${\displaystyle x}$ está siempre en ${\displaystyle [0,1)}$, notemos que hemos esencialmente probado${\displaystyle \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í,

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