2. Proof of Theorem 1

The proof of Theorem 1, our main result, will consist of a sequence of lemmas.

The first of these, Lemma 1, is essentially the proof of Theorem 1 in the case when the $\sigma$-fields $\mathcal{G}$ and ${\mathcal{H}}$ are very simple. The lemma is applied only once, at the very end of the proof of Theorem 1 (at the end of the paper).

Lemma 2 contains an elementary argument showing that one can discretize the problem, i.e., that it is enough to prove Theorem 1 in the case when $\mathcal{G}$ and ${\mathcal{H}}$ are finite.

The remaining lemmas form a reduction argument. Each lemma presents and analyzes a transformation that either decreases the size of $\mathcal{G}$ or ${\mathcal{H}}$ (and does not increase the size of the other $\sigma$-field), or moves the probability mass around the probability space to make it more ‘structured’. The latter aspect of the argument resembles a sliding puzzle with 15 squares, or a Rubik’s Cube. A more detailed and rigorous description of this part of the proof is given below, between the proof of Lemma 2 and the statement of Lemma 3.

We end our introductory remarks about the proof with the observation that our proof is constructive in the following sense. If a probability space is given explicitly, i.e., all relevant probabilities have known numerical values, then all steps of our argument can be implemented in an algorithm that will generate a finite sequence of probability spaces such that, for a fixed $\delta$, the value of ${\operatorname{\mathbb{P}}}(|X-Y| \geq 1-\delta)$ will increase or stay the same with every transformation. As a result, for any probability space one can effectively construct a much simpler probability space with ${\operatorname{\mathbb{P}}}(|X-Y| \geq 1-\delta)$ greater than or equal to that for the original probability space.

Fix any $\delta \in (0, 1/2)$. Most elements of the model (sets, probabilities) will change within this section, but the value of $\delta$ will remain fixed.

Proof. Assume without loss of generality that

Suppose that we can prove that

Then

and, therefore,

This implies (2.1), so it will suffice to prove (2.2).

Let

Then

For $p_2=0$ we obtain

For $p_2=1$,

The right-hand side of (2.3) is a linear function of $p_2$, so (2.3)–(2.5) imply that for all $p_2\in[0, 1]$,

This completes the proof of (2.2). □

Proof. It is obvious that $\lambda'(\delta) \leq \lambda(\delta)$. It remains to prove the opposite inequality.

For $n>1$, let $\mathcal{G}_n$ be the $\sigma$-field generated by the events $ \{k/n \leq X <( k+1)/n\}$, $0 \leq k \leq n$ (note that $k=n$ is included). Let $X_n={\operatorname{\mathbb{P}}}(A\mid \mathcal{G}_n)$. Since

we have

Similarly, let ${\mathcal{H}}_n$ be the $\sigma$-field generated by the events $ \{k/n \leq Y <( k+1)/n\}$, $0 \leq k \leq n$, and $Y_n={\operatorname{\mathbb{P}}}(A\mid {\mathcal{H}}_n)$. Then

It follows that

Since n can be arbitrarily large, (2.6) implies that if one can prove that $\lambda'(\delta) = 2 \delta/(1+\delta)$ for all $\delta\in(0,1/2)$, then $\lambda(\delta) = 2 \delta/(1+\delta)$ for all $\delta\in(0,1/2)$. □

Proof. Since ${\operatorname{\mathbb{P}}}(B)>0$, we must have either $ m_-(\mathcal{G}) \geq 1$, $ m_+({\mathcal{H}}) \leq m({\mathcal{H}})$, and

or $ m_-({\mathcal{H}}) \geq 1$, $m_+(\mathcal{G}) \leq m(\mathcal{G})$, and

By symmetry, it will suffice to discuss only one of these cases.

Suppose that $ m_-(\mathcal{G}) \geq 1$, $ m_+({\mathcal{H}}) \leq m({\mathcal{H}})$, and (2.22) holds. If $ m_-({\mathcal{H}}) \geq 1$, $m_+(\mathcal{G}) \leq m(\mathcal{G})$, and (2.23) is true, then we set ${\textbf{S}}'={\textbf{S}}$ and we are done. Suppose otherwise. We will assume that $ m_-({\mathcal{H}}) =0$ and $m_+(\mathcal{G}) =\infty$. It is easy to see that the argument given below applies also in the case when $ m_-({\mathcal{H}}) \geq 1$, $m_+(\mathcal{G}) \leq m(\mathcal{G})$, and (2.23) does not hold.

Let

where the $\omega^{\prime}_{k,j}$ are all distinct and do not belong to $\Omega$. Let

Fix any $\varepsilon>0$. Let $\varepsilon_1>0$ be so small that

It is elementary to see that we can define a probability measure ${\operatorname{\mathbb{P}}}'$ on $\Omega'$ with the following properties:

Note that $x_{m(\mathcal{G})+1} = 1$ and

Hence, $C^{\prime}_{m(\mathcal{G})+1, 0} \subset B'$. Let us shift the index for the generators $H^{\prime}_j$ of ${\mathcal{H}}'$ so that the generators are $H^{\prime}_1, H^{\prime}_2, \dots, H^{\prime}_{m({\mathcal{H}})+1}$. We see that $m'(\mathcal{G}') = m(\mathcal{G})+1$, $m'({\mathcal{H}}') = m({\mathcal{H}})+1$, $ m^{\prime}_-({\mathcal{H}}') \geq 1$, $m^{\prime}_+(\mathcal{G}') \leq m'(\mathcal{G}')$, and (2.21) holds. It remains to note that, in view of (2.24),

□

Proof. Let $\Omega'$ be defined as follows:

where all listed elements are distinct. Let

for all $1\leq j \leq m(\mathcal{G}) $ and $ 1\leq k \leq m({\mathcal{H}})$, except that $C^{\prime}_{j_1,k_2}\cap A' =\{\omega^{\prime}_{j_1,k_1,1}, \omega^{\prime}_{j_1,k_1,3}\}$. Let $F = \{\omega^{\prime}_{j_1,k_1,1}\}$.

Define the probability measure on $\Omega'$ by

for all $1\leq j \leq m(\mathcal{G}) $ and $ 1\leq k \leq m({\mathcal{H}})$, and

It is elementary to check that ${\textbf{S}}'$ satisfies the lemma. □

In graphical terms, the condition (2.25) means that the thick polygonal line extends in a straight fashion along the boundaries of at least two consecutive cells in the interior of the rectangle in Figure 2. There are several such ‘long’ thick line segments in Figure 2.

Proof of Lemma 5. Let

Let $\mathcal{G}'$ be the $\sigma$-field generated by $\{G^{\prime}_j\}_{1\leq j \leq m(\mathcal{G})-1}$. All other objects in ${\textbf{S}}$ remain unchanged; for example, $A'=A$, ${\mathcal{H}}' = {\mathcal{H}}$, etc. It follows from (2.27)–(2.29) that for $1\leq j \leq m({\mathcal{H}})$,

