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.[1][2]
Variantes del lema (Versión simétrica)
Sea
una secuencia de eventos tal que cada uno de ellos ocurre con probabilidad a lo sumo
y tal que cada evento es independiente de todos los otros, excepto como máximo
de ellos.
Lema I (Lovász y Erdős 1973; publicado en 1975) Si
![{\displaystyle 4pd\leq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d641bf2d9ee03a0d94cccb2cf3c9b2a3bb544f3)
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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/683940cb400e8e27c8972b1bb8ce134cf81680e4)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4eb23c5f8d0fd85ec43359e09f207ec8973585cf)
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88c066f7f593f2786959a8fbb9b1d6ccbe49f0d8)
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
un conjunto finito de eventos en un espacio de probabilidad Ω. Para
, denotamos
los vecinos de
en el grafo de dependencia (en dicho grafo de dependencia, un evento
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
tal que
![{\displaystyle \forall A\in {\mathcal {A}}:\Pr(A)\leq x(A)\prod _{B\in \Gamma (A)}(1-x(B))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ed1d8b214ee8e18c2313e8a139fe2decfcae4f9)
Entonces la probabilidad de evitar todos los acontecimientos en
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})).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aaafe8699a7ac1036caef9540da50db0247d63f3)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbd5078ddb387668d81ff13bc8b7d27adb016416)
de lo que conseguimos la condición suficiente
![{\displaystyle p\leq {\frac {1}{d+1}}\cdot {\frac {1}{e}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23c6d516951388a4b7704b5a4efdf8a5d505d7eb)
ya que
![{\displaystyle {\frac {1}{e}}\leq \left(1-{\frac {1}{d+1}}\right)^{d}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c37c193421b9b91045e5774d31662ed70845d96)
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
en
y todos los subconjuntos
de aquel
que no incluyen a
, tenemos que
La inducción la hacemos con respecto al tamaño (cardinalidad) del conjunto
. Para el caso base
, la condición sigue trivialmente ya que
. Necesitamos mostrar que la desigualdad cumple para cualquier subconjunto de
de cierta cardinalidad, dado que cumple para todos aquellos conjuntos de menos cardinalidad.
Sea
. 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)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b6fe6b9f0645dbc9ccbd4f212b5d211f6eea143)
Encontramos una cuota para el numerador y el denominador de la expresión arriba por separado. Para esto, denotamos.
Primero, explotando el hecho que
no depende de nungún acontecimiento en
:
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe0a0c5c8d23b12cfd14bf7631b7d1723db41e7a)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6c0ead825695a3634a7fc1f947d586d1c2100ab)
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
. 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8e9cfbcdd51d11358f640d6041aea6ff265b2d8)
Como el valor de
está siempre en
, notemos que hemos esencialmente probado
. 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3eca954a2364b1a871b6983cb8a1374ebeaedb01)
Que es lo que buscábamos probar.
Ejemplo
Supongamos que
puntos están colocados alrededor de un círculo y se colorean con
colores diferentes de tal manera que cada color está aplicado a exactamente
puntos. En cualquier tal coloración, tiene que haber un conjunto de
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.,
) para ser escogidos. Los
acontecimientos diferentes que queremos evitar corresponden a los
pares de puntos adyacentes en el círculo. Para cada par, nuestras probabilidades de elegir ambos puntos en aquella pareja es como máximo
(exactamente
si los dos puntos son de colores diferentes, de otro modo
), así que tomaremos
.
Si una pareja de puntos
es escogida depende solamente en lo que ocurre en los colores de
y
, y no depende en absoluto en si cualquier otra colección de puntos en los otros
colores es escogida. Esto implica que el acontecimiento "
y
son ambos escogidos" depende sólo en aquellos pares de puntos adyacentes que comparten un color con
o con
.
Hay 11 puntos en el círculo que comparten un color con
(incluyendo el mismo punto), cada uno de los cuales está implicado con 2 pares. Esto significa que hay 21 pares además de
los cuales incluyen el mismo color que
, y los mismos cumple para
. Lo peor que puede ocurrir es que estos dos conjuntos sean disjuntos, así que podemos tomar
en el lema. Esto nos da
![{\displaystyle ep(d+1)\approx 0.966<1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66c9c47799bf2febf5643e9262debd308964f3fc)
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]
- ↑Error en la cita: La etiqueta de apertura
<ref>
es incorrecta o tiene el nombre mal
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]