Thursday, 26 February 2015

pr.probability - Can you explain the description of the Lovasz Local Lemma by Moser+Tardos?

Yes, one can prove the refinement stated in your question by a slight adaptation of the proof of the classical case.



More precisely, the proof is by recursion over the number of events in $mathbf{A}$. Like in the classical case, assuming that the statement holds for every collection of $n$ events, it is enough to show that $P(A|bar{B})le x(A)$ for every collection $mathbf{A}=${A}$cup${$A_i;1le ile n$}`, where $B$ denotes the union of the events $A_i$ for $1le ile n$ and $bar B$ denotes the complement of $B$.



The first step is to decompose $B$ into $B=Ccup F$ where $C$ is the union of the events in $Gamma(A)$ and $F$ the union of the events not in $Gamma(A)$. Hence, $P(A|bar{B})=P(A|bar{C},bar{F})=N/D$ where $N=P(A,bar{C}|bar{F})$ and $D=P(bar{C}|bar{F})$.



As regards the numerator, $Nle P(A|bar{F})=P(A)$, where the equality stems from the fact that $A$ is independent of the $A_i$ not in $Gamma(A)$, which define $F$.



Some additional work is required to deal with the denumerator. Assume wlog that $Gamma(A)=${$A_i;1le ile q$}and write $bar C$ as $bar C=bar A_1cap bar A_2capcdotscap bar A_q$. Then, by Bayes formula, $P(bar C|bar{F})$ is the product over $1le ile q$ of $P(bar A_i|bar C_i,bar{F})$, where each $C_i$ is the union of $A_j$ for $jle q$, $jne i$. Now, each of these probabilities is conditional on an event which involves at most $q-1le 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;1le ile n$}`.



Finally, $Nle P(A)le x(A)prod_{ile q}(1-x(A_i))$ and $Dgeprod_{ile q}(1-x(A_i))$ hence $P(A|bar{B})le x(A)$ for every collection $mathbf A$ of size $n+1$ as above, which proves the theorem.

No comments:

Post a Comment