Hence, to prove (2.18), it will suffice to show that for all j,

It is elementary to check that (2.28) implies that $x_k \leq x^{\prime}_k \leq x_{k+1}$. In view of (2.25), for every j, we have either

or

If (2.31) is true then $|x^{\prime}_k-y_j| \geq 1-\delta$, so $C^{\prime}_{k,j}\subset B$, and therefore (2.30) is satisfied. In the case (2.32), the condition (2.30) holds because the right-hand side is 0. We have finished the proof of (2.18).

It follows from (2.27)–(2.29) that (2.26) is satisfied.

Some cells that belong to B can coalesce in the upper left corner in Figure 2, if there are any to start with, but they cannot disappear. The same remark applies to the lower right corner, so the condition (2.20)–(2.21) holds. □

Proof. We apply the transformation defined in Lemma 5 repeatedly, as long as there is some k satisfying (2.25). In view of (2.26), these transformations strictly decrease $m(\mathcal{G})$, so they have to stop at some point, either when $m(\mathcal{G}) =1$ or when (2.25) is not satisfied any more. Then we exchange the roles of $\mathcal{G}$ and ${\mathcal{H}}$ and we collapse pairs of ‘rows’ $H_k$ and $H_{k+1}$ into $H^{\prime}_k$ in a similar manner until the condition analogous to (2.25) fails.

If ${\textbf{S}}'$ is the final result of the transformations described above then ${\textbf{S}}'$ may be represented graphically as follows. The thick polygonal line must turn at every cell corner in the interior of the rectangle (see Figure 4), so that the condition (2.25) is not satisfied, and neither is its analogue with the roles of $\mathcal{G}$ and ${\mathcal{H}}$ exchanged. In other words, the boundary of B in the interior of the rectangle is a zigzag line that turns at every opportunity. It is elementary to check that the conditions (2.33)–(2.40) are a rigorous version of this graphical description.

To see that (2.41) holds, recall that we have weak inequalities in view of (2.12). If any weak inequality in the first set is an equality, say $x^{\prime}_k= x^{\prime}_{k+1}$, then (2.25) is satisfied and we can reduce the number of generators $m'(\mathcal{G}')$ using the transformation defined in Lemma 5. A similar argument applies to the second set of inequalities in (2.41). However, by the argument given in the first part of this proof, $m'(\mathcal{G}')$ and $m'({\mathcal{H}}')$ cannot be decreased any more by the transformation defined in Lemma 5, so (2.41) must be true.

The conditions (2.18)–(2.21) are satisfied because this is the case for the transformation defined in Lemma 5. The alternative stated in (2.42) follows from (2.26). □

The condition (2.43) is illustrated in Figure 2 as follows: in row $H_9$, the rightmost cell in B (within the thick polygonal line) is white; i.e., its probability is 0. The transformation defined in Lemma 7 is illustrated in Figures 2 and 3 (see the caption of Figure 3).

Figure 3: This configuration ${\textbf{S}}'$ has been obtained by transforming the ${\textbf{S}}$ of Figure 2 according to (2.46). For the meanings of the colors and thick lines, see Figure 2. Columns $ G_4$ and $G_5$ in Figure 2 have been combined to form column $G^{\prime}_4$ in the present figure. This is because in row $H_9$ in Figure 2, the rightmost cell in B (within the thick polygonal line) is white, i.e., its probability is 0.

Proof of Lemma 7. Let

Let $\mathcal{G}'$ be the $\sigma$-field generated by $\{G^{\prime}_j\}_{1\leq j \leq m(\mathcal{G})-1}$. All other objects in ${\textbf{S}}$ remain unchanged; for example, $A'=A$, ${\mathcal{H}}' = {\mathcal{H}}$, etc. It follows from (2.45)–(2.47) that for $1\leq j \leq m({\mathcal{H}})$,

Hence, to prove (2.18), it will suffice to show that for all j,

It is elementary to check that (2.46) implies that $x_k \leq x^{\prime}_k \leq x_{k+1}$.

Consider $j\ne i$. It follows from the conditions (2.33)–(2.40) (see the remark about the zigzag line in the proof of Lemma 6) that

In the first case,

This implies that $|x^{\prime}_k-y^{\prime}_j| =|x^{\prime}_k-y_j|\geq 1-\delta$, so $C^{\prime}_{k,j}\subset B'$, and therefore

Hence (2.51) is satisfied.

If ${\operatorname{\mathbb{P}}}(( C_{k,j}\cup C_{k+1,j}) \cap B )=0$, then (2.51) holds because its right-hand side is 0.

In the case when $j=i$, our assumptions (2.43) imply that ${\operatorname{\mathbb{P}}}(C_{k,i}\cap B) = {\operatorname{\mathbb{P}}}(C_{k+1,i}\cap B)=0$, so we conclude that (2.51) is true. This completes the proof of (2.18).

It follows from (2.45)–(2.47) that (2.44) is satisfied.

The condition (2.20)–(2.21) follows from (2.48)–(2.51). □

Proof. Let ${\mathcal{T}}_1$ denote the transformation defined in Lemma 6.

Lemma 7 can be obviously generalized to any situation when $C_{k,i} \subset B$, ${\operatorname{\mathbb{P}}}(C_{k,i})=0$, and $C_{k,i}$ is adjacent to a cell in $B^c$. Fix any order, denoted $\prec$, for the set of pairs of cells. Let ${\mathcal{T}}_2$ denote the transformation defined in Lemma 7, applied to the first pair of cells (according to the order $\prec$) satisfying the generalized conditions described at the beginning of this paragraph. Recall that, by convention, if there is no such pair of cells then ${\mathcal{T}}_2({\textbf{S}}) = {\textbf{S}}$.

