¿Puede explicar la descripción del Lemma Local de Lovasz de Moser+Tardos?

Question

El lema local de Lovász (o LLL ) se ocupa de la probabilidad de evitar una colección de eventos "malos" A dado que el conjunto de sucesos es "casi independiente" (cada suceso malo A  ∈  A tiene una probabilidad acotada en función del número de otros eventos A ', A '', etc. del que no es independiente), existe una probabilidad no nula de evitar todos los sucesos malos simultáneamente. La presentación original parece ser el lema de la página 8 de este pdf (cuyo enlace se encuentra en Página de Wikipedia sobre el LLL ); otros trabajos lo presentan de forma similar.

En el artículo [ arXiv:0903.0544 En el caso de los "eventos malos" de la LLL, que se definen en términos de un espacio de probabilidad de bits distribuidos de forma independiente, Moser y Tardos presentan un algoritmo probabilístico para el muestreo del espacio de eventos hasta que se encuentre un evento que evite todos los eventos malos, lo que requiere como máximo un número polinomial de muestras con alta probabilidad. Sin embargo, su caracterización de la LLL es significativamente diferente de cualquier presentación de la misma que haya visto en otros lugares. Su versión del LLL es la siguiente:

Teorema. Dejemos que A sea un conjunto finito de eventos en un espacio de probabilidad. Para A  ∈  A que Γ( A ) sea un subconjunto de A que satisfaga que A es independiente de la colección de eventos A  \ ({ A } ∪ Γ( A )). Si existe una asignación de reales x :  A   (0,1) tal que $$ \forall A \in \mathbf A : \Pr[A] \;\leqslant\; \mathrm x(A) \prod_{B \in \Gamma(A)} (1-\mathrm x(B))$$

entonces la probabilidad de evitar todos los eventos en A es al menos $\prod\limits_{A \in \mathbf A} \;(1 \;\; \mathrm x(A))$ En particular, es positivo.

La prueba de que su algoritmo de muestreo funciona parece depender sustancialmente de esta presentación de la LLL, pero no puedo descifrar la relación exacta entre ésta y otras presentaciones más comunes de la misma. Parece que el producto sobre Γ( A ) en la condición de limitación "quiere ser" una limitación de las probabilidades condicionales de los sucesos A pero no he podido hacer el enlace. ¿Podría alguien ayudarme con la conexión entre esta declaración y las versiones más conocidas de la LLL?

Answer 1

La versión del LLL que escribiste arriba es más fuerte que la de la página 8 del documento que enlazaste. La que enlazas se conoce a veces como la "forma simétrica" del LLL y la que escribiste arriba como la "forma general".

Para ver que la forma general implica la forma simétrica: resérvese al caso en que $|\Gamma(A)|\leq d$ para todos $A$ (como se supone en la forma simétrica), y que $x(A)$ sea una constante $x$ tal que $x(1-x)^d \geq 1/(4d)$ . (Compruebe que siempre puede encontrar tal $x$ ).

Entonces la condición $P(A) \leq 1/(4d)$ en la forma simétrica implica la condición

$P(A) \leq x(A) \prod_{B\in\Gamma(A)} (1-x(B))$

que es la hipótesis de la forma general.

Una referencia estándar es el capítulo 5 del libro de Alon y Spencer, "El método probabilístico". Por supuesto, ¡no cubre el nuevo enfoque de Moser!

Answer 2

Sí, se puede demostrar el refinamiento planteado en su pregunta mediante una ligera adaptación de la prueba del caso clásico.

Más precisamente, la prueba es por recursión sobre el número de eventos en $\mathbf{A}$ . Como en el caso clásico, suponiendo que la afirmación es válida para cada colección de $n$ eventos, basta con mostrar que $P(A|\bar{B})\le x(A)$ para cada colección $\mathbf{A}=$ { A } $\cup$ { $A_i;1\le i\le n$ }`, donde $B$ denota la unión de los eventos $A_i$ para $1\le i\le n$ y $\bar B$ denota el complemento de $B$ .

El primer paso es descomponer $B$ en $B=C\cup F$ donde $C$ es la unión de los eventos en $\Gamma(A)$ y $F$ la unión de los eventos no en $\Gamma(A)$ . Por lo tanto, $P(A|\bar{B})=P(A|\bar{C},\bar{F})=N/D$ donde $N=P(A,\bar{C}|\bar{F})$ y $D=P(\bar{C}|\bar{F})$ .

En cuanto al numerador, $N\le P(A|\bar{F})=P(A)$ donde la igualdad proviene del hecho de que $A$ es independiente del $A_i$ no en $\Gamma(A)$ que definen $F$ .

Se requiere un trabajo adicional para tratar con el denumante. Supongamos wlog que $\Gamma(A)=$ { $A_i;1\le i\le q$ } and write $\bar C$ as $\bar C=\bar A_1\cap \bar A_2\cap\cdots\cap \bar A_q$. Then, by Bayes formula, $P(\bar C|\bar{F})$ is the product over $1\le i\le q$ of $P(\bar A_i|\bar C_i,\bar{F})$, where each $C_i$ is the union of $A_j$ for $j\le q$, $j\ne i$. Now, each of these probabilities is conditional on an event which involves at most $q-1\le n$ events in $\mathbf A$ hence $P(\bar A_i|\bar C_i,\bar{F})\ge1-x(A_i)$ by the recursion hypothesis applied to the collection { $A_i;1\le i\le n$ }`.

Finalmente, $N\le P(A)\le x(A)\prod_{i\le q}(1-x(A_i))$ y $D\ge\prod_{i\le q}(1-x(A_i))$ por lo que $P(A|\bar{B})\le x(A)$ para cada colección $\mathbf A$ de tamaño $n+1$ como arriba, lo que demuestra el teorema.