Lesson 3

To better understand the theorem's condition, let us provide some comments and give a couple of examples before proving it. The function \(\Gamma\) is exactly the localizer we mentioned above: each \(A \in \mathcal{A}\) may depend only on sets from \(\Gamma(A)\). At the same time, \(A\) may not depend on some events from \(\Gamma(A)\). Moreover, there may exist many different functions \(\Gamma\) and \(p\) satisfying the lemma's condition. The conditions on \(\Gamma\) and \(p\) pull us in different directions: the larger the set \(\Gamma(A)\), the easier it is to satisfy the first condition, but the harder it is to satisfy the second.

Now, let us give two examples.

• Suppose \(A_{1}, \dotsc, A_{n}\) are mutually independent. Then \(\Gamma\) and \(p\) can be defined as follows: \(\Gamma(A)=\varnothing\), \(p(A)=\Pr[A]\). The lemma's inequality then reduces to an equality for the probability of the intersection of independent events. In this sense, the lemma generalizes full independence to, roughly speaking, independence with local dependencies.


• Toss three coins, and for \(1 \le i < j \le 3\) let \(A_{ij}\) denote the event “coins \(i\) and \(j\) landed the same.” As we recall, these three events are not mutually independent but are pairwise independent. This means that for each of our three events \(A\), the set \(\Gamma(A)\) must contain at least one other event. For example, like this: \[\Gamma(A_{12})=\{A_{13}\}, \quad \Gamma(A_{12})=\{A_{13}, A_{23}\}, \quad \Gamma(A_{23})=\{A_{12}\}.\] It is not possible to define the function \(p\) to satisfy the lemma's conditions (try it!).