Let ${\textbf{S}}_0 = {\textbf{S}}$ and ${\textbf{S}}_k = {\mathcal{T}}_1( {\mathcal{T}}_2({\textbf{S}}_{k-1}))$ for $k\geq 1$. The transformations ${\mathcal{T}}_1$ and ${\mathcal{T}}_2$ decrease $m(\mathcal{G})$ or $m({\mathcal{H}})$, unless they act as the identity transformation, by (2.42) and (2.44). Hence, for some $k_1$ and all $k\geq k_1$, ${\textbf{S}}_k = {\textbf{S}}_{k_1}$. We let ${\textbf{S}}'= {\textbf{S}}_{k_1}$ and note that ${\mathcal{T}}_1({\textbf{S}}') = {\mathcal{T}}_2({\textbf{S}}') = {\textbf{S}}'$. This implies that ${\textbf{S}}'$ must satisfy the properties listed in Lemmas 6 and 7, i.e., (2.33)–(2.41), and the property that there is no cell $C_{k,i} \subset B$ that is adjacent to a cell in $B^c$ and such that ${\operatorname{\mathbb{P}}}(C_{k,i})=0$. A different way of saying this is that ${\operatorname{\mathbb{P}}}(C^{\prime}_{i,j}) >0$ for all $(i,j) \in\mathcal{D}^{\prime}_- \cup\mathcal{D}^{\prime}_+$.

The conditions (2.18)–(2.21) hold for the transformation defined in this proof because they hold for ${\mathcal{T}}_1$ and ${\mathcal{T}}_2$. □

We have used double primes in the statement of the lemma so that ${\textbf{S}}''$ will not be confused with the ${\textbf{S}}'$ constructed in the first step of the proof.

Proof of Lemma 9. The main idea of the proof is to fix $(k,j) \in\mathcal{D}_-\cup \mathcal{D}_+$ and move as much as possible of $A^c$ inside $C_{k,j}$ to A without destroying those properties of ${\textbf{S}}$ that need to be preserved. If this is not possible, a similar transformation is applied to A in place of $A^c$. Then the transformation is repeatedly applied to all $(k,j) \in\mathcal{D}_-\cup \mathcal{D}_+$.

First we apply the transformation defined in Lemma 8, if necessary, so that we can assume that (2.20) and (2.33)–(2.41) are satisfied for ${\textbf{S}}$, and ${\operatorname{\mathbb{P}}}(C_{i,j}) >0$ for all $(i,j) \in\mathcal{D}_- \cup\mathcal{D}_+$.

Step 1. Consider any $(k,j) \in\mathcal{D}_- \cup \mathcal{D}_+$. If

then we let ${\textbf{S}}' ={\textbf{S}}$ and we let ${\mathcal{T}}_3(k,j)$ act as the identity transformation, i.e., ${\mathcal{T}}_3(k,j)({\textbf{S}})={\textbf{S}}$. In this case at least one of the conditions in (2.65) (see below) holds.

Otherwise we proceed as follows. Assume that $(k,j) \in\mathcal{D}_-$ and

Let $\alpha\geq 0$ be the largest real number such that the following three conditions are satisfied:

Here, if $k = m(\mathcal{G})$ then, by convention, $x_{k+1}=\infty$, and similarly, if $j = m({\mathcal{H}})$ then $y_{j+1}=\infty$. At least one of the inequalities (2.55)–(2.57) is an equality.

We make $\mathcal{F}$ finer, if necessary (see Lemma 4), and find an event $A_* \subset C_{k,j}\cap A^c$ such that ${\operatorname{\mathbb{P}}}(A_*) = \alpha$. Then we let $A'= A\cup A_*$. The other elements of ${\textbf{S}}$ remain unchanged. We have assumed that (2.53) does not hold, so

We have

Clearly, the condition (2.19) is satisfied. To prove (2.18) and (2.20)–(2.21), it will suffice to show that for all i and n,

In view of (2.59)–(2.62), (2.63) holds if $n\ne k$ and $i\ne j$.

The conditions (2.41) and (2.35)–(2.37) and the assumption that $(k,j) \in\mathcal{D}_-$ imply that $|x_k - y_i|\geq 1-\delta$ if and only if $i\geq j$. It follows from (2.54), (2.59), and (2.61)–(2.62) that if $i \geq j$, then

This proves (2.63) for $n=k$ and all i.

The conditions (2.41) and (2.35)–(2.37) and the assumption that $(k,j) \in\mathcal{D}_-$ imply that $|x_n - y_j|\geq 1-\delta$ if and only if $n\leq k$. It follows from (2.54), (2.55), (2.59)–(2.60), and (2.61) that if $n\leq k$, then

This completes the proof of (2.63) for $i=j$ and all n. Hence, (2.18) and (2.20)–(2.21) hold true.

Recall that at least one of the inequalities (2.55)–(2.57) is an equality. We list all possible cases below:

1. • If $x^{\prime}_k={\alpha }/{ p_k }+ x_{k} = \delta$ then we must have $y^{\prime}_j=1$ in view of (2.63). This implies that ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap (A')^c) =0$.

2. • If $x^{\prime}_k={\alpha }/{ p_k }+ x_{k} = x_{k+1}<\delta$ then $x^{\prime}_k = x^{\prime}_{k+1}$.

3. • If $y^{\prime}_j={\alpha }/{ q_j } + y_{j} = 1$ then ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap (A')^c) =0$.

4. • If $y^{\prime}_j={\alpha }/{ q_j } + y_{j} =y_{j+1}< 1$ then $y^{\prime}_j = y^{\prime}_{j+1}$.

5. • If $\alpha = {\operatorname{\mathbb{P}}}(C_{k,j}\cap A^c)$ then ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap (A')^c) =0$.

These observations and (2.58) allow us to conclude that $x^{\prime}_k = x^{\prime}_{k+1}$ or $y^{\prime}_j = y^{\prime}_{j+1}$ or ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j})>{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap (A')^c) =0$.

A completely analogous argument shows that if (2.54) does not hold then we can transform ${\textbf{S}}$ into ${\textbf{S}}'$ such that (2.18)–(2.21) are true, and we have the alternatives $x^{\prime}_k = x^{\prime}_{k-1}$ or $y^{\prime}_j = y^{\prime}_{j-1}$ or ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j})>{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap A') =0$.

We next replace the assumption that $(k,j) \in\mathcal{D}_-$ with $(k,j) \in\mathcal{D}_+$. Once again, we can apply the analogous argument to conclude that we can construct ${\textbf{S}}'$ satisfying (2.18)–(2.21) and such that $x^{\prime}_k = x^{\prime}_{k+1}$ or $y^{\prime}_j = y^{\prime}_{j+1}$ or ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j})>{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap (A')^c) =0$ or $x^{\prime}_k = x^{\prime}_{k-1}$ or $y^{\prime}_j = y^{\prime}_{j-1}$ or ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j})>{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap A') =0$.

We see that if $(k,j) \in\mathcal{D}_- \cup \mathcal{D}_+$, then

or

Let ${\mathcal{T}}_3(k,j)$ be the transformation defined in this step.

Step 2. Let $\prec$ denote an arbitrary order for the set of pairs (k, j). Let ${\mathcal{T}}_3$ be defined as ${\mathcal{T}}_3(k,j)$ applied to the first pair (k, j) (in the sense of the order $\prec$) such that (2.53) does not hold.

Let ${\mathcal{T}}_4$ denote the transformation defined in Lemma 6.

Let ${\textbf{S}}_0 = {\textbf{S}}$ and ${\textbf{S}}_k = {\mathcal{T}}_3({\mathcal{T}}_4({\textbf{S}}_{k-1}))$ for $k\geq 1$. The transformation ${\mathcal{T}}_4$ strictly decreases $m(\mathcal{G})$ or $m({\mathcal{H}})$, unless it acts as the identity transformation. Hence, for some $n_1$ and all $k\geq n_1$, ${\textbf{S}}_k = {\mathcal{T}}_3({\textbf{S}}_{k-1})$. This implies that for $k\geq n_1$, ${\textbf{S}}_k$ satisfies (2.41), and this in turn implies that (2.64) cannot be true for ${\textbf{S}}_k$.

Since none of the conditions in (2.64) can hold, one of the conditions in (2.65) must be true for ${\textbf{S}}_k$, $k\geq n_1$. Note that ${\mathcal{T}}_3(k,j)$ does not change $C_{n,i} \cap A$ or $C_{n,i} \cap A^c$ unless $(n,i) = (k,j)$. Hence, for some $n_2 \geq n_1$ and all $k\geq n_2$, ${\textbf{S}}_k = {\mathcal{T}}_3({\textbf{S}}_{n_2})$. We let ${\textbf{S}}''={\textbf{S}}_{n_2}$.

The conditions (2.18)–(2.21) hold for the transformation defined in this proof because they hold for ${\mathcal{T}}_3$ and ${\mathcal{T}}_4$. □

Consider four cells that lie at the corners of a rectangle, i.e., the cells $C_{k_1,j_1}$, $C_{k_2,j_2}$, $C_{k_1,j_2}$, and $ C_{k_2,j_1}$ for some $j_1$, $j_2$, $k_1$, and $k_2$. The transformation defined in the next lemma moves as much as possible of A from the upper left corner to the lower left corner, and compensates by moving the same amount of A from the lower right corner to the upper right corner. The result of the transformation is that one of the four cells will not hold any A.

Proof. We can make $\mathcal{F}$ finer, if necessary (see Lemma 4), so that there exist sets $A_1 \subset A \cap C_{k_1,j_1} $ and $A_2 \subset A \cap C_{k_2,j_2}$ such that ${\operatorname{\mathbb{P}}}(A_1) = {\operatorname{\mathbb{P}}}(A_2) = p$. Let

For all other values of (k, j), we let $C^{\prime}_{k,j} = C_{k,j}$. These transformations redefine the $G_k$, the $H_j$, $\mathcal{G}$, and ${\mathcal{H}}$. The other elements of ${\textbf{S}}$ are unaffected.

It is clear that (2.72)–(2.75) are satisfied and ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}) = {\operatorname{\mathbb{P}}}(C_{k,j})$ for all other values of (k, j).

