1. Introduction
Imagine two experts, with access to different information, but sharing the same worldview. We model this by a probability space 
$(\Omega, {\mathcal{F}}, {\operatorname{\mathbb{P}}})$ together with two distinct sub-
$\sigma$-fields 
$\mathcal{G}$ and 
${\mathcal{H}}$ of 
$\mathcal{F}$. The sub-
$\sigma$-fields represent the information accessible to the two experts, while the common probability space represents their worldview, in the sense that, if one of the experts knew exactly what the other knows, he/she would arrive at exactly the same conclusions. This set-up is sometimes called the problem of combining experts’ opinions under partial information, or more colloquially ‘the wisdom of crowds’, and is a popular topic in statistics and decision theory. In general there are N experts with their individual sub-
$\sigma$-fields who are all trying to predict the probability of a common event A (such as the event that a particular candidate will win an election). The usual question is whether there is a coherent way (see Definition 1 below) to combine or aggregate their predictions to come up with a better forecast; see [Reference Dawid, DeGroot and Mortera6, Reference DeGroot8, Reference DeGroot and Mortera9, Reference Genest13]. This field has attracted renewed interest in the current age of social networks (see [Reference French12, Reference Lorenz, Rauhut, Schweitzer and Helbing18]). In practice most aggregation techniques are simply weighted linear combination of the individual forecasts. However, [Reference Ranjan and Gneiting21 and Reference Gneiting and Ranjan14] show that linear aggregations are not coherent; they recommend nonlinear combinations. Building on these earlier works, [Reference Satopää, Pemantle and Ungar22] develops a mathematical framework to combine predictions when experts use ‘partially overlapping information sources’, and [Reference Dawid and Mortera7] uses this framework for the case of 
$N=2$ experts in prediction markets who take turns in updating their beliefs. Also see [Reference Casarin, Mantoan and Ravazzolo4, Reference Kapetanios, Mitchell, Price and Fawcett15, Reference Moral-Benito20] for applications to economics, [Reference Krüger and Nolte17] for applications to banking and finance, [Reference Möller19] for applications to meteorology, [Reference Taylor and Jeon23] for applications to maintenance of wind turbines, and [Reference Burdzy1, Reference Easwaran, Fenton-Glynn, Hitchcock and Velasco11] for philosophical implications. The problem is also related to modeling insider trading in finance [Reference Kchia and Protter16], where the insider has more information than the rest of the traders, i.e., 
$\mathcal{G} \subseteq {\mathcal{H}}$, although the general non-containment scenario makes sense for two different insiders. For recent developments on the pure-mathematics side, related to [Reference Burdzy and Pitman3] and the present article, see [Reference Cichomski5].
We ask a different, complementary question, not about the aggregate of the various predictions, but about their spread. More specifically, we consider 
$N=2$ experts predicting the possibility of a common event A and derive sharp probabilistic bounds on the range of their predictions. In particular, we are interested in when this spread is large, a phenomenon that we call ‘contradictory predictions’. Two people make contradictory predictions if one of them asserts that the probability of A is very small and the other one says that it is very large. We will present a theorem formalizing the idea that the two experts are unlikely to make contradictory predictions even if they have different information sources.
Let us formulate the problem in a quantitative and rigorous manner.
Definition 1. Let A be an event in some probability space 
$(\Omega,{\mathcal{F}}, {\operatorname{\mathbb{P}}})$, so 
$A \in\mathcal{F}$, and let 
$X = {\operatorname{\mathbb{P}}}(A\mid {\mathcal{G}})$ and 
$Y = {\operatorname{\mathbb{P}}}(A\mid {{\mathcal{H}}})$ for two sub-
$\sigma$-fields 
$\mathcal{G}$ and 
${\mathcal{H}}$ of 
$\mathcal{F}$. Random variables X and Y satisfying these conditions are called coherent, and so is their joint distribution. Random variables X and Y are coherent if and only if, for some 
$A \in \mathcal{F}$,
\begin{equation*}0 \le X, Y \le 1 \quad \mbox{ and }\quad X = {\operatorname{\mathbb{P}}}(A \mid X) \quad \mbox{ and }\quad Y = {\operatorname{\mathbb{P}}}(A \mid Y)\end{equation*}
(see [Reference Burdzy and Pitman3, (1.2)]).
Let
\begin{align}\lambda(\delta) = \sup {\operatorname{\mathbb{P}}}(|X-Y| \geq 1-\delta) ,\end{align}
where the supremum is taken over all probability spaces 
$(\Omega,{\mathcal{F}}, {\operatorname{\mathbb{P}}})$, all events 
$A\in \mathcal{F}$, and all sub-
$\sigma$-fields 
$\mathcal{G}$ and 
${\mathcal{H}}$ of 
$\mathcal{F}$. It was proved in Theorem 14.1 of [Reference Burdzy1] that 
$\lambda(\delta)\leq 5 \delta$ for 
$\delta \leq 1/10$. The following stronger result was proved by Jim Pitman and was published in [Reference Burdzy2, Thm. 18.1] with his permission. For all 
$\delta \in (0,1)$,
\begin{align}\frac{2 \delta} {1+\delta} \leq \lambda(\delta)\leq 2 \delta.\end{align}
The purpose of this article is to remove the gap between the lower and upper bounds, even though the gap is very small for small 
$\delta$, i.e., in the most interesting case.
Theorem 1. For all 
$\delta \in (0,1/2)$,
\begin{align}\lambda(\delta) = \frac{2 \delta} {1+\delta} .\end{align}
It has been shown in [Reference Burdzy and Pitman3] that 
$\lambda(\delta)$ is, curiously, discontinuous at 
$\delta=1/2$ (see Figure 1). More precisely, 
$\lambda(\delta) =1$ for 
$\delta\geq 1/2$. To see this, construct X and Y so that 
${\operatorname{\mathbb{P}}}(X=1/2) = 1$ and 
${\operatorname{\mathbb{P}}}(Y=0) = {\operatorname{\mathbb{P}}}(Y=1)=1/2$ (see the discussion around (1.10) in [Reference Burdzy and Pitman3]).
The function 
$\lambda (\delta)$ is discontinuous at 
$\delta=1/2$.
As mentioned above, one can interpret X and Y as the opinions of two experts about the probability of A given different sources of information 
$\mathcal{G}$ and 
${\mathcal{H}}$, assuming the experts agree on some initial assignment of probability 
${\operatorname{\mathbb{P}}}$ to events in 
$\mathcal{F}$. The authors of [Reference Dawid, DeGroot and Mortera6, p. 284] pointed out the following:
If X and Y are both produced by ‘experts’, then one should not expect them to be wildly different. For example, it would seem paradoxical if, with X say uniform on [0, 1], one always had 
$Y = 1 - X$.
This suggests that X and Y cannot be too negatively dependent. However, elementary examples in [Reference Dawid, DeGroot and Mortera6, Section 4.1] show that for any prescribed value of 
${\operatorname{\mathbb{E}}} X = {\operatorname{\mathbb{E}}} Y = {\operatorname{\mathbb{P}}}(A) \in (0,1)$, the correlation between X and Y can take any value in 
$(\!-1,1]$. Consider for instance, for 
$\delta \in (0,1)$, the distribution of (X, Y) concentrated on the three points 
$(1-\delta, 1 - \delta)$, 
$(0, 1-\delta)$, and 
$(1-\delta,0)$, with
\begin{equation}{\operatorname{\mathbb{P}}}(X=Y) = {\operatorname{\mathbb{P}}}(1-\delta,1-\delta) = \frac{ 1 - \delta}{ 1 + \delta } \qquad \mbox{and} \qquad {\operatorname{\mathbb{P}}}(0, 1-\delta)= {\operatorname{\mathbb{P}}}(1-\delta,0) = \frac{ \delta}{ 1 + \delta } .\end{equation}
This example from [Reference Dubins and Pitman10] gives coherent X and Y with correlation 
$\rho(X,Y) = - \delta$ which can be any value in 
$(\!-1,0)$.
We end this section with a proof of (1.2) borrowed from [Reference Burdzy2, Theorem 18.1], because it is simple and it underscores the huge gap in complexity between the proof of the upper bound in (1.2) and our proof of the upper bound in (1.3).
Proposition 1. (J. Pitman.) For all 
$\delta \in (0,1)$,
\begin{align}\frac{2 \delta} {1+\delta} \leq \lambda(\delta)\leq 2 \delta.\end{align}
Proof. We will use notation matching that in the proof of our main theorem.
The lower bound for 
$\lambda(\delta)$ is attained by the example in (1.4) with 
$A=\{X=Y\}$.
For the upper bound, it will suffice to consider the case 
$0 < \delta < 1/2$. Note that for any 
$0 < \delta < 1/2$ and any random variables X and Y with 
$0\leq X \leq 1$ and 
$0\leq Y \leq 1$,
\begin{align}\{|X-Y| \geq 1-\delta\} \subset \{ X\leq \delta, Y \geq 1-\delta\}\cup \{ Y\leq \delta, X \geq 1-\delta\}.\end{align}
Since 
$X = {\operatorname{\mathbb{E}}}({\mathds{1}}_A \mid X)$,
\begin{align*}{\operatorname{\mathbb{P}}}(X\leq \delta, Y \geq 1-\delta, A)\leq {\operatorname{\mathbb{P}}}(X\leq \delta, A) = {\operatorname{\mathbb{E}}}({\mathds{1}}_{\{X\leq \delta\}}X)\leq \delta {\operatorname{\mathbb{P}}}(X\leq \delta).\end{align*}
We have 
$1 - Y = {\operatorname{\mathbb{E}}}({\mathds{1}}_{A^c} \mid Y )$, so
\begin{align*}{\operatorname{\mathbb{P}}}(X\leq \delta, Y \geq 1-\delta, A^c)&\leq {\operatorname{\mathbb{P}}}(Y \geq 1-\delta, A^c) = {\operatorname{\mathbb{E}}}({\mathds{1}}_{\{1-Y\leq \delta\}}(1-Y)) \\[3pt]&\leq \delta {\operatorname{\mathbb{P}}}(Y\geq 1-\delta).\end{align*}
It follows that
\begin{align}{\operatorname{\mathbb{P}}}(X\leq \delta, Y \geq 1-\delta)\leq \delta ( {\operatorname{\mathbb{P}}}(X\leq \delta)+ {\operatorname{\mathbb{P}}}(Y\geq 1- \delta))\end{align}
and similarly
\begin{align}{\operatorname{\mathbb{P}}}(Y\leq \delta, X \geq 1-\delta)\leq \delta ( {\operatorname{\mathbb{P}}}(Y\leq \delta)+ {\operatorname{\mathbb{P}}}(X\geq 1- \delta)).\end{align}
For 
$0 < \delta < 1/2$ the events 
$X \leq \delta$ and 
$X \geq 1- \delta$ are disjoint, so 
${\operatorname{\mathbb{P}}}(X\leq \delta) + {\operatorname{\mathbb{P}}}(X\geq\break 1-\delta) \leq 1$, and the same holds for Y. Add (1.7) and (1.8) and use (1.6) to obtain the upper bound in (1.5). □
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.
Lemma 1. Consider any two events G and H such that 
${\operatorname{\mathbb{P}}}(G)>0$ and 
${\operatorname{\mathbb{P}}}(H)>0$. If
\begin{align*}|{\operatorname{\mathbb{P}}}(A\mid G) - {\operatorname{\mathbb{P}}}(A\mid H)| \geq 1-\delta\end{align*}
then
\begin{align}{\operatorname{\mathbb{P}}}(G\cap H) \leq \frac \delta{1+\delta} ({\operatorname{\mathbb{P}}}(G) + {\operatorname{\mathbb{P}}}(H)).\end{align}
Proof. Assume without loss of generality that
\begin{align*}{\operatorname{\mathbb{P}}}(A\mid G) - {\operatorname{\mathbb{P}}}(A\mid H) \geq 1-\delta.\end{align*}
Suppose that we can prove that
\begin{align}{\operatorname{\mathbb{P}}}( (G\cap H^c) \cup (H\cap G^c)\mid G\cup H) \geq {\operatorname{\mathbb{P}}}(A\mid G) - {\operatorname{\mathbb{P}}}(A\mid H).\end{align}
Then
\begin{align*}\frac{{\operatorname{\mathbb{P}}}( G\cap H)}{{\operatorname{\mathbb{P}}}( G\cup H)}&={\operatorname{\mathbb{P}}}( G\cap H\mid G\cup H) = 1 - {\operatorname{\mathbb{P}}}( (G\cap H^c) \cup (H\cap G^c)\mid G\cup H)\\&\leq 1- ({\operatorname{\mathbb{P}}}(A\mid G) - {\operatorname{\mathbb{P}}}(A\mid H)) \leq \delta,\end{align*}
and, therefore,
\begin{align*}&{\operatorname{\mathbb{P}}}( G\cap H) \leq \delta {\operatorname{\mathbb{P}}}( G\cup H)= \delta ({\operatorname{\mathbb{P}}}(G) + {\operatorname{\mathbb{P}}}(H)) - \delta {\operatorname{\mathbb{P}}}( G\cap H),\\[3pt]&(1+\delta){\operatorname{\mathbb{P}}}( G\cap H) \leq \delta ({\operatorname{\mathbb{P}}}(G) + {\operatorname{\mathbb{P}}}(H)).\end{align*}
This implies (2.1), so it will suffice to prove (2.2).
Let
\begin{alignat*}{3}&p_1 = {\operatorname{\mathbb{P}}}(A \mid G\cap H^c), \qquad&&p_2 = {\operatorname{\mathbb{P}}}(A \mid G\cap H), \qquad&&p_3 = {\operatorname{\mathbb{P}}}(A \mid G^c\cap H), \\[3pt] &q_1 = {\operatorname{\mathbb{P}}}( G\cap H^c), \qquad&&q_2 = {\operatorname{\mathbb{P}}}( G\cap H), \qquad&&q_3 = {\operatorname{\mathbb{P}}}( G^c\cap H).\end{alignat*}
Then
\begin{align}{\operatorname{\mathbb{P}}}(A\mid G) - {\operatorname{\mathbb{P}}}(A\mid H)= \frac{p_1 q_1 + p_2q_2}{q_1+q_2}- \frac{p_2 q_2 + p_3q_3}{q_2+q_3}\leq\frac{ q_1 + p_2q_2}{q_1+q_2}- \frac{p_2 q_2 }{q_2+q_3}.\end{align}
For 
$p_2=0$ we obtain
\begin{align}\frac{ q_1 + p_2q_2}{q_1+q_2}- \frac{p_2 q_2 }{q_2+q_3}=\frac{ q_1 }{q_1+q_2} \leq \frac{q_1+q_3}{q_1+q_2+q_3}= {\operatorname{\mathbb{P}}}( (G\cap H^c) \cup (H\cap G^c)\mid G\cup H).\end{align}
For 
$p_2=1$,
\begin{align}\frac{ q_1 + p_2q_2}{q_1+q_2}- \frac{p_2 q_2 }{q_2+q_3}&=\frac{ q_1+q_2 }{q_1+q_2}- \frac{ q_2 }{q_2+q_3} \leq \frac{q_1+q_3}{q_1+q_2+q_3}\nonumber\\[4pt] &= {\operatorname{\mathbb{P}}}( (G\cap H^c) \cup (H\cap G^c)\mid G\cup H).\end{align}
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]$,
\begin{align*}{\operatorname{\mathbb{P}}}(A\mid G) - {\operatorname{\mathbb{P}}}(A\mid H)\leq\frac{ q_1 + p_2q_2}{q_1+q_2}- \frac{p_2 q_2 }{q_2+q_3}\leq {\operatorname{\mathbb{P}}}( (G\cap H^c) \cup (H\cap G^c)\mid G\cup H).\end{align*}
This completes the proof of (2.2). □
Lemma 2. Recall 
$\lambda(\delta)$ defined in (1.1), and let
\begin{align*}\lambda'(\delta) = \sup {\operatorname{\mathbb{P}}}(|X-Y| \geq 1-\delta) ,\end{align*}
where the supremum is taken over all probability spaces 
$(\Omega,{\mathcal{F}}, {\operatorname{\mathbb{P}}})$, all events 
$A\in \mathcal{F}$, and all finitely generated sub-
$\sigma$-fields 
$\mathcal{G}$ and 
${\mathcal{H}}$ of 
$\mathcal{F}$. If 
$\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. 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
\begin{align*}{\operatorname{\mathbb{P}}}(\{X_n \notin [k/n, (k+1)/n)\} \cap \{k/n \leq X <( k+1)/n\}) = 0,\end{align*}
we have
\begin{align*}{\operatorname{\mathbb{P}}}(|X_n - X| \leq 1/n) =1.\end{align*}
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
\begin{align*}{\operatorname{\mathbb{P}}}(|Y_n - Y| \leq 1/n) =1.\end{align*}
It follows that
\begin{align}{\operatorname{\mathbb{P}}}(|X - Y| \geq 1-\delta ) \leq{\operatorname{\mathbb{P}}}(|X_n - Y_n| \geq 1-\delta-2/n ).\end{align}
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)$. □
Notation 1. In view of Lemma 2 we can and will assume from now on that 
$\mathcal{G}$ and 
${\mathcal{H}}$ are finitely generated. Let 
$\{G_1, G_2, \dots ,G_{m(\mathcal{G})}\}$ be the partition of 
$\Omega$ generating 
$\mathcal{G}$, and let the family 
$\{H_1, H_2, \dots ,H_{m({\mathcal{H}})}\}$ be defined in the analogous way relative to 
${\mathcal{H}}$.
We will assume without loss of generality that 
${\operatorname{\mathbb{P}}}(G_k)>0$ and 
${\operatorname{\mathbb{P}}}(H_k)>0$ for all k.
Let
\begin{align}\hspace*{-40pt}p_k = {\operatorname{\mathbb{P}}}(G_k), \qquad 1\leq k \leq m(\mathcal{G}),\end{align}
\begin{align}\hspace*{-40pt}q_k = {\operatorname{\mathbb{P}}}(H_k), \qquad 1\leq k \leq m({\mathcal{H}}),\end{align}
\begin{align}\hspace*{-90pt}C_{j,k} = G_j \cap H_k, \end{align}
\begin{align}x_k &= X(\omega) \qquad\ {for}\ \omega \in G_k,\ 1\leq k \leq m(\mathcal{G}),\end{align}
\begin{align}y_k &= Y(\omega) \qquad {for}\ \omega \in H_k,\ 1\leq k \leq m({\mathcal{H}}).\end{align}
Events 
$C_{k,j}$ will be called cells. Assume without loss of generality that
\begin{align}x_1\leq x_2\leq \dots \leq x_{m(\mathcal{G})},\qquad y_1\leq y_2\leq \dots\leq y_{m({\mathcal{H}})}.\end{align}
In Figure 2, the values of 
$x_k$ grow from the left to the right, and the values of 
$y_k$ grow from the bottom to the top.
White represents ‘empty’ cells, i.e., cells 
$C_{k,j}$ such that 
${\operatorname{\mathbb{P}}}(C_{k,j})=0$. Red designates ‘cells in 
$A^c$’, i.e., cells 
$C_{k,j}$ such that 
${\operatorname{\mathbb{P}}}(C_{k,j} )>{\operatorname{\mathbb{P}}}(C_{k,j} \cap A) =0$. Blue designates ‘cells in A’, i.e., cells 
$C_{k,j}$ such that 
${\operatorname{\mathbb{P}}}(C_{k,j} )>{\operatorname{\mathbb{P}}}(C_{k,j} \cap A^c) =0$. Rectangles colored both red and blue represent cells 
$C_{k,j}$ that contain both A and 
$A^c$, i.e., 
${\operatorname{\mathbb{P}}}(C_{k,j} \cap A) >0$ and 
${\operatorname{\mathbb{P}}}(C_{k,j} \cap A^c) >0$. The event B is contained within two thick closed polygonal lines. In this illustration, 
$m(\mathcal{G}) = m({\mathcal{H}}) = 13$, 
$m_-(\mathcal{G}) = 6$, 
$m_+(\mathcal{G}) = 9$, 
$m_-({\mathcal{H}}) = 5$, and 
$m_+({\mathcal{H}}) = 8$. Cells have different areas to illustrate the point that their probabilities may be unequal, but no conditions on probability values should be inferred from cell areas.
Let
\begin{align}m_-(\mathcal{G}) & = \max \{k\,{:}\, \exists j\ such\ that\ y_j- x_k \geq 1-\delta\},\end{align}
\begin{align}m_+(\mathcal{G}) & = \min \{k\,{:}\, \exists j\ such\ that\ x_k-y_j \geq 1-\delta\},\end{align}
\begin{align}m_-({\mathcal{H}}) & = \max \{k\,{:}\, \exists j\ such\ that\ x_j- y_k \geq 1- \delta\},\end{align}
\begin{align}m_+({\mathcal{H}}) & = \min \{k\,{:}\, \exists j\ such\ that\ y_k-x_j \geq 1-\delta\}.\end{align}
By convention, 
$\max\!(\emptyset) = 0$ and 
$\min\!(\emptyset) = \infty$. Let
\begin{align}B = \{|X-Y| \geq 1-\delta \}.\end{align}
The definitions (2.13)–(2.16) are illustrated in Figure 2 as follows. The projection of the set B (the cells within two closed thick polygonal lines) onto the horizontal axis consists of the two disjoint intervals 
$[1, m_-(\mathcal{G})]$ and 
$[m_+(\mathcal{G}), m(\mathcal{G})]$. The projection of the set B onto the vertical axis consists of the two disjoint intervals 
$[1, m_-({\mathcal{H}})]$ and 
$[m_+({\mathcal{H}}), m({\mathcal{H}})]$.
We will define a number of transformations of the probability space 
$(\Omega, \mathcal{F}, {\operatorname{\mathbb{P}}})$, event A, and 
$\sigma$-fields 
$\mathcal{G}$ and 
${\mathcal{H}}$. We will denote the transformed objects by 
$(\Omega', \mathcal{F}', {\operatorname{\mathbb{P}}})$, A’, 
$\mathcal{G}'$, and 
${\mathcal{H}}'$. We will also write in a similar manner X’, 
$p_k'$, 
$x_k'$, etc. Note that the only exception to this rule is 
${\operatorname{\mathbb{P}}}$. We will write 
${\operatorname{\mathbb{P}}}$ instead of 
${\operatorname{\mathbb{P}}}'$ (except in Lemma 3) even though the transformed probability measure is not necessarily equal to the original one. This should not cause any confusion. We will denote our transformations by 
${\mathcal{T}}_1$, 
${\mathcal{T}}_2$, etc., and we will write
\begin{align*}{\textbf{S}} &= (\Omega, \mathcal{F}, {\operatorname{\mathbb{P}}},A,\mathcal{G},{\mathcal{H}}),\qquad{\textbf{S}}' = (\Omega', \mathcal{F}', {\operatorname{\mathbb{P}}},A',\mathcal{G}',{\mathcal{H}}'),\qquad{\mathcal{T}}({\textbf{S}}) = {\textbf{S}}'.\end{align*}
All objects that are not listed in the definition of 
${\textbf{S}}$ (for example X, Y, and those in (2.7)–(2.11)) are uniquely defined given 
${\textbf{S}}$.
Our definitions of transformations will contain some assumptions about 
${\textbf{S}}$. If the assumptions are not satisfied, the transformation should be interpreted as the identity, i.e., 
${\mathcal{T}}({\textbf{S}}) \,{=}\, {\textbf{S}}$.
Note that 
${\operatorname{\mathbb{P}}}(B) =\sum_{1\leq j \leq m(\mathcal{G}), 1\leq k \leq m({\mathcal{H}})}{\operatorname{\mathbb{P}}}(C_{j,k}\cap B) $. Most of our transformations will satisfy the following three conditions:
\begin{align}{\operatorname{\mathbb{P}}}(B')=\sum_{1\leq j \leq m'(\mathcal{G}'), 1\leq k \leq m'({\mathcal{H}}')}{\operatorname{\mathbb{P}}}(C^{\prime}_{j,k}\cap B') &\geq\sum_{1\leq j \leq m(\mathcal{G}), 1\leq k \leq m({\mathcal{H}})}{\operatorname{\mathbb{P}}}(C_{j,k}\cap B) ={\operatorname{\mathbb{P}}}(B),\end{align}
\begin{align}m'(\mathcal{G}')\leq m(\mathcal{G}), \qquad &m'({\mathcal{H}}')\leq m({\mathcal{H}}).\end{align}
If
\begin{align}\sum_{1\leq j \leq m_-(\mathcal{G}), 1\leq k \leq m({\mathcal{H}})} {\operatorname{\mathbb{P}}}(C_{j,k}\cap B)>0\ \ and\ \sum_{m_+(\mathcal{G}) \leq j \leq m(\mathcal{G}), 1\leq k \leq m({\mathcal{H}})} {\operatorname{\mathbb{P}}}(C_{j,k}\cap B)>0,\end{align}
then
\begin{align}&\sum_{1\leq j \leq m^{\prime}_-(\mathcal{G}'), 1\leq k \leq m'({\mathcal{H}}')} {\operatorname{\mathbb{P}}}(C^{\prime}_{j,k}\cap B')>0\ and \\[3pt] &\qquad \sum_{m^{\prime}_+(\mathcal{G}') \leq j \leq m'(\mathcal{G}'), 1\leq k \leq m'({\mathcal{H}}')} {\operatorname{\mathbb{P}}}(C^{\prime}_{j,k}\cap B')>0. \notag \end{align}
The meaning of the condition in (2.20)–(2.21) is that if the part of B in the upper left corner in Figure 2 is non-empty and has a strictly positive 
${\operatorname{\mathbb{P}}}$-measure, and the same is true for the part of B in the lower right corner, then the same holds for 
${\textbf{S}}'$.
Lemma 3. Suppose that 
${\textbf{S}}$ is given and 
${\operatorname{\mathbb{P}}}(B) >0$. Then for every 
$\varepsilon>0$ there exists 
${\textbf{S}}'$ such that 
${\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) holds.
Proof. Since 
${\operatorname{\mathbb{P}}}(B)>0$, we must have either 
$ m_-(\mathcal{G}) \geq 1$, 
$ m_+({\mathcal{H}}) \leq m({\mathcal{H}})$, and
\begin{align}\sum_{1\leq j \leq m_-(\mathcal{G}), 1\leq k \leq m({\mathcal{H}})} {\operatorname{\mathbb{P}}}(C_{j,k}\cap B)>0,\end{align}
or 
$ m_-({\mathcal{H}}) \geq 1$, 
$m_+(\mathcal{G}) \leq m(\mathcal{G})$, and
\begin{align}\sum_{m_+(\mathcal{G}) \leq j \leq m(\mathcal{G}), 1\leq k \leq m({\mathcal{H}})} {\operatorname{\mathbb{P}}}(C_{j,k}\cap B)>0.\end{align}
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
\begin{align*}\Omega' = \Omega \cup \{\omega^{\prime}_{k,0}: 1\leq k \leq m(\mathcal{G}) +1\}\cup \{\omega^{\prime}_{m(\mathcal{G})+1,j}: 1\leq j \leq m({\mathcal{H}}) \},\end{align*}
where the 
$\omega^{\prime}_{k,j}$ are all distinct and do not belong to 
$\Omega$. Let
\begin{align*}C^{\prime}_{k,j} &= C_{k,j}, \qquad 1\leq k \leq m(\mathcal{G}), 1\leq j \leq m({\mathcal{H}}),\\[2pt]C^{\prime}_{k,0} &= \{\omega^{\prime}_{k,0} \}, \qquad 1\leq k \leq m(\mathcal{G}) +1,\\[2pt] C^{\prime}_{m(\mathcal{G})+1,j}& = \{\omega^{\prime}_{m(\mathcal{G})+1,j}\}, \qquad 1\leq j \leq m({\mathcal{H}}) ,\\[2pt] G^{\prime}_k &= \bigcup_{ 0\leq j \leq m({\mathcal{H}})} C^{\prime}_{k,j}, \qquad 1\leq k \leq m(\mathcal{G}) +1,\\[2pt] H^{\prime}_j &= \bigcup_{ 1\leq k \leq m(\mathcal{G})+1} C^{\prime}_{k,j}, \qquad 0\leq j \leq m({\mathcal{H}}) ,\\[2pt] \mathcal{G}' &= \sigma\{G^{\prime}_k, 1\leq k \leq m(\mathcal{G}) +1\},\\[2pt] {\mathcal{H}}'&= \sigma\{H^{\prime}_j, 0\leq j \leq m({\mathcal{H}})\},\\[2pt] A' &= A \cup G^{\prime}_{m(\mathcal{G})+1} .\end{align*}
Fix any 
$\varepsilon>0$. Let 
$\varepsilon_1>0$ be so small that
\begin{align}{\operatorname{\mathbb{P}}}(B) (1- \varepsilon_1/2 - \varepsilon_1 /4)> {\operatorname{\mathbb{P}}}(B) -\varepsilon.\end{align}
It is elementary to see that we can define a probability measure 
${\operatorname{\mathbb{P}}}'$ on 
$\Omega'$ with the following properties:
\begin{align*}{\operatorname{\mathbb{P}}}'\left(H^{\prime}_0 \setminus C^{\prime}_{m(\mathcal{G})+1, 0}\right) &= \varepsilon_1/2,\\ \\[-8pt]{\operatorname{\mathbb{P}}}'\left( C^{\prime}_{m(\mathcal{G})+1, 0}\right)& >0,\\ \\[-8pt] {\operatorname{\mathbb{P}}}'\left( G^{\prime}_{m(\mathcal{G})+1} \right) & = \varepsilon_1\delta/4,\\ \\[-8pt] {\operatorname{\mathbb{P}}}'(F) &= (1- \varepsilon_1/2 - \varepsilon_1 \delta /4) {\operatorname{\mathbb{P}}}(F), \qquad F\subset \Omega.\end{align*}
Note that 
$x_{m(\mathcal{G})+1} = 1$ and
\begin{align*}y_0 = \frac{{\operatorname{\mathbb{P}}}(A'\cap H^{\prime}_0)}{{\operatorname{\mathbb{P}}}( H^{\prime}_0)}\leq \frac{{\operatorname{\mathbb{P}}}\left(C^{\prime}_{m(\mathcal{G})+1, 0}\right)}{{\operatorname{\mathbb{P}}}\left(H^{\prime}_0 \setminus C^{\prime}_{m(\mathcal{G})+1, 0}\right)}\leq \frac{{\operatorname{\mathbb{P}}}\left(G^{\prime}_{m(\mathcal{G})+1}\right)}{{\operatorname{\mathbb{P}}}\left(H^{\prime}_0 \setminus C^{\prime}_{m(\mathcal{G})+1, 0}\right)}= \frac{\varepsilon_1 \delta /4}{\varepsilon_1/2}= \delta/2.\end{align*}
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),
\begin{align*}{\operatorname{\mathbb{P}}}'(B') \geq {\operatorname{\mathbb{P}}}'(B) = {\operatorname{\mathbb{P}}}(B) (1- \varepsilon_1/2 - \varepsilon_1 \delta /4)> {\operatorname{\mathbb{P}}}(B) -\varepsilon.\\[-35pt]\end{align*}
□
Lemma 4. Suppose that for some 
${\textbf{S}}$, 
$j_1$, and 
$k_1$, we have 
${\operatorname{\mathbb{P}}}(C_{j_1,k_1}\cap A) = p_1>0$, and consider any 
$p_2 \in (0, p_1)$. There exists 
${\textbf{S}}'$ such that 
$m'(\mathcal{G}')=m(\mathcal{G})$, 
$m'({\mathcal{H}}')=m({\mathcal{H}})$,
\begin{align*}{\operatorname{\mathbb{P}}}(C^{\prime}_{j,k}\cap A') &= {\operatorname{\mathbb{P}}}(C_{j,k}\cap A), \qquad{\operatorname{\mathbb{P}}}(C^{\prime}_{j,k}\cap (A')^c) = {\operatorname{\mathbb{P}}}(C_{j,k}\cap A^c),\end{align*}
for all 
$1\leq j \leq m(\mathcal{G}) $ and 
$ 1\leq k \leq m({\mathcal{H}})$, and there exists an event 
$F\subset C^{\prime}_{j_1,k_1}\cap A'$ with 
${\operatorname{\mathbb{P}}}(F) = p_2$. Moreover, the conditions (2.18)–(2.21) are satisfied.
Proof. Let 
$\Omega'$ be defined as follows:
\begin{align*}\Omega'= \{\omega^{\prime}_{j,k,1}\}_{1\leq j \leq m(\mathcal{G}), 1\leq k \leq m({\mathcal{H}})}\cup\{\omega^{\prime}_{j,k,2}\}_{1\leq j \leq m(\mathcal{G}), 1\leq k \leq m({\mathcal{H}})} \cup\{\omega^{\prime}_{j_1,k_1,3}\},\end{align*}
where all listed elements are distinct. Let
\begin{align*}C^{\prime}_{j,k}\cap A' &= \{\omega^{\prime}_{j,k,1}\},\qquad C^{\prime}_{j,k}\cap (A')^c = \{\omega^{\prime}_{j,k,2}\},\end{align*}
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
\begin{align*}{\operatorname{\mathbb{P}}}(C^{\prime}_{j,k}\cap A') &= {\operatorname{\mathbb{P}}}(C_{j,k}\cap A), \qquad{\operatorname{\mathbb{P}}}(C^{\prime}_{j,k}\cap (A')^c) = {\operatorname{\mathbb{P}}}(C_{j,k}\cap A^c),\end{align*}
for all 
$1\leq j \leq m(\mathcal{G}) $ and 
$ 1\leq k \leq m({\mathcal{H}})$, and
\begin{align*}{\operatorname{\mathbb{P}}}(F) = {\operatorname{\mathbb{P}}}(\{\omega^{\prime}_{j_1,k_1,1}\})=p_2,\qquad{\operatorname{\mathbb{P}}}(\{\omega^{\prime}_{j_1,k_1,3}\})=p_1-p_2.\end{align*}
It is elementary to check that 
${\textbf{S}}'$ satisfies the lemma. □
Lemma 5. Suppose that there exists 
$k\in\{1,\dots, m(\mathcal{G})-1\}$ such that for every 
$j\in\{1,\dots, m({\mathcal{H}})\}$ we have
\begin{align} C_{k,j}\cup C_{k+1,j} \subset B \quad \text{ or }\quad {\operatorname{\mathbb{P}}}(( C_{k,j}\cup C_{k+1,j}) \cap B )=0.\end{align}
Then there exists 
${\textbf{S}}'$ such that (2.18) and (2.20)–(2.21) are satisfied, and
\begin{align}m'(\mathcal{G}')= m(\mathcal{G})-1, \qquad &m'({\mathcal{H}}')\leq m({\mathcal{H}}).\end{align}
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
\begin{align}\hspace*{-55pt}G^{\prime}_j = G_j, \quad 1\leq j
< k,\end{align}
\begin{align}\hspace*{-73pt}G^{\prime}_k = G_k \cup G_{k+1}, \end{align}
\begin{align}G^{\prime}_j = G_{j+1}, \quad k+1 \leq j \leq m(\mathcal{G})-1.\end{align}
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}})$,
\begin{align*}C^{\prime}_{r,j} &= C_{r,j}, \quad 1\leq r
< k,\notag\\[3pt] C^{\prime}_{k,j} &= C_{k,j} \cup C_{k+1,j},\\[3pt] C^{\prime}_{r,j} &= C_{r+1,j}, \quad k+1 \leq r \leq m(\mathcal{G})-1.\notag\end{align*}
Hence, to prove (2.18), it will suffice to show that for all j,
\begin{align}{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap B)\geq{\operatorname{\mathbb{P}}}(C_{k,j}\cap B) + {\operatorname{\mathbb{P}}}(C_{k+1,j}\cap B).\end{align}
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
\begin{align}|x_k-y_j| \geq 1-\delta \quad\text{ and }\quad|x_{k+1}-y_j| \geq 1-\delta\end{align}
or
\begin{align}|x_k-y_j| < 1-\delta \quad\text{ and }\quad|x_{k+1}-y_j|
< 1-\delta .\end{align}
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. □
Lemma 6. For any 
${\textbf{S}}$ there exists 
${\textbf{S}}'$ such that (2.18)–(2.21) are satisfied and
\begin{align}m^{\prime}_-(\mathcal{G}') &= m'({\mathcal{H}}')- m^{\prime}_+({\mathcal{H}}')+1, \end{align}
\begin{align} m^{\prime}_-({\mathcal{H}}') &= m'(\mathcal{G}') -m^{\prime}_+(\mathcal{G}')+1,\end{align}
\begin{align}y^{\prime}_{m'({\mathcal{H}}') - k+1} - x^{\prime}_k &\geq 1-\delta, \qquad 1\leq k \leq m^{\prime}_-(\mathcal{G}'), \end{align}
\begin{align}y^{\prime}_{m'({\mathcal{H}}') - k+1} - x^{\prime}_{k+1} &
< 1-\delta, \qquad 1\leq k \leq m^{\prime}_-(\mathcal{G}'), \end{align}
\begin{align}y^{\prime}_{m'({\mathcal{H}}') - k} - x^{\prime}_k &
< 1-\delta, \qquad 1\leq k \leq m^{\prime}_-(\mathcal{G}'), \end{align}
\begin{align}x^{\prime}_{m'(\mathcal{G}') - k+1} - y^{\prime}_k &\geq 1-\delta, \qquad 1\leq k \leq m^{\prime}_-({\mathcal{H}}'), \end{align}
\begin{align}x^{\prime}_{m'(\mathcal{G}') - k+1} - y^{\prime}_{k+1} &
< 1-\delta, \qquad 1\leq k \leq m^{\prime}_-({\mathcal{H}}'), \end{align}
\begin{align}x^{\prime}_{m'(\mathcal{G}') - k} - y^{\prime}_k &
< 1-\delta, \qquad 1\leq k \leq m^{\prime}_-({\mathcal{H}}'), \end{align}
\begin{align}x^{\prime}_1 < x^{\prime}_2 < \dots < x^{\prime}_{m(\mathcal{G}')}, & \quad \text{ and }\quad y^{\prime}_1 < y^{\prime}_2 < \dots
< y^{\prime}_{m({\mathcal{H}}')}.\end{align}
Moreover,
\begin{align}{\textbf{S}}' = {\textbf{S}} \qquad \text{or} \qquad m'(\mathcal{G}')< m(\mathcal{G})\qquad \text{or} \qquad &m'({\mathcal{H}}')
< m({\mathcal{H}}).\end{align}
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). □
Notation 2. If 
$(k,j) = (k, m({\mathcal{H}}) - k+1)$ and the conditions (2.35)–(2.37), without primes, are satisfied, then we will write 
$(k,j) \in\mathcal{D}_-$. If 
$(j,k) = ( m(\mathcal{G}) - k+1,k)$ and the conditions (2.38)–(2.40), without primes, are satisfied, then we will write 
$(j,k) \in\mathcal{D}_+$. In Figure 4, the cells belonging to 
$\mathcal{D}_-$ and 
$\mathcal{D}_+$ are crossed. The set 
$\mathcal{D}_-\cup \mathcal{D}_+$ is the ‘internal border’ of B. Note that if 
$(k,j) \in\mathcal{D}_-$ then 
$x_k \leq \delta$ and 
$y_j \geq 1-\delta$. If 
$(k,j) \in\mathcal{D}_+$ then 
$x_k \geq 1-\delta$ and 
$y_j \leq \delta$.
Lemma 7. Suppose that 
${\textbf{S}} $ satisfies (2.33)–(2.41) and there exist 
$k\in\{1,\dots, m(\mathcal{G})-1\}$ and 
$i\in\{1,\dots, m({\mathcal{H}})\}$ such that
\begin{align} &C_{k,i} \subset B , \quad C_{k+1,i} \subset B^c, \quad{\operatorname{\mathbb{P}}}(C_{k,i})=0 .\end{align}
Then there exists 
${\textbf{S}}'$ such that (2.18) and (2.20)–(2.21) are satisfied, and
\begin{align}m'(\mathcal{G}')= m(\mathcal{G})-1, \qquad &m'({\mathcal{H}}')\leq m({\mathcal{H}}).\end{align}
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).
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
\begin{equation}\hspace*{-63pt}G^{\prime}_j = G_j, \quad 1\leq j
< k,\end{equation}
\begin{equation}\hspace*{-80pt}G^{\prime}_k = G_k \cup G_{k+1}, \end{equation}
\begin{align}\hspace*{-6pt}G^{\prime}_j & = G_{j+1}, \quad k+1 \leq j \leq m(\mathcal{G})-1.\end{align}
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}})$,
\begin{align}\hspace*{-60pt}C^{\prime}_{r,j} = C_{r,j}, \quad 1\leq r
< k,\end{align}
\begin{align}\hspace*{-75pt}C^{\prime}_{k,j} = C_{k,j} \cup C_{k+1,j},\end{align}
\begin{align}C^{\prime}_{r,j} = C_{r+1,j}, \quad k+1 \leq r \leq m(\mathcal{G})-1.\end{align}
Hence, to prove (2.18), it will suffice to show that for all j,
\begin{align}{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap B')\geq{\operatorname{\mathbb{P}}}(C_{k,j}\cap B) + {\operatorname{\mathbb{P}}}(C_{k+1,j}\cap B).\end{align}
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
\begin{align*} C_{k,j}\cup C_{k+1,j} \subset B \quad \text{ or }\quad {\operatorname{\mathbb{P}}}(( C_{k,j}\cup C_{k+1,j}) \cap B )=0.\end{align*}
In the first case,
\begin{align*}|x_k-y_j| \geq 1-\delta \quad\text{ and }\quad|x_{k+1}-y_j| \geq 1-\delta .\end{align*}
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
\begin{align*}{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap B')={\operatorname{\mathbb{P}}}(C^{\prime}_{k,j})= {\operatorname{\mathbb{P}}}(C_{k,j}) + {\operatorname{\mathbb{P}}}(C_{k+1,j})\geq{\operatorname{\mathbb{P}}}(C_{k,j}\cap B) + {\operatorname{\mathbb{P}}}(C_{k+1,j}\cap B).\end{align*}
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). □
Lemma 8. For any 
${\textbf{S}}$ there exists 
${\textbf{S}}'$ such that (2.18)–(2.21) and (2.33)–(2.41) are satisfied, and 
${\operatorname{\mathbb{P}}}(C^{\prime}_{i,j}) >0$ for all 
$(i,j) \in\mathcal{D}^{\prime}_- \cup\mathcal{D}^{\prime}_+$.
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$. □
Lemma 9. Suppose that 
${\textbf{S}}$ satisfies the conditions (2.33)–(2.41). There exists 
${\textbf{S}}''$ such that (2.18)–(2.21) and (2.33)–(2.41) hold, and
\begin{align}{\operatorname{\mathbb{P}}}(C'^{\prime}_{k,j}) >{\operatorname{\mathbb{P}}}(C'^{\prime}_{k,j}\cap (A'')^c) =0 \quad\ {or}\ \quad{\operatorname{\mathbb{P}}}(C'^{\prime}_{k,j}) > {\operatorname{\mathbb{P}}}(C'^{\prime}_{k,j}\cap A'') =0,\end{align}
for all 
$(k,j) \in\mathcal{D}'^{\prime}_- \cup \mathcal{D}'^{\prime}_+$.
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
\begin{align}{\operatorname{\mathbb{P}}}(C_{k,j}\cap (A)^c) =0 \quad \text{ or }\quad {\operatorname{\mathbb{P}}}(C_{k,j}\cap A) =0,\end{align}
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
\begin{align}p_{k} \geq q_{j}.\end{align}
Let 
$\alpha\geq 0$ be the largest real number such that the following three conditions are satisfied:
\begin{align}\hspace*{-40pt}\frac{\alpha }{ p_k }+ x_{k} \leq x_{k+1}\land \delta,\end{align}
\begin{align}\hspace*{-40pt}\frac{\alpha }{ q_j } + y_{j} \leq y_{j+1} \land 1,\end{align}
\begin{align}\alpha & \leq {\operatorname{\mathbb{P}}}(C_{k,j}\cap A^c).\end{align}
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
\begin{align}{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}) \geq {\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap A')\geq {\operatorname{\mathbb{P}}}(C_{k,j}\cap A)>0.\end{align}
We have
\begin{align}\hspace*{-38pt}x_{k}' = \frac{\alpha }{ p_k }+ x_{k},\end{align}
\begin{align}x^{\prime}_i = x_i, \qquad \text{ for } i\ne k,\end{align}
\begin{align}\hspace*{-38pt}y^{\prime}_{j} = \frac{\alpha }{ q_j } + y_{j},\end{align}
\begin{align}y^{\prime}_i &= y_i,\qquad \text{ for } i\ne j.\end{align}
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,
\begin{align}\text{ if } \quad |x_n - y_i|\geq 1-\delta \quad\text{ then } \quad |x^{\prime}_n - y^{\prime}_i|\geq 1-\delta .\end{align}
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
\begin{align*}y^{\prime}_{i} - x^{\prime}_k \geq y^{\prime}_{j} - x^{\prime}_k=\frac{\alpha }{ q_j } + y_{j}- \frac{\alpha }{ p_k }- x_{k}\geq y_{j}- x_{k}\geq 1-\delta.\end{align*}
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
\begin{align*}y^{\prime}_{j} - x^{\prime}_n \geq y^{\prime}_{j} - x^{\prime}_k=\frac{\alpha }{ q_j } + y_{j}- \frac{\alpha }{ p_k } - x_{k}\geq y_{j}- x_{k}\geq 1-\delta.\end{align*}
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:
• 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$.• If
$x^{\prime}_k={\alpha }/{ p_k }+ x_{k} = x_{k+1}<\delta$ then $x^{\prime}_k = x^{\prime}_{k+1}$.• If
$y^{\prime}_j={\alpha }/{ q_j } + y_{j} = 1$ then ${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap (A')^c) =0$.• If
$y^{\prime}_j={\alpha }/{ q_j } + y_{j} =y_{j+1}< 1$ then $y^{\prime}_j = y^{\prime}_{j+1}$.• 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
\begin{align}x^{\prime}_k = x^{\prime}_{k+1} \quad \text{ or }\quad y^{\prime}_j = y^{\prime}_{j+1} \quad \text{ or }\quad x^{\prime}_k = x^{\prime}_{k-1} \quad \text{ or }\quad y^{\prime}_j = y^{\prime}_{j-1},\end{align}
or
\begin{align}{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j})>{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap (A')^c) =0 \quad \text{ or }\quad {\operatorname{\mathbb{P}}}(C^{\prime}_{k,j})>{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}\cap A') =0.\end{align}
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.
Lemma 10. Suppose that for some 
${\textbf{S}}$, 
$1\leq k_1 < k_2 \leq m(\mathcal{G})$, and 
$1 \leq j_2 < j_1 \leq m({\mathcal{H}})$, we have
\begin{align}&p \coloneqq \min({\operatorname{\mathbb{P}}}(A \cap C_{k_1,j_1} ) , {\operatorname{\mathbb{P}}}(A \cap C_{k_2,j_2} )) >0.\end{align}
Assume that
\begin{align}C_{k_1,j_1} \cup C_{k_2,j_2} &\cup C_{k_1,j_2} \cup C_{k_2,j_1}\subset B, \quad\ {or}\end{align}
\begin{align}C_{k_1,j_1} \cup C_{k_1,j_2}\subset B \quad & {and} \quad C_{k_2,j_1} \cup C_{k_2,j_2}\subset B^c, \quad\ or\end{align}
\begin{align}C_{k_1,j_1} \cup C_{k_1,j_2}\subset B^c \quad & and\ \quad C_{k_2,j_1} \cup C_{k_2,j_2}\subset B, \quad\ or\ \end{align}
\begin{align}C_{k_1,j_1} \cup C_{k_2,j_1}\subset B \quad & \ and\ \quad C_{k_1,j_2} \cup C_{k_2,j_2}\subset B^c, \quad\ or\ \end{align}
\begin{align}C_{k_1,j_1} \cup C_{k_2,j_1}\subset B^c \quad & and\ \quad C_{k_1,j_2} \cup C_{k_2,j_2}\subset B.\end{align}
Then there exists 
${\textbf{S}}'$ such that 
$m'(\mathcal{G}') = m(\mathcal{G})$, 
$m'({\mathcal{H}}') = m({\mathcal{H}})$,
\begin{align}{\operatorname{\mathbb{P}}}(C^{\prime}_{k_1,j_1})&= {\operatorname{\mathbb{P}}}(C_{k_1,j_1}) -p,\end{align}
\begin{align}{\operatorname{\mathbb{P}}}(C^{\prime}_{k_2,j_2})&= {\operatorname{\mathbb{P}}}(C_{k_2,j_2}) -p,\end{align}
\begin{align}{\operatorname{\mathbb{P}}}(C^{\prime}_{k_1,j_2})&= {\operatorname{\mathbb{P}}}(C_{k_1,j_2}) +p,\end{align}
\begin{align}{\operatorname{\mathbb{P}}}(C^{\prime}_{k_2,j_1})&= {\operatorname{\mathbb{P}}}(C_{k_2,j_1}) +p,\end{align}
and 
${\operatorname{\mathbb{P}}}(C^{\prime}_{k,j}) = {\operatorname{\mathbb{P}}}(C_{k,j})$ for all other values of (k, j).
Moreover, (2.20)–(2.21) hold. The condition (2.18) holds with equality.
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
\begin{align*}C^{\prime}_{k_1,j_1}&= C_{k_1,j_1} \setminus A_1,\qquad C^{\prime}_{k_2,j_2}= C_{k_2,j_2} \setminus A_2,\\[3pt]C^{\prime}_{k_1,j_2}&= C_{k_1,j_2} \cup A_1,\qquad C^{\prime}_{k_2,j_1}= C_{k_2,j_1} \cup A_2.\end{align*}
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
\begin{align}&{\operatorname{\mathbb{P}}}(C^{\prime}_{k_1,j_1} \cap B') +{\operatorname{\mathbb{P}}}( C^{\prime}_{k_1,j_2} \cap B')\notag\\[3pt]&\quad= {\operatorname{\mathbb{P}}}(C^{\prime}_{k_1,j_1} ) +{\operatorname{\mathbb{P}}}( C^{\prime}_{k_1,j_2} )= {\operatorname{\mathbb{P}}}(C_{k_1,j_1} )-p +{\operatorname{\mathbb{P}}}( C_{k_1,j_2} )+p \notag \\[3pt]&\quad= {\operatorname{\mathbb{P}}}(C_{k_1,j_1} ) +{\operatorname{\mathbb{P}}}( C_{k_1,j_2} )={\operatorname{\mathbb{P}}}(C_{k_1,j_1} \cap B) +{\operatorname{\mathbb{P}}}( C_{k_1,j_2} \cap B),\end{align}
and
\begin{align*}{\operatorname{\mathbb{P}}}(C^{\prime}_{k_2,j_1} \cap B') +{\operatorname{\mathbb{P}}}( C^{\prime}_{k_2,j_2} \cap B')&= 0={\operatorname{\mathbb{P}}}(C_{k_2,j_1} \cap B) +{\operatorname{\mathbb{P}}}( C_{k_2,j_2} \cap B).\end{align*}
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. □
Notation 3. We will use 
${\tnw}((k_1,j_1),(k_2,j_2))$ to denote the transformation defined in Lemma 10. We define a transformation 
${\tnwc}((k_1,j_1),(k_2,j_2))$ by replacing A with 
$A^c$ in the assumption (2.66) and the construction of 
${\tnw}((k_1,j_1),(k_2,j_2))$.
If the assumptions of Lemma 10 do not hold then 
${\tnw}((k_1,j_1),(k_2,j_2))$ will denote the identity transformation, and similarly for 
${\tnwc}((k_1,j_1),(k_2,j_2))$.
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$.
(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.
Lemma 11. Given 
${\textbf{S}}$, let
\begin{align}A' &=\left( A\cup\bigcup_{m_-(\mathcal{G}) < k \leq m(\mathcal{G}),m_-({\mathcal{H}}) < j \leq m({\mathcal{H}})} C_{k,j} \right)\Bigg\backslash\left(\!\bigcup_{1 \leq k < m_+(\mathcal{G}),1 \leq j
< m_+({\mathcal{H}})} C_{k,j}\right).\end{align}
Let all other elements of 
${\textbf{S}}'$ be the same as those of 
${\textbf{S}}$. Then the conditions (2.18)–(2.21) hold.
Proof. The condition (2.19) clearly holds.
Note that
\begin{align*}x^{\prime}_k & \leq x_k, \quad \text{ for } 1 \leq k \leq m_-(\mathcal{G}),\\[3pt]y^{\prime}_k & \leq y_k, \quad \text{ for } 1 \leq k \leq m_-({\mathcal{H}}),\\[3pt]x^{\prime}_k & \geq x_k, \quad \text{ for } m_+(\mathcal{G}) \leq k \leq m(\mathcal{G}),\\[3pt]y^{\prime}_k & \geq y_k, \quad \text{ for } m_+({\mathcal{H}}) \leq k \leq m({\mathcal{H}}).\end{align*}
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$.
Lemma 12. Consider an 
${\textbf{S}}$ such that (2.20) holds. Then there exists 
${\textbf{S}}'$ such that the conditions (2.18)–(2.21), (2.33)–(2.41), and (2.52) hold, and
\begin{align}{\operatorname{\mathbb{P}}}((G^{\prime}_k \setminus B') \cap A') &=0 \quad\ {for}\ \quad 1\leq k \leq m_-(\mathcal{G}'),\end{align}
\begin{align}{\operatorname{\mathbb{P}}}((H^{\prime}_k \setminus B') \cap A') &=0 \quad\ for\ \quad 1\leq k \leq m_-({\mathcal{H}}'),\end{align}
\begin{align}{\operatorname{\mathbb{P}}}((G^{\prime}_k \setminus B') \cap (A')^c) &=0\quad\ for\ \quad m_+(\mathcal{G}) \leq k \leq m(\mathcal{G}),\end{align}
\begin{align}{\operatorname{\mathbb{P}}}((H^{\prime}_k \setminus B') \cap (A')^c) &=0\quad\ for\ \quad m_+({\mathcal{H}}) \leq k \leq m({\mathcal{H}}).\end{align}
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
\begin{align}A \cap\bigcup_{m_-(\mathcal{G}) < k \leq m(\mathcal{G}),m_-({\mathcal{H}}) < j \leq m({\mathcal{H}})} C_{k,j}&\subset A' \cap\bigcup_{m^{\prime}_-(\mathcal{G}') < k \leq m'(\mathcal{G}'),m^{\prime}_-({\mathcal{H}}')
< j \leq m'({\mathcal{H}}')} C^{\prime}_{k,j} ,\end{align}
\begin{align}\hspace*{-20pt}A' \cap \bigcup_{1 \leq k < m^{\prime}_+(\mathcal{G}'),1 \leq j < m^{\prime}_+({\mathcal{H}}')} C^{\prime}_{k,j}&\subset A \cap \bigcup_{1 \leq k < m_+(\mathcal{G}),1 \leq j
< m_+({\mathcal{H}})} C_{k,j}.\end{align}
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}})$:
\begin{align}C^{\prime}_{k,j}&=\emptyset \quad\text{ if } k \leq m_-(\mathcal{G}),\ j\geq m_+({\mathcal{H}}), \text{ and } C^{\prime}_{k,j} \subset B^c;\end{align}
\begin{align}C^{\prime}_{k,j}&=\emptyset \quad\text{ if } k \geq m_+(\mathcal{G}),\ j\leq m_-({\mathcal{H}}), \text{ and } C^{\prime}_{k,j} \subset B^c.\end{align}
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. □
Lemma 13. If 
${\operatorname{\mathbb{P}}}(B)>0$ and 
$\varepsilon>0$, then there exists 
${\textbf{S}}'$ satisfying
(i)
${\operatorname{\mathbb{P}}}(B') > {\operatorname{\mathbb{P}}}(B) - \varepsilon$,-
(ii)
$m_-(\mathcal{G}) = 1$, or $m_-(\mathcal{G}) =2$ and ${\operatorname{\mathbb{P}}}(C_{1,m({\mathcal{H}})})=0$, and -
(iii)
$m_-({\mathcal{H}}) = 1$, or $m_-({\mathcal{H}}) =2$ and ${\operatorname{\mathbb{P}}}(C_{m(\mathcal{G}),1})=0$.
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.
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}})$:
\begin{align*}C_{k,m({\mathcal{H}})} \cup C_{m_-(\mathcal{G}),m({\mathcal{H}})}\subset B \quad &\text{ and } \quad C_{k,j} \cup C_{m_-(\mathcal{G}),j}\subset B^c.\end{align*}
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
\begin{align}{\operatorname{\mathbb{P}}}\left(A^c \cap \bigcup _{k
< m_-(\mathcal{G})} C_{k, m({\mathcal{H}})} \right) &= 0\quad \text{ or }\end{align}
\begin{align}{\operatorname{\mathbb{P}}}\left(A^c \cap \bigcup _{j
< m({\mathcal{H}})} C_{m_-(\mathcal{G}), j} \right) &= 0.\end{align}
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
\begin{align}{\operatorname{\mathbb{P}}}(A^c \cap H_{m({\mathcal{H}})})={\operatorname{\mathbb{P}}}\left(A^c \cap \bigcup _{1\leq k \leq m(\mathcal{G})} C_{k, m({\mathcal{H}})} \right) = 0.\end{align}
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
\begin{align}{\operatorname{\mathbb{P}}}(A \cap G_{1})= 0.\end{align}
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}})}$.
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
\begin{align}{\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A) =0\end{align}
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
\begin{align}{\operatorname{\mathbb{P}}}\left(A \cap \bigcup _{k>m_-(\mathcal{G})} C_{k,m({\mathcal{H}})-1)} \right) &= 0\quad \text{ or }\end{align}
\begin{align}{\operatorname{\mathbb{P}}}\left(A \cap C_{2,m({\mathcal{H}})} \right) = 0.\hspace*{-30pt}\end{align}
${\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).
See the body of the article for the description.
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
\begin{align}{\operatorname{\mathbb{P}}}\left(A^c \cap C_{1,m_+({\mathcal{H}})+1} \right) &= 0\quad \text{ or }\end{align}
\begin{align}\vspace*{-16pt}{\operatorname{\mathbb{P}}}\left(A^c \cap \bigcup _{j<m_+({\mathcal{H}})} C_{2,j} \right) = 0.\end{align}
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).
See the body of the article for the description.
See the body of the article for the description.
See the body of the article for the description.
${\circled{J8}}$ Assume that (2.65) holds (see Figures 9–10); that is,
\begin{align}{\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A) =0\quad \text{ or } \quad{\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})-1}\cap A^c) =0.\end{align}
${\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
\begin{align}{\operatorname{\mathbb{P}}}\bigg(A^c \cap \bigcup _{j
< m_+({\mathcal{H}})} C_{m_-(\mathcal{G})-1, j} \bigg) &= 0\quad \text{ or }\end{align}
\begin{align}\hspace*{-10pt}{\operatorname{\mathbb{P}}}\bigg(A^c \cap \bigcup _{k
< m_-(\mathcal{G})-1} C_{k, m({\mathcal{H}})-1} \bigg) &= 0.\end{align}
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)$.
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
\begin{align}{\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G})-1,m({\mathcal{H}})-1}\cap A^c) =0.\end{align}
${\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),
\begin{align}{\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G}),m({\mathcal{H}})}\cap A^c) =0 \quad \text{ and }\quad {\operatorname{\mathbb{P}}}(C_{m_-(\mathcal{G})-1,m({\mathcal{H}})-1}\cap A) =0.\end{align}
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):
\begin{align}{\operatorname{\mathbb{P}}}(C_{1,m_+({\mathcal{H}})}\cap A) =0 \quad \text{ and }\quad {\operatorname{\mathbb{P}}}(C_{2,m({\mathcal{H}})+1}\cap A^c) =0.\end{align}
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
\begin{align}{\operatorname{\mathbb{P}}}\left(A^c \cap C_{k+1, j+1} \right) &= 0\quad \text{ or }\end{align}
\begin{align}\hspace*{-10pt}{\operatorname{\mathbb{P}}}\left(A^c \cap \bigcup _{j_1 \ne j,j+1} C_{k, j_1} \right) = 0.\end{align}
${\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
\begin{align}{\operatorname{\mathbb{P}}}(G_k \cap A^c) = {\operatorname{\mathbb{P}}}(C_{k,j+1} \cap A^c).\end{align}
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):
\begin{align}{\operatorname{\mathbb{P}}}(H_{j+1} \cap A) = {\operatorname{\mathbb{P}}}(C_{k,j+1} \cap A).\end{align}
It follows from (2.103), (2.104), 
$k\leq m_-(\mathcal{G})$, and 
$j+1\geq m_+({\mathcal{H}})$ that
\begin{align*}{\operatorname{\mathbb{P}}}(A^c\mid C_{k,j+1})&=\frac{{\operatorname{\mathbb{P}}}(A^c \cap C_{k,j+1})}{{\operatorname{\mathbb{P}}}(A^c \cap C_{k,j+1}) + {\operatorname{\mathbb{P}}}(A \cap C_{k,j+1})}\\[2pt]&\geq\frac{{\operatorname{\mathbb{P}}}(A^c \cap C_{k,j+1})}{{\operatorname{\mathbb{P}}}(A^c \cap C_{k,j+1}) + {\operatorname{\mathbb{P}}}(A \cap C_{k,j+1})+ {\operatorname{\mathbb{P}}}(G_k \setminus C_{k,j+1})}\\[2pt]& =\frac{{\operatorname{\mathbb{P}}}(A^c \cap G_k)}{{\operatorname{\mathbb{P}}}(A^c \cap C_{k,j+1}) + {\operatorname{\mathbb{P}}}(A \cap C_{k,j+1})+ {\operatorname{\mathbb{P}}}(G_k \setminus C_{k,j+1})}\\[2pt]&=\frac{{\operatorname{\mathbb{P}}}(A^c \cap G_k)}{{\operatorname{\mathbb{P}}}(G_k )}= 1 - x_k \geq 1- \delta,\end{align*}
and
\begin{align*}{\operatorname{\mathbb{P}}}(A\mid C_{k,j+1})&=\frac{{\operatorname{\mathbb{P}}}(A \cap C_{k,j+1})}{{\operatorname{\mathbb{P}}}(A^c \cap C_{k,j+1}) + {\operatorname{\mathbb{P}}}(A \cap C_{k,j+1})}\\[2pt]&\geq\frac{{\operatorname{\mathbb{P}}}(A \cap C_{k,j+1})}{{\operatorname{\mathbb{P}}}(A^c \cap C_{k,j+1}) + {\operatorname{\mathbb{P}}}(A \cap C_{k,j+1})+ {\operatorname{\mathbb{P}}}(H_{j+1} \setminus C_{k,j+1})}\\[2pt]& =\frac{{\operatorname{\mathbb{P}}}(A \cap H_{j+1})}{{\operatorname{\mathbb{P}}}(A^c \cap C_{k,j+1}) + {\operatorname{\mathbb{P}}}(A \cap C_{k,j+1})+ {\operatorname{\mathbb{P}}}(H_{j+1} \setminus C_{k,j+1})}\\[2pt]&=\frac{{\operatorname{\mathbb{P}}}(A \cap H_{j+1})}{{\operatorname{\mathbb{P}}}(H_{j+1} )}= y_{j+1}\geq 1-\delta.\end{align*}
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:
\begin{align*}{\operatorname{\mathbb{P}}}(B)-\varepsilon &\leq {\operatorname{\mathbb{P}}}(B') = \sum_{k\in{\mathcal{B}}'}{\operatorname{\mathbb{P}}}(C^{\prime}_{k,j(k)})= \sum_{k\in{\mathcal{B}}'} {\operatorname{\mathbb{P}}}(G^{\prime}_{k}\cap H^{\prime}_{j(k)})\\&\leq \sum_{k\in{\mathcal{B}}'} \frac \delta{1+\delta} ({\operatorname{\mathbb{P}}}(G^{\prime}_{k}) + {\operatorname{\mathbb{P}}}(H^{\prime}_{j(k)}))=\frac \delta{1+\delta}\left ( \sum_{k\in{\mathcal{B}}'} {\operatorname{\mathbb{P}}}(G^{\prime}_{k})+ \sum_{k\in{\mathcal{B}}'} {\operatorname{\mathbb{P}}}(H^{\prime}_{j(k)})\right)\\&\leq \frac {2\delta}{1+\delta} .\end{align*}
Since 
$\varepsilon>0$ is arbitrarily small, 
${\operatorname{\mathbb{P}}}(B) \leq 2\delta/(1+\delta)$. □
Acknowledgements
We are grateful to David Aldous and Jim Pitman for very useful advice. We thank the anonymous referees for many suggestions for improvement. The first author is supported in part by Simons Foundation Grant 506732. The second author is supported in part by NSF Grant DMS-1612483.
