In reading through the proof of Lovász Local Lemma in a probability book, I came across some questions that I hope someone could clarify.

  1. In the proof, a lower bound is found for the probability of $\bigwedge_{i=1}^n\bar{A_i},$ where $A_1,...,A_n$ are events in an arbitrary probability space. I am not sure what we are actually finding the probability of; I am not sure what the wedge notation means in this context and it does not seem to be defined in the book. Does it mean the intersection of all of the complements of $A_i, i=1,...,n$?

  2. In the proof, they let $S_1=\{j\in S: (i,j)\in E\}$ and $S_2=S-S_1$. Then they state that $$\mathbb{P}(A_i \vert \bigwedge_{j\in S}\bar{A_j})=\frac{\mathbb{P}(A_i \wedge (\bigwedge_{j\in S_1}\bar{A_j} )\vert \bigwedge_{l\in S_2}\bar{A_l})}{\mathbb{P}(\bigwedge_{j\in S_1}\bar{A_j} \vert \bigwedge_{l\in S_2}\bar{A_l})}.$$ I am not sure why this equality holds either. I know that for conditional probability in general, we have that $\mathbb{P}(E |F)=\mathbb{P}(EF)/\mathbb{P}(F)$, but I don't quite see how we have that above. Any explanation would be greatly appreciated.

  • 1
    $\begingroup$ This notation is maybe a bit old-fashioned. If $A,B$ are events, then $$A\text{ and }B = A \wedge B$$ is the event that happens iff both $A$ and $B$ happen. In Kolmogorov's model for probability, this is the intersection. $\endgroup$ – GEdgar Mar 10 '15 at 17:31
  • $\begingroup$ It's not at all old-fashioned. $\endgroup$ – Yuval Filmus Mar 10 '15 at 17:38

It's simply a case of treating events as logical propositions rather sets of outcomes.

$A\wedge B$ means "event $A$ happens and event $B$ happens". It's the conjunction or intersection of events.

$A\vee B$ means "either event $A$ happens or event $B$ happens". It's the disjunction or union of events.

The big wedge notation is the series conjunction operator. $$\bigwedge_{i=1}^n A_i = A_1\wedge A_2\wedge \cdots \wedge A_n$$

I know that for conditional probability in general, we have that $\Bbb P(E|F)=\Bbb P(EF)/\Bbb P(F)$, but I don't quite see how we have that above.

That would be written as $\Bbb P(E\mid F) = \Bbb P(E\wedge F)/\Bbb P(F)$

And we have $\Bbb P(E\mid F\wedge G) = \frac{\Bbb P(E\wedge F\wedge G)}{\Bbb P(F\wedge G)}=\frac{\Bbb P(E\wedge F\mid G)\;\Bbb P(G)}{\Bbb P(F\mid G)\;\Bbb P(G)}=\frac{\Bbb P(E\wedge F\mid G)}{\Bbb P(F\mid G)}$ , so:

$$\begin{align}\mathbb{P}(A_i \vert \bigwedge_{j\in S}\bar{A_j}) & = \Bbb P(A_i\mid \bigwedge_{j\in S_1} A_j \wedge \bigwedge_{l\in S_2} A_l) \\ & =\frac{\mathbb{P}(A_i \wedge (\bigwedge_{j\in S_1}\bar{A_j} )\vert \bigwedge_{l\in S_2}\bar{A_l})}{\mathbb{P}(\bigwedge_{j\in S_1}\bar{A_j} \vert \bigwedge_{l\in S_2}\bar{A_l})} \end{align}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.