It is easy to check that $p^{\prime}_k = p_k$, $q^{\prime}_k = q_k$, $x^{\prime}_k = x_k$, and $y^{\prime}_k=y_k$ for all k. Therefore, $C^{\prime}_{k,j} \subset B'$ if and only if $C_{k,j} \subset B$, for every (k, j).

Suppose that (2.68) is true. Then

and

These formulas and the fact that ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}) = {\operatorname{\mathbb{P}}}(C_{k,j})$ for all other values of (k, j) imply that (2.18) holds with equality.

It follows from (2.68) that either $j_1,j_2 \leq m_-({\mathcal{H}})$ or $j_1,j_2 \geq m_+({\mathcal{H}})$. This and (2.76) imply that (2.20)–(2.21) hold.

One can prove that (2.20)–(2.21) hold and (2.18) holds with equality under any of the assumptions (2.67)–(2.71) in a similar manner.

The condition (2.19) obviously holds. □

The transformation defined in the next lemma converts the top right family of cells in Figure 4 into subsets of A. It also converts the bottom left family of cells in Figure 4 into subsets of $A^c$.

Figure 4: (Color coded) For the meanings of the white, red, and blue colors and the thick lines, see the caption of Figure 2. Green has the same meaning as white: it represents ‘empty’ cells, i.e., cells $C_{k,j}$ such that ${\operatorname{\mathbb{P}}}(C_{k,j})=0$. The green cells are the cells that were ‘emptied’ in Step 1 of the proof of Lemma 12. Every crossed cell belongs either to $\mathcal{D}_- $ or to $ \mathcal{D}_+$ and must satisfy ${\operatorname{\mathbb{P}}}(C_{k,j} )>0$ and either ${\operatorname{\mathbb{P}}}(C_{k,j} \cap A) =0$ or ${\operatorname{\mathbb{P}}}(C_{k,j} \cap A^c) =0$. All cells below $\mathcal{D}_-$ are in $A^c$ or empty. All cells above $\mathcal{D}_+$ are in A or empty. All cells to the right of $\mathcal{D}_-$ are in A or empty. All cells to the left of $\mathcal{D}_+$ are in $A^c$ or empty. If a cell is below a cell in $\mathcal{D}_-$ and to the right of a (different) cell in $\mathcal{D}_-$, then it is empty. If a cell is above a cell in $\mathcal{D}_+$ and to the left of a (different) cell in $\mathcal{D}_+$, then it is empty.

Proof. The condition (2.19) clearly holds.

Note that

These observations and (2.13)–(2.16) imply that $B\subset B'$, and therefore (2.18) and (2.20)–(2.21) hold. □

The transformation defined in the next lemma empties all cells in the ‘bottom right corner of the upper left corner’ (marked in green in Figure 4), and similarly on the other side of the diagonal. The result of the transformations described in Lemmas 11–12 is that large regions in Figure 4 do not have cells that would hold both A and $A^c$.

Proof. Step 1. It follows from (2.20) that $ m_-(\mathcal{G})\geq 1$, $ m_+({\mathcal{H}})\leq m({\mathcal{H}})$, $ m_-({\mathcal{H}})\geq 1$, and $ m_+(\mathcal{G})\leq m(\mathcal{G})$. Consider k and j such that $k \leq m_-(\mathcal{G})$, $j\geq m_+({\mathcal{H}}) $, and $C_{k,j} \subset B^c$. Let $C^{\prime}_{k,j} = \emptyset$.

If ${\operatorname{\mathbb{P}}}(A\mid C_{k,j}) < 1-\delta$ then let $ A' = A \setminus C_{k,j}$ and $C^{\prime}_{k,1} = C_{k,1} \cup C_{k,j}$.

If ${\operatorname{\mathbb{P}}}(A\mid C_{k,j}) \geq 1-\delta$ then let $ A' = A \cup C_{k,j}$ and $C^{\prime}_{m(\mathcal{G}),j} = C_{m(\mathcal{G}),j} \cup C_{k,j}$.

These changes will affect $\mathcal{G}$ and ${\mathcal{H}}$. Other elements of ${\textbf{S}}$ will be unchanged.

It is easy to check that $x^{\prime}_k \leq x_k$, $x^{\prime}_{m(\mathcal{G})} \geq x_{m(\mathcal{G})}$, $y^{\prime}_1 \leq y_1$, and $y^{\prime}_j \geq y_j$. All other $x_i$ and $y_i$ will be unaffected. For all i and n such that $C_{i,n}\subset B$, ${\operatorname{\mathbb{P}}}(C^{\prime}_{i,n}) = {\operatorname{\mathbb{P}}}(C_{i,n})$. Hence, in view of (2.13)–(2.16), we see that (2.18)–(2.21) hold. We also have

We repeat the transformation for all k and j such that $k \leq m_-(\mathcal{G})$, $j\geq m_+({\mathcal{H}}) $, and $C_{k,j} \subset B^c$. The result is that $C^{\prime}_{k,j}=\emptyset$ for all such pairs (k, j). Moreover, (2.18)–(2.21) and (2.82)–(2.83) hold.

We apply an analogous sequence of transformations corresponding to all pairs (k, j) such that $k \geq m_+(\mathcal{G})$, $j\leq m_-({\mathcal{H}}) $, and $C_{k,j} \subset B^c$. The result is, once again, that $C^{\prime}_{k,j}=\emptyset$ for all such pairs (k, j). The conditions (2.18)–(2.21) and (2.82)–(2.83) still hold. Note that A and A $^{\prime}$ do not exchange roles in (2.82)–(2.83); i.e., these conditions hold as stated.

We will denote the composition of all transformations defined in this step by ${\mathcal{T}}_5$.

For later reference, we record the following properties of ${\textbf{S}}' = {\mathcal{T}}_5({\textbf{S}})$:

Step 2. Let ${\mathcal{T}}_6$, ${\mathcal{T}}_7$, and ${\mathcal{T}}_8$ denote the transformations defined in Lemmas 11, 9, and 6. Let ${\textbf{S}}_0={\textbf{S}}$ and ${\textbf{S}}_k = {\mathcal{T}}_5({\mathcal{T}}_6({\mathcal{T}}_7({\mathcal{T}}_8({\textbf{S}}_{k-1}))))$ for $k\geq 1$. In view of (2.42) and the fact that ${\mathcal{T}}_5$, ${\mathcal{T}}_6$, and ${\mathcal{T}}_7$ have the property (2.19), ${\mathcal{T}}_8$ must act as the identity eventually; i.e., there must exist $n_1$ such that ${\textbf{S}}_k = {\mathcal{T}}_5({\mathcal{T}}_6({\mathcal{T}}_7({\textbf{S}}_{k-1})))$ for $k\geq n_1$.

The transformations ${\mathcal{T}}_5$ and ${\mathcal{T}}_6$ do not change $m(\mathcal{G})$ and $m({\mathcal{H}})$. They also do not change the values of ${\operatorname{\mathbb{P}}}(C_{k,j})$ and ${\operatorname{\mathbb{P}}}(C_{j,k}\cap A)$ for $(k,j) \in \mathcal{D}_- \cap \mathcal{D}_+$. It follows that ${\mathcal{T}}_7$ must act as the identity eventually; i.e., there must exist $n_2\geq n_1$ such that ${\textbf{S}}_k = {\mathcal{T}}_5({\mathcal{T}}_6({\textbf{S}}_{k-1}))$ for $k\geq n_2$.

It follows from (2.77) and (2.82)–(2.83) that there must exist $n_3\geq n_2$ such that ${\textbf{S}}_k = {\textbf{S}}_{k-1}$ for $k\geq n_3$. Let ${\textbf{S}}'= {\textbf{S}}_{n_3}$. Since ${\mathcal{T}}_i({\textbf{S}}') = {\textbf{S}}'$ for $i=5,6,7,8$, the conditions (2.18)–(2.21), (2.33)–(2.41), (2.52), and (2.78)–(2.81) are satisfied. □

Proof. Suppose that ${\operatorname{\mathbb{P}}}(B)>0$ and $\varepsilon>0$. We apply the transformation defined in Lemma 3 and obtain ${\textbf{S}}'$ satisfying ${\operatorname{\mathbb{P}}}(B') > {\operatorname{\mathbb{P}}}(B) - \varepsilon$, $m'(\mathcal{G}') \leq m(\mathcal{G})+1$, $m'({\mathcal{H}}') \leq m({\mathcal{H}})+1$, and (2.21).

Next we apply the transformation defined in Lemma 12 and obtain ${\textbf{S}}''$ satisfying (2.18), (2.21), (2.33)–(2.41), (2.52), (2.78)–(2.81), $m''(\mathcal{G}'') \leq m(\mathcal{G})+1$, and $m''({\mathcal{H}}'') \leq m({\mathcal{H}})+1$. These properties of ${\textbf{S}}''$ are illustrated in Figure 4.

The logical scheme of the remaining part of the proof is represented by the flowchart in Figure 5.

Figure 5: The logical structure of the proof of Lemma 13.

The leaves of our branching argument will be denoted by ${\circled{X}}$. These are places where logical contradictions are reached so another branch of the proof must be considered.

We will now give names to the transformations that we will apply in this proof.

Let ${\mathcal{T}}_9$ be the transformation defined in Lemma 12.

Recall that ${\tnw}((k_1,j_1),(k_2,j_2))$ denotes the transformation defined in Lemma 10. The transformation ${\tnwc}((k_1,j_1),(k_2,j_2))$ was defined in an analogous way, by replacing A with $A^c$ in the assumption (2.66) and the construction of ${\tnw}((k_1,j_1),(k_2,j_2))$.

Recall that ${\mathcal{T}}_3(k,j)$ is the transformation defined in Step 1 of the proof of Lemma 9. If ${\textbf{S}}' = {\mathcal{T}}_3(k,j)({\textbf{S}})$ then at least one of the conditions (2.64)–(2.65) holds.

The root of the flowchart in Figure 5 is ${\circled{A}}$. Our argument will require that we jump to ${\circled{A}}$ repeatedly. We will argue in the main body of the proof that every jump to ${\circled{A}}$ is associated with the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$. Therefore, there can be only a finite number of jumps to ${\circled{A}}$ from later parts of the proof.

We will repeatedly apply the transformations named above, but instead of using the notation with primes, e.g. $C^{\prime}_{k,j}$, for the resulting objects, we will always write $C_{k,j}$, etc., without primes, to simplify the notation. We hope that this convention will not be confusing in this proof.

Suppose that ${\textbf{S}}$ is given. In view of the initial part of the proof, we can assume that it has all the properties of ${\textbf{S}}''$, i.e., it satisfies (2.18), (2.21), (2.33)–(2.41), (2.52), and (2.78)–(2.81).

${\circled{A}}$ Apply ${\mathcal{T}}_9$ to ${\textbf{S}}$.

If $m_-(\mathcal{G}) \leq 1$ then we jump to ${\circled{B}}$.

${\circled{C}}$ Suppose that $m_-(\mathcal{G}) > 1$. We apply the transformations ${\tnwc}((k,m({\mathcal{H}})), (m_-(\mathcal{G}), j))$ repeatedly for all $k < m_-(\mathcal{G})$ and $j< m_+({\mathcal{H}})$. The resulting ${\textbf{S}}$ satisfies (2.18) because the following case of (2.68)–(2.71) is satisfied for $k < m_-(\mathcal{G})$ and $j< m_+({\mathcal{H}})$:

In later applications of ${\tnw}$ or ${\tnwc}$, we will leave it to the reader to check that one of the conditions (2.67)–(2.71) is satisfied.

In view of (2.84)–(2.85), the result of these transformations has the property that

We apply the transformation ${\mathcal{T}}_3(m_-(\mathcal{G}), m({\mathcal{H}}))$. Note that it changes the ‘A-contents’ of only $C_{m_-(\mathcal{G}), m({\mathcal{H}})}$. The resulting ${\textbf{S}}$ satisfies (2.64) or (2.65) with $(k,j) = (m_-(\mathcal{G}), m({\mathcal{H}}))$.

If ${\textbf{S}}$ satisfies (2.64) then we jump to ${\circled{A}}$. Then an application of ${\mathcal{T}}_9$ will result in the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in view of (2.41) and (2.42).

${\circled{D}}$ Assume that (2.65) holds, i.e., that we have either ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G}),m({\mathcal{H}})}\cap A) =0$ or ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G}),m({\mathcal{H}})}\cap A^c) =0$.

${\circled{E}}$ Assume that (2.87) holds and recall (2.78)–(2.81). These formulas imply that ${\operatorname{\mathbb{P}}}\big(\!\bigcup _{j < m({\mathcal{H}})} C_{m_-(\mathcal{G}), j} \big) = 0$. Since ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G}),m({\mathcal{H}})}) >0$ and either ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G}),m({\mathcal{H}})}\cap A) =0$ or ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G}),m({\mathcal{H}})}\cap A^c) =0$, we must have $x_{m_-(\mathcal{G})} = 0$ or $x_{m_-(\mathcal{G})} = 1$. If $x_{m_-(\mathcal{G})} =0$ then this contradicts the facts that $m_-(\mathcal{G})>1$ and $x_{m_-(\mathcal{G})} > x_1 \geq 0$. We cannot have $x_{m_-(\mathcal{G})} =1$ because that would contradict (2.13). We conclude that (2.87) cannot hold. ${\circled{X}}$

${\circled{F}}$ Assume that (2.86) is true. The transformations which generated (2.86)–(2.87) did not change the $x_i$ and $y_i$, and they also did not change the fact that ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G}),i}\cap A) =0$ for all $i< m({\mathcal{H}})$. We are in the current branch of the proof because we have not jumped to ${\circled{A}}$ after applying ${\mathcal{T}}_3(m_-(\mathcal{G}), m({\mathcal{H}}))$. Hence, $x_{m_-(\mathcal{G})} > x_{m_-(\mathcal{G})-1}$. If ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G}),m({\mathcal{H}})}\cap A) =0$ then $x_{m_-(\mathcal{G})} =0$, but this contradicts the facts that $m_-(\mathcal{G})>1$ and $x_{m_-(\mathcal{G})} > x_1 \geq 0$. Hence, we must have ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G}),m({\mathcal{H}})}\cap A^c) =0$. This, (2.78)–(2.81), and (2.86) imply that

At this point our argument branches as follows. We will consider the case $m_-(\mathcal{G})=2$ in ${\circled{G}}$ and ${\circled{I}}$, the case $m_-(\mathcal{G})=3$ in ${\circled{G}}$ and ${\circled{J}}$, and the case $m_-(\mathcal{G})\geq 4$ in ${\circled{H}}$.

${\circled{G}}$ If $m_-(\mathcal{G})=2$ or $m_-(\mathcal{G})=3$, then we interchange the roles of A and $A^c$ and those of $\mathcal{G}$ and ${\mathcal{H}}$, and argue as follows. We apply the transformations ${\tnw}((k,m_+({\mathcal{H}})), (1, j))$ repeatedly for all $k > m_-(\mathcal{G})$ and $j> m_+({\mathcal{H}})$. Then we apply the transformation ${\mathcal{T}}_3(1, m_+({\mathcal{H}}))$.

If ${\textbf{S}}$ satisfies (2.64) then we jump to ${\circled{A}}$. Then an application of ${\mathcal{T}}_9$ will result in the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in view of (2.41) and (2.42).

Otherwise we will reach the conclusion analogous to (2.88), namely that

We will now argue that the transformations described between (2.88) and (2.89) do not affect the validity of (2.88), assuming that there was no jump to ${\circled{A}}$. The transformations ${\tnw}((k,m_+({\mathcal{H}})), (1, j))$ do not change any of the $x_i$, $y_i$, $p_i$, or $q_i$. The transformation ${\mathcal{T}}_3(1, m_+({\mathcal{H}}))$ does not affect any cells in $H_{m({\mathcal{H}})}$ because $m_+({\mathcal{H}}) < m({\mathcal{H}})$. Hence, (2.88) remains true.

${\circled{I}}$ Suppose that $m_-(\mathcal{G})=2$ and use (2.88)–(2.89) to conclude that ${\operatorname{\mathbb{P}}}(C_{1,m({\mathcal{H}})})=0$. We now jump to ${\circled{B}}$.

${\circled{J}}$ Next assume that $m_-(\mathcal{G})=3$. This case is rather complicated, so it is the only part of the proof whose steps are illustrated one by one in Figures 6–12. We will now explain how different events are represented in these figures. The three columns represent $G_1$, $G_2$, and $G_3$. The three rows represent $H_{m_+({\mathcal{H}})} = H_{m({\mathcal{H}})-2}$, $H_{m({\mathcal{H}})-1}$, and $H_{m({\mathcal{H}})}$. The colors have the same meaning as in Figure 4. Cells containing both white and some other color may be empty or contain either A or $A^c$, depending on the color. The colored areas at the bottom represent the family of cells $C_{k,j}$ (not individual cells) with $1\leq k \leq 3$ and $j < m_+({\mathcal{H}})$, and the colored areas on the right represent the family of cells $C_{k,j}$ with $k> m_-(\mathcal{G})$ and $H_{m_+({\mathcal{H}})} \leq j \leq H_{m({\mathcal{H}})}$.

Figure 6: See the body of the article for the description.

The starting point is illustrated in Figure 6. This ${\textbf{S}}$ satisfies (2.88)–(2.89). We have either

or ${\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A^c) =0$. We will discuss only the case in (2.90), depicted in Figure 6. The other case can be dealt with in an analogous way.

We apply the transformations ${\tnw}((2,m({\mathcal{H}})), (k,m({\mathcal{H}})-1))$ repeatedly for all $k>m_-(\mathcal{G})$. The result of these transformations has the property that

${\circled{J1}}$ If (2.91) holds then ${\operatorname{\mathbb{P}}}(H_{m({\mathcal{H}})-1} \cap A ) =0$ because of (2.78)–(2.81), (2.89), and (2.90). But then $y_{m({\mathcal{H}})-1}=0$. This is impossible because $m({\mathcal{H}})-1 > m_+({\mathcal{H}})$. ${\circled{X}}$

${\circled{J2}}$ Assume that (2.92) is true. We apply ${\mathcal{T}}_3(2,m({\mathcal{H}})-1)$. The resulting ${\textbf{S}}$ satisfies (2.64) or (2.65) with $(k,j) = (2,m({\mathcal{H}})-1)$.

${\circled{J3}}$ If ${\textbf{S}}$ satisfies (2.64) then we jump to ${\circled{A}}$. Then an application of ${\mathcal{T}}_9$ will result in the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in view of (2.41) and (2.42).

${\circled{J4}}$ Assume that (2.65) holds, i.e., either ${\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A) =0$ or ${\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A^c) =0$ (see Figures 7–8).

Figure 7: See the body of the article for the description.

Figure 8: See the body of the article for the description.

${\circled{J5}}$ Assume that ${\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A) =0$ (see Figure 7). This assumption, combined with (2.78)–(2.81) and (2.92), implies that $x_2={\operatorname{\mathbb{P}}}(G_2 \cap A) = 0$. This is impossible because $x_2> x_1 \geq 0$. ${\circled{X}}$

${\circled{J6}}$ Hence, we must have ${\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A^c) =0$ (see Figure 8). We apply the transformations ${\tnwc}((1,m_+({\mathcal{H}})+1), (2,j))$ repeatedly for all $j<m_+({\mathcal{H}})$. The result of these transformations has the property that

We apply the transformation ${\mathcal{T}}_3(2,m({\mathcal{H}})-1)$. The resulting ${\textbf{S}}$ satisfies (2.64) or (2.65) with $(k,j) =(2,m({\mathcal{H}})-1)$.

${\circled{J7}}$ If ${\textbf{S}}$ satisfies (2.64) then we jump to ${\circled{A}}$. Then an application of ${\mathcal{T}}_9$ will result in the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in view of (2.41) and (2.42).

Figure 9: See the body of the article for the description.

Figure 10: See the body of the article for the description.

Figure 11: See the body of the article for the description.

${\circled{J8}}$ Assume that (2.65) holds (see Figures 9–10); that is,

${\circled{J9}}$ Suppose (2.93) holds.

If ${\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A^c) =0$, then ${\operatorname{\mathbb{P}}}(H_{m({\mathcal{H}})-1} \cap A^c ) =0$, because of (2.78)–(2.81) (see Figure 9). Then $y_{m({\mathcal{H}})-1}=1= y_{m({\mathcal{H}})}$ and we jump to ${\circled{A}}$. An application of ${\mathcal{T}}_9$ will result in the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in view of (2.41) and (2.42).

If (2.93) holds and ${\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A) =0$, then ${\operatorname{\mathbb{P}}}(G_2 \cap A ) =0$, because of (2.78)–(2.81) and (2.92) (see Figure 10). Then $x_2=0=x_1$ and we jump to ${\circled{A}}$. An application of ${\mathcal{T}}_9$ will result in the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in view of (2.41) and (2.42).

${\circled{J10}}$ Next suppose that (2.94) holds; see Figures 11–12. In view of (2.84)–(2.85), (2.92), and (2.95), either $x_2 = 1$ or $x_2 =0$. The first case is impossible because $2< m_-(\mathcal{G})$. ${\circled{X}}$

In the second case we have $x_2=0=x_1$ and we jump to ${\circled{A}}$. Then an application of ${\mathcal{T}}_9$ will result in the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in view of (2.41) and (2.42).

${\circled{H}}$ We now assume that $m_-(\mathcal{G})\geq 4$. Recall (2.88). We will analyze $H_{m({\mathcal{H}})-1}\cap B$. We apply the transformations ${\tnwc}((k,m({\mathcal{H}})-1), (m_-(\mathcal{G})-1, j))$ repeatedly for all $k < m_-(\mathcal{G})-1$ and $j< m_+({\mathcal{H}})$. The resulting ${\textbf{S}}$ has the property that

We apply the transformation ${\mathcal{T}}_3(m_-(\mathcal{G})-1, m({\mathcal{H}})-1)$. The resulting ${\textbf{S}}$ satisfies (2.64) or (2.65) with $(k,j) = (m_-(\mathcal{G})-1, m({\mathcal{H}})-1)$.

Figure 12: See the body of the article for the description.

${\circled{H1}}$ If ${\textbf{S}}$ satisfies (2.64) then we jump to ${\circled{A}}$. Then an application of ${\mathcal{T}}_9$ will result in the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in view of (2.41) and (2.42).

${\circled{H2}}$ Assume that (2.65) holds, i.e., either ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G})-1,m({\mathcal{H}})-1}\cap A) =0$ or ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G})-1,m({\mathcal{H}})-1}\cap A^c) =0$.

${\circled{H3}}$ Suppose that

${\circled{H5}}$ Assume that (2.96) holds. The transformations which generated (2.97)–(2.96) did not affect the conditions (2.78)–(2.81). This, (2.84)–(2.85), and (2.96) imply that ${\operatorname{\mathbb{P}}}\big(\!\bigcup _{j < m({\mathcal{H}})-1} C_{m_-(\mathcal{G})-1, j} \big) = 0$. We have ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G})-1,m({\mathcal{H}})}\cap A^c) =0$ because of (2.88). These observations and (2.98) imply that $x_{m_-(\mathcal{G})-1} = 1$. But this contradicts the definition of $m_-(\mathcal{G})$. Hence, (2.96) cannot be true. ${\circled{X}}$

${\circled{H6}}$ Next suppose that (2.97) is true and recall (2.84)–(2.81). We conclude that ${\operatorname{\mathbb{P}}}(A^c \cap H_{m({\mathcal{H}})-1})= 0$. Hence, $y_{m({\mathcal{H}})-1} =1$. We have shown earlier that $y_{m({\mathcal{H}})}=1$, so $y_{m({\mathcal{H}})-1}=y_{m({\mathcal{H}})}$. We jump to ${\circled{A}}$. Then an application of ${\mathcal{T}}_9$ will result in the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in view of (2.41) and (2.42).

${\circled{H4}}$ Suppose that ${\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G})-1,m({\mathcal{H}})-1}\cap A) =0$. Then, in view of (2.88),

Recall that we are assuming here that $m_-(\mathcal{G}) \geq 4$. The argument given between ${\circled{H}}$ and ${\circled{H6}}$ can be applied with the roles of $\mathcal{G}$ and ${\mathcal{H}}$, and those of A and $A^c$, interchanged. Just as in the case of the original argument, some branches will end with ${\circled{X}}$ and some will lead to ${\circled{A}}$. The only branch that will not end this way will generate the following analogue of (2.99):

The argument which led to (2.99) did not affect the cells in (2.100), so, by analogy, the argument used to prove (2.100) does not affect the cells in (2.99). Hence, both (2.99) and (2.100) hold.

For all $(k,j) \in \mathcal{D}_-$ we have ${\operatorname{\mathbb{P}}}(C_{k,j}) >0$ and either ${\operatorname{\mathbb{P}}}(C_{k,j}\cap A^c) =0$ or ${\operatorname{\mathbb{P}}}(C_{k,j}\cap A) =0$. It follows from (2.99) and (2.100) that there exists $(k,j) \in \mathcal{D}_-$ with ${\operatorname{\mathbb{P}}}(C_{k,j}\cap A^c) =0$ and ${\operatorname{\mathbb{P}}}(C_{k+1,j+1}\cap A) =0$. Fix (k, j) with these properties.

We apply the transformations ${\tnwc}((k+1,j+1), (k, j_1))$ repeatedly, for all $((k+1,j+1), (k, j_1))$ such that $j_1\ne j, j+1$. The resulting ${\textbf{S}}$ has the property that

${\circled{H7}}$ If (2.101) holds, then ${\operatorname{\mathbb{P}}}(C_{k+1,j+1}) =0$, because we have assumed that ${\operatorname{\mathbb{P}}}(C_{k+1,j+1}\cap A) =0$. We now apply the transformation defined in Lemma 7 (or one of its variants described at the beginning of the proof of Lemma 8). This transformation decreases $m(\mathcal{G})$ or $m({\mathcal{H}})$. Then we jump to ${\circled{A}}$.

${\circled{H8}}$ If (2.102) holds then we combine it with the assumption that ${\operatorname{\mathbb{P}}}(C_{k,j}\cap A^c) =0$ to obtain

Reversing the roles of $\mathcal{G}$ and ${\mathcal{H}}$, (k, j) and $(k+1,j+1)$, and A and $A^c$, we obtain the following formula analogous to (2.103):

It follows from (2.103), (2.104), $k\leq m_-(\mathcal{G})$, and $j+1\geq m_+({\mathcal{H}})$ that

and

The two inequalities contradict each other since $\delta < 1/2$. ${\circled{X}}$

${\circled{B}}$ We jump here from two points in the proof. We can jump here from ${\circled{A}}$ in the case when $m_-(\mathcal{G}) \leq 1$. We can also jump here from ${\circled{I}}$; in this case we have $m_-(\mathcal{G}) =2$ and ${\operatorname{\mathbb{P}}}(C_{1,m({\mathcal{H}})})=0$. All branches of the proof corresponding to $m_-(\mathcal{G}) >2$ (sub-branches of ${\circled{J}}$ and ${\circled{H}}$) ended with ${\circled{X}}$ or returned to ${\circled{A}}$.

We have pointed out within the proof that every jump to ${\circled{A}}$ was associated with the decrease of $m(\mathcal{G})$ or $m({\mathcal{H}})$, in most cases because of the application of ${\mathcal{T}}_9$. Hence, after a finite number of jumps to ${\circled{A}}$, ${\textbf{S}}$ must have been transformed so that $m_-(\mathcal{G}) \leq 2$.

We can now exchange the roles of $\mathcal{G}$ and ${\mathcal{H}}$ and apply the same argument to cells $C_{k,j}$ with $k\geq m_+(\mathcal{G})$ and $j \leq m_-({\mathcal{H}})$. In this way, we will eliminate the case $m_-({\mathcal{H}}) >2$ and will be left with the case $m_-({\mathcal{H}}) \leq 2$. Moreover, if $m_-({\mathcal{H}}) =2$, we will have ${\operatorname{\mathbb{P}}}(C_{m(\mathcal{G}),1})=0$. Some transformations in the new part of the proof are of the type ${\tnw}$ or ${\tnwc}$; these transformations do not change any of the $x_k$, $y_j$, $p_k$, or $q_j$. Transformations of the type ${\mathcal{T}}_3(\,\cdot\,,\,\cdot\,)$ in the new part of the proof do not affect cells $C_{k,j}$ with $k\leq m_-(\mathcal{G})$ and $j \geq m_+({\mathcal{H}})$. Hence, we have constructed ${\textbf{S}}$ satisfying $m_-(\mathcal{G}) \leq 1$, or $m_-(\mathcal{G}) =2$ and ${\operatorname{\mathbb{P}}}(C_{1,m({\mathcal{H}})})=0$, and also satisfying $m_-({\mathcal{H}}) \leq 1$, or $m_-({\mathcal{H}}) =2$ and ${\operatorname{\mathbb{P}}}(C_{m(\mathcal{G}),1})=0$.

Part (i) of the lemma is satisfied because after the initial application of Lemma 3, at the very beginning of the proof, all other transformations satisfied (2.18). □

Proof of Theorem 1. Recall that $\delta \in (0, 1/2)$ is fixed.

For the proof of the lower bound in (1.3), see Proposition 1.

We turn our attention to the upper bound. In view of Lemma 2, we can assume that $\mathcal{G}$ and ${\mathcal{H}}$ are finitely generated.

Consider any ${\textbf{S}}$. If ${\operatorname{\mathbb{P}}}(B) =0$ then we are done. Assume that ${\operatorname{\mathbb{P}}}(B)>0$ and consider any $\varepsilon>0$. Let ${\textbf{S}}'$ be the result of the transformation defined in Lemma 13. Then ${\operatorname{\mathbb{P}}}(B') \geq {\operatorname{\mathbb{P}}}(B) -\varepsilon$.

Parts (ii) and (iii) of Lemma 13 imply that for each $1\leq k \leq m'(\mathcal{G}')$ there is at most one j such that $C^{\prime}_{k,j}\subset B'$ and ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j})>0$, and, similarly, for each $1 \leq j \leq m'({\mathcal{H}}')$ there is at most one k such that $C^{\prime}_{k,j}\subset B'$ and ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j})>0$. Let ${\mathcal{B}}'$ be the family of all $1\leq k \leq m'(\mathcal{G}')$ such that there is a (unique) j(k) such that $C^{\prime}_{k,j(k)}\subset B'$. Note that $j(k_1) \ne j(k_2)$ if $k_1 \ne k_2$. We apply Lemma 1 as follows:

Since $\varepsilon>0$ is arbitrarily small, ${\operatorname{\mathbb{P}}}(B) \leq 2\delta/(1+\delta)$. □