# Appendix For Tightening Bounds on Probabilities of Causation By Merging
Datasets

##  Appendix A Proof of Theorem 1

To prove Theorem 1, we first state lemmas we utilize as part of our proof. The
lemmas are organized in subsections as follows. First, Lemma 1 and 2 are
needed to constrain the set of target distributions using the external dataset
(§A.1) and to express the set of target distributions compatible with the
external distribution as a system of equations and its $N$ corresponding free
parameters, where $N+1$ is the cardinality of the support of $Y$. Furthermore,
they place bounds on the free parameters in this system. Lemma 3 and 4 examine
the conditions that govern the bounds on the free parameters. Next, Lemma 5
and 6 re-express the bounds on $PNS$ originally derived using the joint
distributions $P(Z,X,Y)$ in terms of the free parameters derived in Lemma 1
and Lemma 2. Lemmas 7 through 20 examine the behavior of the maximum operators
in the bounds provided in Lemma 5 and 6 under various constraints on the free
parameters. Finally, we use these lemmas to provide the proof for the lower
bound and upper bound of the PNS. The proof for the lemmas can be found in
Section G.

###  A.1 Constraining the Set of Target Distributions Using the External
Dataset

######  Lemma 1.

Let $X$ and $Z$ be binary random variables, and let $Y$ be a discrete random
variable taking on values in $0,\dots,N$. Let $X$, $Y$ and $Z$ obey the causal
structure in Fig. 3(b). Then, given marginals $P^{T}(Z,X)$ and $P^{E}(Z,Y)$,
the conditional distributions $P(Z\mid X,Y)$ can be expressed in terms of free
parameters $P(Z=1\mid X=1,Y=i)$ for $i\in\\{1,\dots,N\\}$ as

$\displaystyle\mathbb{P}(Z=1\mid X=0,Y=0)$
$\displaystyle=\frac{p_{x}}{1-p_{x}}\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n)+\frac{p^{E}_{10}p_{y_{0}}-p^{T}_{11}p_{x}}{(1-p_{x})p_{y_{0}}}$
$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0)$
$\displaystyle=\frac{p^{T}_{11}}{p_{y_{0}}}-\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n)$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=1)$
$\displaystyle=\frac{p^{E}_{11}}{1-p_{x}}-\frac{p_{x}}{1-p_{x}}\mathbb{P}(Z=1\mid
X=1,Y=1)$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=2)$
$\displaystyle=\frac{p^{E}_{12}}{1-p_{x}}-\frac{p_{x}}{1-p_{x}}\mathbb{P}(Z=1\mid
X=1,Y=2)$ $\displaystyle\vdots$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=N)$
$\displaystyle=\frac{p^{E}_{1N}}{1-p_{x}}-\frac{p_{x}}{1-p_{x}}\mathbb{P}(Z=1\mid
X=1,Y=N)$

Where $P(X=1)$ is denoted as $p_{x}$, $P(Y=n)$ is denoted as $p_{y_{n}}$,
$P^{T}(Z=1\mid X=1)$ is denoted as $p^{T}_{11}$, $P^{T}(Z=1\mid X=0)$ is
denoted as $p^{T}_{10}$, and $P^{E}(Z=1\mid Y=n)$ is denoted as $p^{E}_{1n}$
for $n\in\\{0,\dots,N\\}$.

######  Lemma 2.

To ensure the solution to the system of equations in Lemma 1 form coherent
probabilities, the following bounds on the free parameters must hold

$\displaystyle\max\begin{bmatrix}\frac{p^{T}_{11}p_{x}-p^{E}_{10}p_{y_{0}}}{p_{x}}\\\
p_{11}-p_{y_{0}}\end{bmatrix}\leq\sum_{n=1}^{N}p_{y_{n}}\mathbb{P}(Z=1\mid
X=1,Y=n)\leq\min\begin{bmatrix}\frac{(1-p_{x})p_{y_{0}}+p^{T}_{11}p_{x}-p^{E}_{10}p_{y_{0}}}{p_{x}}\\\
p^{T}_{11}\end{bmatrix}$ (1)

And for each $i\in\\{1,\dots,N\\}$, we the bounds on the following free
parameters $P(Z=1\mid X=1,Y=i)$

$\displaystyle\max\begin{bmatrix}0\\\
\frac{p^{E}_{1i}-(1-p_{x})}{p_{x}}\end{bmatrix}\leq P(Z=1\mid
X=1,Y=i)\leq\min\begin{bmatrix}1\\\ \frac{p^{E}_{1i}}{p_{x}}\end{bmatrix}$ (2)

###  A.2 Relation of Bounds on Free Parameters to the External Dataset

Lemma 3 and Lemma 4 establish the relationship between the external dataset
and the upper and lower bounds in Lemma 2.

######  Lemma 3.

The following implications hold:

  1. 1.

$p^{E}_{10}<p_{x}\implies\frac{p^{T}_{11}p_{x}-p^{E}_{10}p_{y_{0}}}{p_{x}}>p^{T}_{11}-p_{y_{0}}$

  2. 2.

$p^{E}_{10}\geq
p_{x}\implies\frac{p^{T}_{11}p_{x}-p^{E}_{10}p_{y_{0}}}{p_{x}}\leq
p^{T}_{11}-p_{y_{0}}$

  3. 3.

$p^{E}_{10}<1-p_{x}\implies
p^{T}_{11}<\frac{(1-p_{x})p_{y_{0}}+p^{T}_{11}p_{x}-p^{E}_{10}p_{y_{0}}}{p_{x}}$

  4. 4.

$p^{E}_{10}\geq 1-p_{x}\implies
p^{T}_{11}\geq\frac{(1-p_{x})p_{y_{0}}+p^{T}_{11}p_{x}-p^{E}_{10}p_{y_{0}}}{p_{x}}$

######  Lemma 4.

For $i\in\\{1,\dots,N\\}$, when $p^{E}_{1i}\geq
1-p_{x}\implies\frac{p^{E}_{11}-(1-p_{x})}{p_{x}}\geq 0$. When
$p^{E}_{1i}<p_{x}\implies\frac{p^{E}_{11}}{p_{x}}\leq 1$

###  A.3 Bounds on PNS In Terms of Free Parameters

In Lemma 5, we re-express bounds in dawid2017probability on PC in terms of PNS
under the assumption of exogenity.

######  Lemma 5.

Let $X$, $Z$ be binary random variables, and let $Y$ be a discrete multivalued
random variable, obeying the causal structure in Fig 2. We define the $PNS$ as

$PNS\equiv P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0)$

Where $\mathbf{x}$ and $\mathbf{x^{\prime}}$ denote the setting of $X$ to $1$
and $0$ respectively. Bounds on the PNS under the causal graph in 1 given the
joint distribution $P(Z,X,Y)$ are given in dawid2017probability as

$\displaystyle\Delta\leq PNS\leq\mathbb{P}(Z=1\mid X=1)-\Gamma$

Where

$\Delta=\sum_{y}\mathbb{P}(Y=y)\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=y)-\mathbb{P}(Z=1\mid X=0,Y=y)\\}$

And $\Gamma$ is

$\displaystyle\Gamma=\sum_{y}\mathbb{P}(Y=y)\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=y)-\mathbb{P}(Z=0\mid X=0,Y=y)\\}$

At this point we remind to the reader that the above bounds require access to
the joint distribution $P(Z,X,Y)$. Given the scenario described in the paper,
we do not have access to this. Therefore, in Lemma 6 we are expressing the
joint $P(Z\mid X,Y)$ in terms of the free parameters corresponding to the
system of equations derived in Lemma 1.

######  Lemma 6.

Given $P(Z,X)$ and $P(Z,Y)$, using the solution to the system of equations in
Lemma 1, each of the terms in $\Delta$ and $\Gamma$ defined in Lemma 5 are
expressed in terms of the free parameters below. First, for $\Gamma$, each of
the terms can be written as

$\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)$
$=\frac{p^{E}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p^{T}_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$ (3)

And for the terms in $\Gamma$ corresponding to $Y=i$, $i\in\\{1,\dots,N\\}$

$P(Z=1\mid X=1,Y=i)-P(Z=0\mid X=0,Y=i)$ $P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$
(4)

Similarly, the terms in $\Delta$ can be expressed in terms of the free
parameter as

$\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=1\mid X=0,Y=0)$
$\frac{p^{T}_{11}-p^{E}_{10}p_{y_{0}}-\sum_{n=1}^{N}p_{y_{n}}\mathbb{P}(Z=1\mid
X=1,Y=n)}{(1-p_{x})p_{y_{0}}}$ (5)

And for the terms in $\Delta$ corresponding to $Y=i$, $i\in\\{1,\dots,N\\}$

$\mathbb{P}(Z=1\mid X=1,Y=1)-\mathbb{P}(Z=1\mid X=0,Y=1)$
$\frac{\mathbb{P}(Z=1\mid X=1,Y=i)-p^{E}_{1i}}{1-p_{x}}$ (6)

###  A.4 Behavior of Max Operators in $\Gamma$

The behavior of this function must be analyzed in two cases, one where
$p_{x}>1-p_{x}$, and vice-versa. We present results for $p_{x}>1-p_{x}$, and
analogous results can be derived for $p_{x}<1-p_{x}$.

######  Lemma 7.

Assume $p_{x}>1-p_{x}$. The function $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}$ defined in Lemma 6 will be greater
than or equal to $0$ when

$\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)\geq\frac{p_{y_{0}}((1-p_{x})-p^{E}_{10})}{p_{x}-(1-p_{x})}+p^{T}_{11}$
(7)

######  Lemma 8.

Assume $p_{x}>1-p_{x}$. If $p^{E}_{10}\geq p_{x}$, then

$p^{T}_{11}-p_{y_{0}}\geq\frac{p_{y_{0}}((1-p_{x})-p^{E}_{10})}{p_{x}-(1-p_{x})}+p^{T}_{11}$

######  Remark 9.

Lemma 7 and Lemma 8 imply that when $p_{x}>1-p_{x}$,
$p^{E}_{10}\geq\max\\{p_{x},1-p_{x}\\}$ then

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)\\}$ $\displaystyle=\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)$

Analogously, when $p^{E}_{10}\leq\min\\{p_{x},1-p_{x}\\}$, i.e.
$p^{E}_{10}\leq 1-p_{x}$, similar results are obtained, and to show this, we
state the following Lemmas.

######  Lemma 10.

Assume $p_{x}>1-p_{x}$. If $p^{E}_{10}<p_{x}$, then

$\frac{p^{T}_{11}p_{x}-p^{E}_{10}p_{y_{0}}}{p_{x}}<\frac{p_{y_{0}}((1-p_{x})-p^{E}_{10})}{p_{x}-(1-p_{x})}+p^{T}_{11}$

######  Lemma 11.

Assume $p_{x}>1-p_{x}$. If $p^{E}_{10}\leq 1-p_{x}$, then

$p^{T}_{11}\leq\frac{p_{y_{0}}((1-p_{x})-p^{E}_{10})}{p_{x}-(1-p_{x})}+p^{T}_{11}$

######  Remark 12.

Lemma 10 and Lemma 11 imply that when $p_{x}>1-p_{x}$,
$p^{E}_{10}\leq\min\\{p_{x},1-p_{x}\\}$ then

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)\\}=0$

Next, consider the case when $1-p_{x}<p^{\prime}_{10}<p_{x}$. Then the
following bounds hold

$\displaystyle\frac{p_{11}x-p^{\prime}_{10}y_{0}}{p_{x}}\leq\sum_{n=1}^{N}y_{n}\mathbb{P}(Z=1\mid
X=1,Y=n)\leq\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$

From Lemma 9,
$\frac{p_{11}x-p^{\prime}_{10}y_{0}}{x}<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$.
And under these conditions,

$\displaystyle\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}<\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$

Now, we provide lemmas that similarly examine the behavior of
$\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}$. As
before, the behavior of this function needs to be analyzed in two case, and we
provide lemmas for $p_{x}>1-p_{x}$, and lemmas for $p_{x}<1-p_{x}$ can be
analogously derived.

######  Lemma 13.

Assume $p_{x}>1-p_{x}$. The function $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}\geq 0$ for $i\in\\{1,\dots,N\\}$ when

$\displaystyle P(Z=1\mid
X=1,Y=i)\leq\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

######  Lemma 14.

Assume $p_{x}>1-p_{x}$. If $p^{\prime}_{1i}\geq x$ for $i\in\\{1,\dots,N\\}$,
then

$\displaystyle 1\leq\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

This implies that when $p^{\prime}_{1i}\geq\max\\{p_{x},1-p_{x}\\}$, then

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid
X=0,Y=i)\\}$ $\displaystyle=\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid
X=0,Y=i)$

Next, when $p^{\prime}_{1i}\leq\min\\{p_{x},1-p_{x}\\}$, then consider the
following Lemmas.

######  Lemma 15.

Assume $p_{x}>1-p_{x}$. If $p^{\prime}_{1i}<p_{x}$ for $i\in\\{1,\dots,N\\}$,
then

$\displaystyle\frac{p^{\prime}_{11}}{p_{x}}>\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

######  Lemma 16.

Assume $p_{x}>1-p_{x}$. If $p^{\prime}_{1i}\leq 1-p_{x}$ for
$i\in\\{1,\dots,N\\}$, then

$\displaystyle 0\geq\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

This implies that when $p^{\prime}_{1i}\leq\min\\{p_{x},1-p_{x}\\}$, then

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid
X=0,Y=i)\\}=0$

And when $1-p_{x}<p^{\prime}_{1i}<p_{x}$, then
$\frac{p^{\prime}_{11}}{p_{x}}>\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$
and
$\frac{p^{\prime}_{11}-(1-p_{x})}{p_{x}}<\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$.

###  A.5 Behavior of Max Operators in $\Delta$

######  Lemma 17.

The function $\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=1\mid
X=0,Y=0)\\}\geq 0$ when

$\displaystyle
p_{11}-p^{\prime}_{10}p_{y_{0}}\geq\sum_{n=1}^{N}p_{y_{n}}\mathbb{P}(Z=1\mid
X=1,Y=n)$

######  Lemma 18.

The following inequalities hold

$p_{11}\geq p_{11}-p^{\prime}_{10}p_{y_{0}}$ (8)
$\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}\geq
p_{11}-p^{\prime}_{10}y_{0}$ (9) $p_{11}-p_{y_{0}}\leq
p_{11}-p^{\prime}_{10}y_{0}$
$\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq
p_{11}-p^{\prime}_{10}y_{0}$

###### Proof.

The upper bound is $\frac{p_{11}}{y_{1}}$: Assume

$\displaystyle\frac{p_{11}}{y_{1}}$
$\displaystyle<\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$
$\displaystyle\implies$ $\displaystyle 0<-\frac{p^{\prime}_{10}y_{0}}{y_{1}}$

This is a contradiction, hence

$\frac{p_{11}}{y_{1}}\geq\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$

The upper bound is $\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$: Assume

$\displaystyle\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$
$\displaystyle>\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{xy_{1}}$
$\displaystyle p_{11}-p^{\prime}_{10}y_{0}$
$\displaystyle>\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$
$\displaystyle p_{11}x-p^{\prime}_{10}xy_{0}$
$\displaystyle>(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}$
$\displaystyle-p^{\prime}_{10}xy_{0}$
$\displaystyle>(1-x)y_{0}-p^{\prime}_{10}y_{0}$ $\displaystyle
p^{\prime}_{10}y_{0}(1-x)$ $\displaystyle>(1-x)y_{0}$ $\displaystyle\implies
p^{\prime}_{10}$ $\displaystyle>1$

∎

This Lemma implies that $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=1\mid X=0,Y=0)\\}$ can be either zero or non-zero over
the range of the free parameters.

Now, we similarly examine the behavior of $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=1\mid X=0,Y=i)\\}$.

######  Lemma 19.

The function $\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=1\mid
X=0,Y=i)\\}\geq 0$ for $i\in\\{1,\dots,N\\}$ when

$p^{\prime}_{1i}\leq P(Z=1\mid X=1,Y=1)$

######  Lemma 20.

The following inequalities hold

$\displaystyle 1$ $\displaystyle\geq p^{\prime}_{1i}$
$\displaystyle\frac{p^{\prime}_{1i}}{p_{x}}$ $\displaystyle\geq
p^{\prime}_{1i}$ $\displaystyle 0$ $\displaystyle\leq p^{\prime}_{1i}$
$\displaystyle\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}}$ $\displaystyle\leq
p^{\prime}_{1i}$

This Lemma implies that $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=1\mid X=0,Y=i)\\}$ can be either zero or non-zero over
the range of the free parameters.

###  A.6 Behavior of Upper Bound on PNS Under Special Conditions

Here we analyze the behavior of the upper bound on the PNS in Theorem 1 under
certain conditions, since these will be used in the proof of Theorem 1.

######  Lemma 21.

Given the upper bound in Theorem 2 on PNS, when $p_{x}>1-p_{x}$ and all
$p^{\prime}_{1i}\geq p_{x}$ for $i\in\\{0,\dots,N\\}$ and , then

$p_{00}<p_{11}-\sum_{i=0}^{N}\Phi_{i}$

###### Proof.

Since $p^{\prime}_{1i}\geq p_{x}$ for all $i$, then all the indicators will
evaluate to $1$, as a result $p_{11}-\sum_{i=0}^{N}\Phi_{i}$ will equal

$\displaystyle
p_{11}-\sum_{i=0}^{N}\frac{p_{y_{i}}(p^{\prime}_{1i}-p_{x})}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{11}(1-p_{x})-\sum_{i=0}^{N}p_{y_{i}}(p^{\prime}_{1i}-p_{x})}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{11}(1-p_{x})-p_{11}p_{x}-p_{10}(1-p_{x})+p_{x}}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{11}(1-p_{x})-p_{11}p_{x}+p_{00}(1-p_{x})-(1-p_{x})+p_{x}}{1-p_{x}}$
$\displaystyle\implies=p_{01}(\frac{p_{x}}{1-p_{x}}-1)+p_{00}$

And since $p_{x}>1-p_{x}$, this quantity will be greater than $p_{00}$. ∎

######  Lemma 22.

Given the upper bound in Theorem 2 on PNS, when $p_{x}>1-p_{x}$ and
$p^{\prime}_{1i}\leq 1-p_{x}$ for $i\in\\{0,\dots,N\\}$ and , then

$p_{00}-\sum_{i=0}^{N}\Theta_{i}>p_{11}$

###### Proof.

Since $p^{\prime}_{1i}\leq 1-p_{x}$ for all $i$, then all the indicators will
evaluate to $1$, as a result $p_{00}-\sum_{i=0}^{N}\Theta_{i}$ will equal

$\displaystyle
p_{00}-\sum_{i=0}^{N}\frac{p_{y_{i}}((1-p_{x})-p^{\prime}_{1i})}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{00}(1-p_{x})-(1-p_{x})+\sum_{i=0}^{N}p_{y_{i}}p^{\prime}_{1i}}{1-p_{x}}$
$\displaystyle\implies=\frac{-p_{10}(1-p_{x})+\sum_{i=0}^{N}p_{y_{i}}p^{\prime}_{1i}}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{11}p_{x}}{1-p_{x}}$

And since $p_{x}>1-p_{x}$, this concludes the proof. ∎

######  Lemma 23.

Given the upper bound in Theorem 2 on PNS, when $p_{x}<1-p_{x}$ and all
$p^{\prime}_{1i}\geq 1-p_{x}$ for $i\in\\{0,\dots,N\\}$ and , then

$p_{00}<p_{11}-\sum_{i=0}^{N}\Phi_{i}$

###### Proof.

Since $p^{\prime}_{1i}\geq 1-p_{x}$ for all $i$, then all the indicators will
evaluate to $1$, as a result $p_{11}-\sum_{i=0}^{N}\Phi_{i}$ will equal

$\displaystyle
p_{11}-\sum_{i=0}^{N}\frac{p_{y_{i}}(p^{\prime}_{1i}-(1-p_{x}))}{p_{x}}$
$\displaystyle\implies=\frac{p_{11}p_{x}-\sum_{i=0}^{N}p_{y_{i}}(p^{\prime}_{1i}-(1-p_{x}))}{p_{x}}$
$\displaystyle\implies=\frac{p_{11}p_{x}-p_{11}p_{x}-p_{10}(1-p_{x})+(1-p_{x})}{p_{x}}$
$\displaystyle\implies=\frac{p_{00}(1-p_{x})}{p_{x}}$

And since $p_{x}<1-p_{x}$, this quantity will be greater than $p_{00}$. ∎

######  Lemma 24.

Given the upper bound in Theorem 2 on PNS, when $p_{x}<1-p_{x}$ and
$p^{\prime}_{1i}\leq p_{x}$ for $i\in\\{0,\dots,N\\}$ and , then

$p_{00}-\sum_{i=0}^{N}\Theta_{i}>p_{11}$

###### Proof.

Since $p^{\prime}_{1i}\leq p_{x}$ for all $i$, then all the indicators will
evaluate to $1$, as a result $p_{00}-\sum_{i=0}^{N}\Theta_{i}$ will equal

$\displaystyle
p_{00}-\sum_{i=0}^{N}\frac{p_{y_{i}}(p_{x}-p^{\prime}_{1i})}{p_{x}}$
$\displaystyle\implies=\frac{p_{00}p_{x}-p_{x}+\sum_{i=0}^{N}p_{y_{i}}p^{\prime}_{1i}}{p_{x}}$
$\displaystyle\implies=\frac{-p_{10}p_{x}+p_{10}(1-p_{x})}{p_{x}}+p_{11}$
$\displaystyle\implies=p_{10}(\frac{1-p_{x}}{p_{x}}-1)+p_{11}$

And since $1-p_{x}>p_{x}$, the ineqality holds. ∎

######  Lemma 25.

Assume $p_{x}>1-p_{x}$. Assume all $1-p_{x}<p^{\prime}_{1i}<p_{x}$. Then all
max operators to can open simultaneously if and only if $\Phi_{X}\geq 0$.

###### Proof.

To prove an if and only if, we first show that all max operators opening
implies $p_{11}+p_{10}-1\geq 0$, and then the other way round.

Starting with the first, note that for all max operators to open
simultaneously, the following conditions must hold

$\displaystyle\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)\geq\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$

And for all $i\in\\{1,\dots N\\}$

$\displaystyle P(Z=1\mid
X=1,Y=i)\leq\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

This is equivalent to

$\displaystyle\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}\leq\sum_{i=1}^{N}p_{y_{i}}\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$
$\displaystyle\implies
p_{y_{0}}((1-p_{x})-p^{\prime}_{10})+p_{11}(p_{x}-(1-p_{x}))+\leq\sum_{i=1}^{N}p_{y_{i}}(p^{\prime}_{1i}-(1-p_{x}))$
$\displaystyle\implies(1-p_{x})+p_{11}(p_{x}-(1-p_{x}))+\leq\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}+p^{\prime}_{10}p_{y_{0}}$
$\displaystyle\implies(1-p_{x})-p_{11}(1-p_{x})+\leq p_{10}(1-p_{x})$
$\displaystyle\implies 0\leq p_{11}+p_{10}-1$

Next, to prove the backward implication, we utilize a proof by contrapositive,
i.e. we must prove that .

$\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}>\sum_{i=1}^{N}p_{y_{i}}\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}\implies
p_{11}+p_{10}-1<0$

To see this, note that

$\displaystyle\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}>\sum_{i=1}^{N}p_{y_{i}}\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$
$\displaystyle\implies
p_{y_{0}}((1-p_{x})-p^{\prime}_{10})+p_{11}(p_{x}-(1-p_{x}))>\sum_{i=1}^{N}p_{y_{i}}(p^{\prime}_{1i}-(1-p_{x}))$
$\displaystyle\implies(1-p_{x})-p_{11}(1-p_{x})>p_{10}p_{x}$
$\displaystyle\implies 0>p_{11}+p_{10}-1$

∎

######  Lemma 26.

All max operators in $\Delta$ can open simultaneously if and only if
$p_{11}-p_{10}\geq 0$.

###### Proof.

To prove an if and only if, we first show that all max operators opening
implies $p_{11}-p_{10}\geq 0$, and then the other way round.

Starting with the first, note that for all max operators to open
simultaneously, the following conditions must hold

$\displaystyle
p_{11}-p^{\prime}_{10}p_{y_{0}}\geq\sum_{n=1}^{N}p_{y_{n}}\mathbb{P}(Z=1\mid
X=1,Y=n)$

And for all $i\in\\{1,\dots N\\}$

$\displaystyle P(Z=1\mid X=1,Y=i)\geq p^{\prime}_{1i}$

This is equivalent to

$\displaystyle\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}\leq
p_{11}-p^{\prime}_{10}p_{y_{0}}$
$\displaystyle\implies\sum_{i=0}^{N}p_{y_{i}}p^{\prime}_{1i}\leq p_{11}$
$\displaystyle\implies p_{11}p_{x}+p_{10}(1-p_{x})\leq p_{11}$
$\displaystyle\implies 0\leq(1-p_{x})(p_{11}-p_{10})$

This proves the forward implication. A similar proof for the backward
implication can be provided using a proof by contra positive as well,
concluding the proof for this lemma. ∎

###  A.7 Proof Of Upper Bound In Theorem 1

According to Theorem 1, the upper bound is given as

$\displaystyle
PNS\leq\min\begin{bmatrix}p_{11}-\sum_{i=0}^{1}\mathbb{I}(p^{\prime}_{1i}\geq\max\\{1-p_{x},p_{x}\\})\frac{p_{y_{i}}(p^{\prime}_{1i}-\max\\{1-p_{x},p_{x}\\})}{\min\\{1-p_{x},p_{x}\\}}\\\
p_{00}-\sum_{i=0}^{1}\mathbb{I}(p^{\prime}_{1i}\leq\min\\{1-p_{x},p_{x}\\})\frac{p_{y_{i}}(\min\\{1-p_{x},p_{x}\\}-p^{\prime}_{1i})}{\min\\{1-p_{x},p_{x}\\}}\\\
\end{bmatrix}$

The upper bound is obtained by solving

$\displaystyle PNS\leq\mathbb{P}(Z=1\mid X=1)-\min_{P_{i}}\Gamma(P_{i})$

We follow a proof by cases approach, and demonstrate on a case-by-case basis
that $\mathbb{P}(Z=1\mid X=1)-\min_{P_{i}}\Gamma(P_{i})$ equals the bounds
proposed in Theorem 1.

Given binary $Y$, we can use Lemma 1 and Lemma 2 to obtain the solutions for
the joint distribution given the marginals, by constraining the following
conditionals $P(Z=1|X,Y)$ with respect to the free parameter $P(Z=1\mid
X=1,Y=1)$.

$\displaystyle\mathbb{P}(Z=1\mid X=0,Y=0)$
$\displaystyle=\frac{p_{x}}{1-p_{x}}\frac{p_{y_{1}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=1)+\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}$
$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0)$
$\displaystyle=\frac{p_{11}}{p_{y_{0}}}-\frac{p_{y_{1}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=1)$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=1)$
$\displaystyle=\frac{p^{\prime}_{11}}{1-p_{x}}-\frac{p_{x}}{1-p_{x}}\mathbb{P}(Z=1\mid
X=1,Y=1)$

And the following bounds on the free parameter $P(Z=1\mid X=1,Y=1)$ must hold

$\displaystyle\max\begin{bmatrix}\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\\\
p_{11}-p_{y_{0}}\end{bmatrix}\leq y_{1}\mathbb{P}(Z=1\mid
X=1,Y=1)\leq\min\begin{bmatrix}\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\\\
p_{11}\end{bmatrix}$ (10)

Along with

$\displaystyle\max\begin{bmatrix}0\\\
\frac{p^{\prime}_{11}-(1-p_{x})}{p_{x}}\end{bmatrix}\leq P(Z=1\mid
X=1,Y=1)\leq\min\begin{bmatrix}1\\\
\frac{p^{\prime}_{11}}{p_{x}}\end{bmatrix}$ (11)

In the binary case, $\Gamma$ is expressed as

$\displaystyle\Gamma$ $\displaystyle=P(Y=0)\max\\{0,P(Z=1\mid
X=1,Y=0)-P(Z=0\mid X=0,Y=0)\\}$ $\displaystyle+P(Y=1)\max\\{0,P(Z=1\mid
X=1,Y=1)-P(Z=0\mid X=0,Y=1)\\}$

And based on Lemma 6, each of these terms in $\Gamma$ can be written as

  1. 1.

$P(Z=1\mid X=1,Y=0)-P(Z=0\mid X=0,Y=0)$
$\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{p_{y_{1}}P(Z=1\mid
X=1,Y=1)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$ (12)

  2. 2.

$P(Z=1\mid X=1,Y=1)-P(Z=0\mid X=0,Y=1)$ $P(Z=1\mid
X=1,Y=1)(1-\frac{p_{x}}{1-p_{x}})+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}\\\
$ (13)

####  A.7.1 $p_{x}=1-p_{x}$

In this setting, we will prove the following equations hold

$p_{11}-\min_{P_{i}}\Gamma(P_{i})=p_{11}-\sum_{i=0}^{1}\mathbb{I}(p^{\prime}_{1i}\geq\max\\{1-p_{x},p_{x}\\})\frac{p_{y_{i}}(p^{\prime}_{1i}-\max\\{1-p_{x},p_{x}\\})}{\min\\{1-p_{x},p_{x}\\}}$
(14)

And

$p_{11}-\min_{P_{i}}\Gamma(P_{i})=p_{00}-\sum_{i=0}^{N}\mathbb{I}(p^{\prime}_{1i}\leq\min\\{1-p_{x},p_{x}\\})\frac{p_{y_{i}}(\min\\{1-p_{x},p_{x}\\}-p^{\prime}_{1i})}{\min\\{1-p_{x},p_{x}\\}}$
(15)

Note that when $p_{x}=1-p_{x}$, $\Gamma$ is no longer a function of $P(Z=1\mid
X=1,Y=1)$ since 12 and 13 are no longer a function of $P(Z=1\mid X=1,Y=1)$.
$\Gamma$ will equal

$\displaystyle\Gamma=p_{y_{0}}\max\\{0,\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}\\}+p_{y_{1}}\max\\{0,\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}\\}$

And the upper bound on PNS will equal

$\displaystyle p_{11}-\Gamma$

Next, we show on a case by case basis that $p_{11}-\Gamma$ will always equal
both 14 and 15. We provide the proof for one case, and the rest of the cases
can be proved in a similar fashion.
Case I: $p^{\prime}_{10}\geq 1-p_{x}$ and $p^{\prime}_{11}\geq 1-p_{x}$:
$\Gamma$ will equal

$\displaystyle\Gamma$
$\displaystyle=\frac{p_{y_{0}}p^{\prime}_{10}-p_{y_{0}}(1-p_{x})}{1-p_{x}}+\frac{p_{y_{1}}p^{\prime}_{11}-p_{y_{1}}(1-p_{x})}{1-p_{x}}$
$\displaystyle\implies p_{11}-\Gamma$
$\displaystyle=p_{11}-\frac{p_{y_{0}}p^{\prime}_{10}-p_{y_{0}}(1-p_{x})}{1-p_{x}}-\frac{p_{y_{1}}p^{\prime}_{11}-p_{y_{1}}(1-p_{x})}{1-p_{x}}$

By direct comparison, this is equal to 14. Next, to prove the equality to 15,
note that

$\displaystyle
p_{11}-\frac{p_{y_{0}}p^{\prime}_{10}-p_{y_{0}}(1-p_{x})}{1-p_{x}}-\frac{p_{y_{1}}p^{\prime}_{11}-p_{y_{1}}(1-p_{x})}{1-p_{x}}$
Since $p_{x}=1-p_{x}$
$\displaystyle\implies=\frac{p_{11}p_{x}-p_{y_{0}}p^{\prime}_{10}+p_{y_{0}}(1-p_{x})-p_{y_{1}}p^{\prime}_{11}+p_{y_{1}}(1-p_{x})}{1-p_{x}}$
$\displaystyle=\frac{-p_{10}(1-p_{x})+(1-p_{x})}{1-p_{x}}$
$\displaystyle=p_{00}$

And by comparison to 15, we can see these are equal as well. This proves that
in the case $x=1-x$, $p_{11}-\Gamma$ will equal 14 and 15. Now, we move on to
the scenario where $p_{x}>1-p_{x}$.

####  A.7.2 $p_{x}>1-p_{x}$

Here we follow a similar proof by cases as well, with each case being defined
by relation of $p^{\prime}_{10}$ and $p^{\prime}_{11}$ to $p_{x}$ and
$1-p_{x}$.
Note that since $p_{x}>1-p_{x}$, $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}$ is an increasing function of the free
parameter, while $\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid
X=0,Y=i)\\}$ is a decreasing function of the free parameter.

Case I Consider the following case

$\displaystyle p_{x}$ $\displaystyle\leq p^{\prime}_{10}$ $\displaystyle
p_{x}$ $\displaystyle\leq p^{\prime}_{11}$

Since $p^{\prime}_{10}\geq\max\\{p_{x},1-p_{x}\\}$, and the same for
$p^{\prime}_{11}$, the following hold

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)\\}$ $\displaystyle=\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)$

As well as

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=1)-\mathbb{P}(Z=0\mid
X=0,Y=1)\\}$ $\displaystyle=\mathbb{P}(Z=1\mid X=1,Y=1)-\mathbb{P}(Z=0\mid
X=0,Y=1)$

And since $\Gamma$ is equal to their weighted sum, $\Gamma=\Phi_{X}$. Hence

$p_{11}-\Gamma=p_{00}$

And based on Lemma XXX (prove this later), this will equal the result in
Theorem 1.

Case II Consider the following case

$\displaystyle p^{\prime}_{10}\leq 1-p_{x}$ $\displaystyle p^{\prime}_{11}\leq
1-p_{x}$

Based on Lemma XXX and Lemma XXXX, both max operators will equal $0$ over the
entire range of the free parameter. Hence $\Gamma=0$, and the bound is
$p_{11}$.

Case III Consider the following case

$\displaystyle p_{x}$ $\displaystyle\leq p^{\prime}_{10}$ $\displaystyle
p^{\prime}_{11}$ $\displaystyle\leq 1-p_{x}$

Based on Lemma XXX, since $p^{\prime}_{1i}\leq\min\\{p_{x},1-p_{x}\\}$,
$\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}=0$ over
the entire range of the free parameter. However, since
$p^{\prime}_{10}\geq\max\\{p_{x},1-p_{x}\\}$, $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}\geq 0$.

Consequently, finding the $\min\Gamma$ comes down to solving

$\min\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}$

Since we have proved that both lower bounds are large enough to ensure
$\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}\geq 0$,
this is written as $\min\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)$. This is an increasing function of the free parameter, and the
minimum will be attained at the lower bound of the free parameter, which will
be $\max\\{0,p_{11}-p_{y_{0}}\\}$.

Substituting both values of the free parameter into $\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)$,

$\displaystyle\Gamma=\min\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)$
$\displaystyle=\max\\{\frac{p_{y_{0}}(p^{\prime}_{10}-p_{x})}{1-p_{x}},\Phi_{x}+\frac{p_{y_{1}}((1-p_{x})-p^{\prime}_{11})}{1-p_{x}}\\}$

And since the upper bound is $p_{11}-\Gamma$, then

$\displaystyle
p_{11}-\max\\{\frac{p_{y_{0}}(p^{\prime}_{10}-p_{x})}{1-p_{x}},\Phi_{x}+\frac{p_{y_{1}}((1-p_{x})-p^{\prime}_{11})}{1-p_{x}}\\}$
$\displaystyle=\min\\{p_{11}-\frac{p_{y_{0}}(p^{\prime}_{10}-p_{x})}{1-p_{x}},p_{00}-\frac{p_{y_{1}}((1-p_{x})-p^{\prime}_{11})}{1-p_{x}}\\}$

This aligns with the bounds in Theorem 1.

Case IV Consider the following case

$\displaystyle 1-p_{x}$ $\displaystyle<p_{x}\leq p^{\prime}_{10}$
$\displaystyle 1-p_{x}$ $\displaystyle<p^{\prime}_{11}<p_{x}$

Based on Lemma XXX and Lemma XXX, $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}=\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)$ over the entire range of free
parameters. However, $\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)\\}$ may be zero or non-zero, and depending on the bounds on the free
parameter. If the bounds on the free parameter allow
$\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=1)-\mathbb{P}(Z=0\mid X=0,Y=1)\\}$ to be
$0$ or non-zero, then $\min\Gamma$ would be attained at the lower bound of the
free parameter, since increasing the value of the free parameter increases the
value of $\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)\\}$, and once as long as $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=1)-\mathbb{P}(Z=0\mid X=0,Y=1)\\}$ is also non-zero their weighted sum
will evaluate to the constant $p_{11}+p_{10}-1$. However, as the value of the
free parameter increases, $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=1)-\mathbb{P}(Z=0\mid X=0,Y=1)\\}=0$ while increasing the value of the
other max operator. Since the lower bound is maximum of the two lower bounds
implied by the bounds, it becomes equivalent to choosing between
$\min\Gamma=\max\\{p_{11}+p_{10}-1,p_{11}-\frac{p_{y_{0}}(p^{\prime}_{10}-p_{x})}{1-p_{x}}\\}$,
and hence
$p_{11}-\max\\{p_{11}+p_{10}-1,\frac{p_{y_{0}}(p^{\prime}_{10}-p_{x})}{1-p_{x}}\\}$
will equal

$\min\\{p_{00},p_{11}-\frac{p_{y_{0}}(p^{\prime}_{10}-p_{x})}{1-p_{x}}$

And this matches the bounds proposed in Theorem 1.

Case V Consider the following case

$\displaystyle 1-p_{x}$ $\displaystyle<p^{\prime}_{10}<p_{x}$ $\displaystyle
1-p_{x}$ $\displaystyle<p^{\prime}_{11}<p_{x}$

Based on Lemma XX and XX, both max operators in $\Gamma$ can be non-zero or
zero over the range of the free parameters.

Based on Lemma XXX, when the range of the free parameters allow both max
operators to simultaneously equal open with non-zero terms, then
$\Gamma=p_{11}+p_{10}-1$. And deviation away from this state would be greater
than $p_{11}+p_{10}-1$ since this would allow either max operator to increase
while the other max operator that counterbalanced this increase before will
evaluate to $0$, making their sum greater than $p_{11}+p_{10}-1$.

Next, consider the case XX, when both max operators cannot simultaneously open
as non-zero terms. Based on Lemma XX, the bounds on $P(Z=1\mid X=1,Y=1)$ are

$max\begin{bmatrix}\frac{p^{\prime}_{11}-(1-p_{x})}{p_{x}}\\\
\frac{p^{\prime}_{11}p_{y_{1}}-p_{10}(1-p_{x})}{p_{x}p_{y_{1}}}\end{bmatrix}\leq
P(Z=1\mid X=1,Y=1)\leq min\begin{bmatrix}\frac{p^{\prime}_{11}}{x}\\\
\frac{(1-x)(1-y)-p_{10}(1-x)+p^{\prime}_{11}y}{xy}\end{bmatrix}$

Now, we check whether the lower bounds are greater than (b) and if the upper
bounds are less than (a).

  1. 1.

First, $\frac{p^{\prime}_{11}-(1-x)}{x}<\frac{p^{\prime}_{11}-(1-x)}{2x-1}$
since the denominator is smaller on the right hand side. This lower bound is
less than (a), and will consequently be less than (b).

  2. 2.

Checking the lower bound of $\frac{p^{\prime}_{11}y-p_{10}(1-x)}{xy}$ against
(b), using a proof by contradiction. Assume,

$\frac{p^{\prime}_{11}y-p_{10}(1-x)}{xy}>\frac{p^{\prime}_{11}y-(1-x)(p_{11}+p_{10}-1)-y(1-x)}{y(x-(1-x))}$

Checking the right hand side of the implication

$\displaystyle\implies
p^{\prime}_{11}y(x-(1-x))-p_{10}(1-x)(x-(1-x))>p^{\prime}_{11}xy-x(1-x)(p_{11}+p_{10}-1)-xy(1-x)$
$\displaystyle\implies-p^{\prime}_{11}y-p_{10}(x-(1-x))>-x(p_{11}+p_{10}-1)-xy$
$\displaystyle\implies-p^{\prime}_{11}y+p_{10}(1-x)-p_{10}x>-xp_{11}-xp_{10}+x-xy$
$\displaystyle\implies-p^{\prime}_{11}y+p_{10}(1-x)+xp_{11}>x(1-y)$
$\displaystyle\implies p^{\prime}_{10}(1-y)>x(1-y)\implies p^{\prime}_{10}>x$

This is a contradiction based on the case we are in. So,

$\frac{p^{\prime}_{11}y-p_{10}(1-x)}{xy}\leq\frac{p^{\prime}_{11}y-(1-x)(p_{11}+p_{10}-1)-y(1-x)}{y(x-(1-x))}$

Checking the upper bounds now.

  1. 1.

When the upper bound is $\frac{p^{\prime}_{11}}{x}$: Checking this against the
(a).

$\displaystyle\frac{p^{\prime}_{11}}{x}<\frac{p^{\prime}_{11}-(1-x)}{x-(1-x)}\implies
p^{\prime}_{11}x-p^{\prime}_{11}(1-x)<p^{\prime}_{11}x-x(1-x)$
$\displaystyle\implies p^{\prime}_{11}>x$

This is a contradiction because of the case we are in. So

$\frac{p^{\prime}_{11}}{x}\geq\frac{p^{\prime}_{11}-(1-x)}{x-(1-x)}$

  2. 2.

When the upper bound is $\frac{(1-x)(1-y)-p_{10}(1-x)+p^{\prime}_{11}y}{xy}$:
Assume

$\frac{(1-x)(1-y)-p_{10}(1-x)+p^{\prime}_{11}y}{xy}<\frac{p^{\prime}_{11}-(1-x)}{x-(1-x)}$
$\displaystyle\implies(1-x)(1-y)(x-(1-x))-p_{10}(1-x)(x-(1-x))+p^{\prime}_{11}y(x-(1-x))<p^{\prime}_{11}xy-
xy(1-x)$
$\displaystyle\implies(1-x)(1-y)(x-(1-x))-p_{10}(1-x)(x-(1-x))-p^{\prime}_{11}y(1-x)<-xy(1-x)$
$\displaystyle\implies(1-y)(x-(1-x))-p_{10}(x-(1-x))-p^{\prime}_{11}y<-xy$
$\displaystyle\implies x-xy-(1-y)(1-x)-p_{10}(x-(1-x))-p^{\prime}_{11}y<-xy$
$\displaystyle\implies x-(1-y)(1-x)-p_{10}(x-(1-x))-p^{\prime}_{11}y<0$
$\displaystyle\implies x-p_{10}x-(1-y)(1-x)+p_{10}(1-x)-p^{\prime}_{11}y<0$
$\displaystyle\implies x-p_{10}x-(1-y)(1-x)+p^{\prime}_{10}(1-y)-p_{11}x<0$
$\displaystyle\implies x(1-p_{10}-p_{11})-(1-y)(1-x)+p^{\prime}_{10}(1-y)<0$
$\displaystyle\implies(1-y)(p^{\prime}_{10}-(1-x))<x(p_{11}+p_{10}-1)$

This creates a contradiction since the LHS is positive but the RHS is
negative.

So, no falsification in this case. So,

$\frac{(1-x)(1-y)-p_{10}(1-x)+p^{\prime}_{11}y}{xy}\geq\frac{p^{\prime}_{11}-(1-x)}{x-(1-x)}$

This shows that there will always be a region of the space of the free
parameter where both max operators will evaluate to $0$, making this the
minimum.

Hence, $\Gamma$ will equal $0$ or depending on whether the free parameter
allows both max operators to be zero simultaneously or not. Based on Lemma
XXX, this is determined by $p_{11}+p_{10}-1\geq 0$. Hence the bounds will be

$p_{11}-\max\\{0,p_{11}+p_{10}-1\\}=\min\\{p_{11},p_{00}\\}$

Similar approaches can be used for the rest of the cases, as well as for the
case when $p_{x}<1-p_{x}$.

###  A.8 Proof Of Lower Bound In Theorem 1

Based on Lemma XX, every term in $\Delta$ can be expressed in terms of the
free parameter as

  1. 1.

$\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=1\mid X=0,Y=0)$

$\frac{p_{11}-p^{\prime}_{10}p_{y_{0}}-p_{y_{1}}\mathbb{P}(Z=1\mid
X=1,Y=1)}{(1-p_{x})p_{y_{0}}}$ (16)

  2. 2.

$\mathbb{P}(Z=1\mid X=1,Y=1)-\mathbb{P}(Z=1\mid X=0,Y=1)$

$\frac{\mathbb{P}(Z=1\mid X=1,Y=1)-p^{\prime}_{11}}{1-p_{x}}$ (17)

First, consider the case when both max operators can open with non-zero terms
at the same time, i.e. $p^{\prime}_{11}<P(Z=1\mid
X=1,Y=1)<\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$, which based on Lemma
XXXX, happens when $p_{11}-p_{10}>0$. In this case, $\Delta$ is minimized for
values of the free parameter when all the max operators are non-zero.

This can be seen on a case by case basis, where we first examine how to
decrease Eq. 16. This would be accomplished by increasing the value of
$P(Z=1\mid X=1,Y=1)$, however, this also increases the value of Eq. 17. Since
their weighted sum is a constant, it means that the increase of one
counterbalances the decrease in another, however, after a certain point since
the max operator corresponding to Eq. 16 starts evaluating to $0$, this
increase is no longer counterbalanced, leading to Eq. 17 taking on a value
greater than $p_{11}-p_{10}$ (the value of the sum of both max operators).

Next, consider the case when $p_{11}-p_{10}\leq 0$, based on Lemma XXX, both
max operators cannot open with non-zero terms at the same time. First we check
whether any lower bounds are large enough to make $P(Z=1\mid
X=1,Y=1)-p^{\prime}_{11}>0$.

We utilize a proof by contradiction to show each of the lower bounds cannot be
greater than $p^{\prime}_{11}$. When the lower bound is $0$ or
$\frac{p^{\prime}_{11}-(1-p_{x})}{p_{x}}$, from Lemma XX we have seen there
are not large enough to make $\max\\{0,P(Z=1\mid X=1,Y=1)\\}$ equal to a non-
zero value. We now check the remaining possibilities for lower bounds.

  1. 1.

If the lower bound is $\frac{p_{11}-y_{0}}{y_{1}}$: Assume

$\displaystyle\frac{p_{11}-y_{0}}{y_{1}}$ $\displaystyle>p^{\prime}_{11}$
$\displaystyle\implies(1-x)(p_{11}-p_{10})>y_{0}p^{\prime}_{00}$

This is a contradiction since $p_{11}-p_{10}\leq 0$, hence

$\frac{p_{11}-y_{0}}{y_{1}}\leq p^{\prime}_{11}$

  2. 2.

The lower bound is $\frac{p_{11}x-p^{\prime}_{10}y_{0}}{xy_{1}}$: Assume

$\displaystyle\frac{p_{11}x-p^{\prime}_{10}y_{0}}{xy_{1}}$
$\displaystyle>p^{\prime}_{11}$ $\displaystyle\implies
p_{11}-p_{10}>p^{\prime}_{10}y_{0}$

And this is a contradiction as well for the same reasons as before, hence

$\frac{p_{11}x-p^{\prime}_{10}y_{0}}{xy_{1}}\leq p^{\prime}_{11}\\\ $

Hence, we have shown the lower bounds are always going to allow
$\max\\{0,P(Z=1\mid X=1,Y=1)\\}$ to take on the value of $0$. Next, checking
whether the upper bound restrict the range of
$\max\\{0,\frac{p_{11}-p^{\prime}_{10}y_{0}-y_{1}\mathbb{P}(Z=1\mid
X=1,Y=1)}{(1-x)y_{0}}\\}$.

From Lemma XXX, this requires $P(Z=1\mid
X=1,Y=1)<\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$. Following a similar
argument as before, we need the upper bound on $P(Z=1\mid X=1,Y=1)$ to be less
than $\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$. From Lemma XXX,
$\frac{p_{11}}{y_{1}}$ and $\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$
are greater, so we prove the remaining bounds.

  1. 1.

The upper bound is $1$: Assume

$\displaystyle 1$ $\displaystyle<\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$
$\displaystyle y_{1}$
$\displaystyle<p_{11}-p_{11}x-p_{10}(1-x)+p^{\prime}_{11}y_{1}$
$\displaystyle\implies$ $\displaystyle
y_{1}p^{\prime}_{01}<(1-x)(p_{11}-p_{10})$

This is a contradiction as well, hence

$1\geq\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$

  2. 2.

The upper bound is $\frac{p^{\prime}_{11}}{x}$: Assume

$\displaystyle\frac{p^{\prime}_{11}}{x}$
$\displaystyle<\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$
$\displaystyle\implies$
$\displaystyle(1-x)p^{\prime}_{11}y_{1}<(1-x)(p_{11}-p_{10})$

This is a contradiction, hence

$\frac{p^{\prime}_{11}}{x}\geq\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$

Since we have shown that the lower bound of $P(Z=1\mid X=1,Y=1)$ is always
less than $p^{\prime}_{11}$ and the upper bound is always greater than
$\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$, there will always be a value of
$P(Z=1\mid X=1,Y=1)$ allowed such that both max operators open as $0$.

So we have shown that when $p_{11}-p_{10}>0$, $\Delta$ will evaluate to
$p_{11}-p_{10}$, and $0$ otherwise. This concludes the proof of the lower
bound.

##  Appendix B Proof of Theorem 2

The proof for this Theorem follows a similar proof for the proof of Theorem 1,
and we prove the lower bounds and upper bounds separately.

Based on Lemma 2, the following bounds hold for the free parameters.

$\displaystyle\max\begin{bmatrix}\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\\\
p_{11}-p_{y_{0}}\end{bmatrix}\leq\sum_{n=1}^{N}y_{n}\mathbb{P}(Z=1\mid
X=1,Y=n)\leq\min\begin{bmatrix}\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}y_{0}}{p_{x}}\\\
p_{11}\end{bmatrix}$ (18)

And for each $i\in\\{1,\dots,N\\}$, we the bounds on the following free
parameters $P(Z=1\mid X=1,Y=i)$

$\displaystyle\max\begin{bmatrix}0\\\
\frac{p^{\prime}_{1i}-(1-x)}{x}\end{bmatrix}\leq P(Z=1\mid
X=1,Y=i)\leq\min\begin{bmatrix}1\\\ \frac{p^{\prime}_{1i}}{x}\end{bmatrix}$
(19)

###  B.1 Proof for Upper Bound in Theorem 2

In the binary case, $\Gamma$ is expressed as

$\Gamma&=\sum_{y}P(Y=y)\max\\{0,P(Z=1\mid X=1,Y=y)-P(Z=0\mid X=0,Y=y)\\}$ (20)

And based on Lemma 6, each of these terms in $\Gamma$ can be written as

  1. 1.

$P(Z=1\mid X=1,Y=0)-P(Z=0\mid X=0,Y=0)$
$\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{p_{y_{1}}P(Z=1\mid
X=1,Y=1)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$ (21)

  2. 2.

$P(Z=1\mid X=1,Y=1)-P(Z=0\mid X=0,Y=1)$ $P(Z=1\mid
X=1,Y=1)(1-\frac{p_{x}}{1-p_{x}})+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}\\\
$ (22)

####  B.1.1 $p_{x}=1-p_{x}$

In this setting, we will prove the following equations hold

$p_{11}-\min_{P_{i}}\Gamma(P_{i})=p_{11}-\sum_{i=0}^{N}\mathbb{I}(p^{\prime}_{1i}\geq\max\\{1-p_{x},p_{x}\\})\frac{p_{y_{i}}(p^{\prime}_{1i}-\max\\{1-p_{x},p_{x}\\})}{\min\\{1-p_{x},p_{x}\\}}$
(23)

And

$p_{11}-\min_{P_{i}}\Gamma(P_{i})=p_{00}-\sum_{i=0}^{N}\mathbb{I}(p^{\prime}_{1i}\leq\min\\{1-p_{x},p_{x}\\})\frac{p_{y_{i}}(\min\\{1-p_{x},p_{x}\\}-p^{\prime}_{1i})}{\min\\{1-p_{x},p_{x}\\}}$
(24)

Note that when $p_{x}=1-p_{x}$, $\Gamma$ is no longer a function of $P(Z=1\mid
X=1,Y=1)$ since 21 and 22 are no longer a function of $P(Z=1\mid X=1,Y=1)$.
$\Gamma$ will equal

$\displaystyle\Gamma=\sum_{i=0}^{N}p_{y_{i}}\max\\{0,\frac{p^{\prime}_{1i}-(1-p_{x})}{1-p_{x}}\\}$

Next, we show on a case by case basis that $p_{11}-\Gamma$ will always equal
both 23 and 24. Partition the set $\\{0,\dots,N\\}$ into two disjoint subsets
$R$ and $L$ such that $\forall i\in R$, $p^{\prime}_{1i}\geq p_{x}$, $\forall
j\in L$, $p^{\prime}_{1j}\leq p_{x}$. Then, $p_{11}-\Gamma$ will evaluate to

$p_{11}-\Gamma=p_{11}-\sum_{r\in
R}p_{y_{r}}\frac{p^{\prime}_{1r}-(1-p_{x})}{1-p_{x}}$ (25)

By direct comparison, this is equal to Eq. 23. Next, since $p_{x}=1-p_{x}$ Eq.
25 can be written as

$\displaystyle\frac{p_{11}p_{x}-\sum_{r\in
R}p_{y_{r}}(p^{\prime}_{1r}-(1-p_{x}))}{1-p_{x}}$ Using the identity
$p_{11}p_{x}+p_{10}(1-p_{x})=\sum_{i=0}^{N}p^{\prime}_{1i}p_{y_{i}}$
$\displaystyle\implies=\frac{-p_{10}(1-p_{x})+\sum_{l\in
L}p_{y_{l}}p^{\prime}_{1l}+(1-\sum_{l\in L}p_{y_{l}})(1-p_{x})}{1-p_{x}}$
$\displaystyle\implies=p_{00}-\sum_{l\in
L}\frac{p_{y_{l}}((1-p_{x})-p^{\prime}_{1l})}{1-p_{x}}$

And by comparison to 15, we can see these are equal as well. This proves that
in the case $x=1-x$, $p_{11}-\Gamma$ will equal 14 and 15. Now, we move on to
the scenario where $p_{x}>1-p_{x}$.

###  B.2 $p_{x}>1-p_{x}$

We prove the bounds when $p_{x}>1-p_{x}$ in the following cases.
Case I: Consider the following case. $p^{\prime}_{10}\leq\min{p_{x},1-p_{x}}$.
Partition $\\{1,\dots N\\}$ into three disjoint subsets $L$, $R$ and $S$ such
that $\forall l\in L\;p^{\prime}_{1l}\leq\min\\{p_{x},1-p_{x}\\}$, $\forall
r\in R\;p^{\prime}_{1r}\geq\max\\{p_{x},1-p_{x}\\}$, and $\forall s\in
S\;1-p_{x}<p^{\prime}_{1s}<p_{x}$.

Then, from Lemma XXX and XXXX, $\max\\{P(Z=1\mid X=1,Y=0)-P(Z=0\mid
X=0,Y=0)\\}=0$ over the entire range of the free parameters. Similarly,
$\forall l\max\\{P(Z=1\mid X=1,Y=l)-P(Z=0\mid X=0,Y=l)\\}=0$ over the entire
range of free parameters.

For the remaining max operators in $\Gamma$ corresponding to $S$ and $R$, they
will all vary independently and be decreasing functions of their corresponding
free parameter. Hence, to minimize $\Gamma$ over the range of free parameters,
we want to minimize each of the max operators in $\Gamma$ corresponding to $S$
and $R$ while obeying the bounds on the free parameters.

From Lemma XXX, all $\forall r\in R\max\\{P(Z=1\mid X=1,Y=r)-P(Z=0\mid
X=0,Y=r)\\}=P(Z=1\mid X=1,Y=r)-P(Z=0\mid X=0,Y=r)$. Similarly, all the max
operators corresponding to $S$ can be zero or non-zero.

We consider the following values of free parameters will minimize $Gamma$.

  1. 1.

$\forall l\in L\;P(Z=1\mid X=1,Y=l)=0$

  2. 2.

$\forall r\in R\;P(Z=1\mid X=1,Y=l)=1$

  3. 3.

$\forall s\in S\;P(Z=1\mid
X=1,Y=l)=\frac{p^{\prime}_{1s}-(1-p_{x})}{p_{x}-(1-p_{x})}$

This setting of free parameters minimizes $Gamma$ because it sets all the max
operators capable of attaining $0$ equal to $0$, while minimizing the
remaining max operators. This would result in $Gamma$ evaluating as

$\Gamma=\sum_{r\in R}p_{y_{r}}\frac{p^{\prime}_{1r}-p_{x}}{1-p_{x}}$

However, we must check whether this setting of the free parameters obeys the
restrictions on the weighted sum of free parameters. To this end, we must
check

$\displaystyle\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq\sum_{s\in
S}y_{s}\frac{p^{\prime}_{1s}-(1-p_{x})}{p_{x}-(1-p_{x})}+\sum_{r\in
R}p_{y_{r}}\leq p_{11}$ (26)

With respect to the lower bound, even if $\sum_{s\in
S}y_{s}\frac{p^{\prime}_{1s}-(1-p_{x})}{p_{x}-(1-p_{x})}+\sum_{r\in
R}p_{y_{r}}$ not sufficiently large enough, the only parameters that are
allowed to increase are $P(Z=1\mid X=1,Y=0)$, $P(Z=1\mid X=1,Y=l)$ and
$P(Z=1\mid X=1,Y=s)$, since the remaining parameters are already set at their
individual upper bounds. This will not change the value of $\Gamma$ since the
corresponding max operators will still remain $0$ even with the increase in
the value of free parameters.

However, when this upper bound does not hold, then, we must minimize $\Gamma$
while obeying $\sum_{i=1}^{N}p_{y_{i}}P(Z=1\mid X=1,Y=i)\leq p_{11}$. To
evaluate this, note that any solution to $\min\Gamma$ will set all the max
operators $\forall s\in S\;P(Z=1\mid X=1,Y=s)-P(Z=0\mid X=0,Y=s)$ to exactly
$0$ or greater, since further reduction still gives a zero, while restricting
the range of the other free parameters, thereby increasing the value of
$\Gamma$. Therefore, $\forall s\in S\;\max\\{0,P(Z=1\mid X=1,Y=s)-P(Z=0\mid
X=0,Y=s)\\}=P(Z=1\mid X=1,Y=s)-P(Z=0\mid X=0,Y=s)$. Now, $\Gamma$ will be
evaluated as

$\displaystyle\Gamma$ $\displaystyle=\min_{P}\sum_{s\in S}P(Y=s)(P(Z=1\mid
X=1,Y=s)-P(Z=0\mid X=1,Y=s))$ $\displaystyle+\sum_{r\in R}P(Y=r)(P(Z=1\mid
X=1,Y=r)-P(Z=0\mid X=1,Y=r))$ (27)

And expressing this in terms of free parameters as

$\displaystyle\Gamma$ $\displaystyle=\min_{P}\sum_{i\in
R,S}p_{y_{i}}(P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\sum_{i\in
R,S}p_{y_{i}}\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}})$
$\displaystyle=\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}\sum_{i\in
R,S}p_{y_{i}}P(Z=1\mid X=1,Y=i)+\sum_{i\in
R,S}\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$

Since $\Gamma$ is a decreasing function of the weighted sum of free
parameters, it will be minimized at the upper bound of
$\sum_{i=1}^{N}P(Z=1\mid X=1,Y=i)$, which in this case equals $p_{11}$. And
since the solution for $\min\Gamma$ will set $\forall l\in L\;P(Z=1\mid
X=1,L=l)=0$, $\sum_{i\in R,S}p_{y_{i}}(P(Z=1\mid X=1,Y=i)=p_{11}$. Plugging
this into the expression of $\Gamma$ evaluates to

$\displaystyle\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}p_{11}+\sum_{i\in
R,S}p_{y_{i}}\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$
$\displaystyle\implies=p_{11}+\frac{-p_{11}p_{x}+\sum_{i\in
R,S}p_{y_{i}}(p^{\prime}_{11}-(1-p_{x}))}{1-p_{x}}$
$\displaystyle\implies=p_{11}+\frac{p_{10}(1-p_{x})-\sum_{l\in
l}p_{y_{l}}p^{\prime}_{1l}-\sum_{i\in R,S}p_{y_{i}}(1-p_{x})}{1-p_{x}}$
$\displaystyle\implies=p_{11}+\frac{p_{10}(1-p_{x})-(1-p_{x})-\sum_{l\in
l}p_{y_{l}}p^{\prime}_{1l}-\sum_{i\in
R,S}p_{y_{i}}(1-p_{x})+(1-p_{x})}{1-p_{x}}$
$\displaystyle\implies=p_{11}+p_{10}-1+\frac{-\sum_{l\in
l}p_{y_{l}}p^{\prime}_{1l}+\sum_{l\in L}p_{y_{l}}(1-p_{x})}{1-p_{x}}$
$\displaystyle\implies=p_{11}+p_{10}-1+\sum_{l\in
L}p_{y_{l}}\frac{(1-p_{x})-p^{\prime}_{1l}}{1-p_{x}}$

Hence, $\min\Gamma$ will be decided by whether $p_{11}<\sum_{s\in
S}y_{s}\frac{p^{\prime}_{1s}-(1-p_{x})}{p_{x}-(1-p_{x})}+\sum_{r\in
R}p_{y_{r}}$ or not. And since $\Gamma$ is a decreasing one-to-one function of
the free parameter, this is equivalent to choosing $\max\\{\sum_{r\in
R}p_{y_{r}}\frac{p^{\prime}_{1r}-p_{x}}{1-p_{x}},p_{11}+p_{10}-1+\sum_{l\in
L}p_{y_{l}}\frac{(1-p_{x})-p^{\prime}_{1l}}{1-p_{x}}\\}$. Since this this is
subtracted from $p_{11}$, this max can be converted to a min again, giving us
the desired upper bound.

Case II: Consider the following case.
$p^{\prime}_{10}\geq\max{p_{x},1-p_{x}}$. Partition $\\{1,\dots N\\}$ into
three disjoint subsets $L$, $R$ and $S$ such that $\forall l\in
L\;p^{\prime}_{1l}\leq\min\\{p_{x},1-p_{x}\\}$, $\forall r\in
R\;p^{\prime}_{1r}\geq\max\\{p_{x},1-p_{x}\\}$, and $\forall s\in
S\;1-p_{x}<p^{\prime}_{1s}<p_{x}$.

Then, from Lemma XXX and XXXX, $\max\\{0,P(Z=1\mid X=1,Y=0)-P(Z=0\mid
X=0,Y=0)\\}=P(Z=1\mid X=1,Y=0)-P(Z=0\mid X=0,Y=0)$ over the entire range of
the free parameters. Similarly, $\forall l\max\\{P(Z=1\mid X=1,Y=l)-P(Z=0\mid
X=0,Y=l)\\}=0$, and $\forall r\max\\{P(Z=1\mid X=1,Y=r)-P(Z=0\mid
X=0,Y=r)\\}=P(Z=1\mid X=1,Y=r)-P(Z=0\mid X=0,Y=r)$ over the entire range of
free parameters.

In this case, $\Gamma$ will evaluate to

$\displaystyle\Gamma=$ $\displaystyle\sum_{i\in\\{0,R\\}}P(Y=i)(P(Z=1\mid
X=1,Y=i)-P(Z=0\mid X=0,Y=i))$ $\displaystyle+\sum_{s\in
S}P(Y=s)\max\\{0,P(Z=1\mid X=1,Y=s)-P(Z=0\mid X=0,Y=s)$ (28)

Expressing this in terms of free parameters, we get

$\displaystyle\Gamma=$ $\displaystyle
p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+(\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11})\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$
$\displaystyle+\sum_{i\in R}p_{y_{i}}\\{P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}\\}$
$\displaystyle+\sum_{s\in S}P(Y=s)\max\\{0,P(Z=1\mid
X=1,Y=s)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}\\}$
(29)

The above can be simplified to

$\displaystyle
p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}-p_{11}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}+\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)$ $\displaystyle+\sum_{i\in
R}\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}p_{y_{i}}P(Z=1\mid
X=1,Y=i)+\sum_{i\in R}p_{y_{r}}\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$
$\displaystyle+\sum_{s\in S}p_{y_{s}}\max\\{0,P(Z=1\mid
X=1,Y=s)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}\\}$
$\displaystyle\implies=p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}-p_{11}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$
$\displaystyle+\sum_{i\in
R}p_{y_{r}}\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}+\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}\sum_{n\in
N\setminus R}p_{y_{n}}P(Z=1\mid X=1,Y=n)$ $\displaystyle+\sum_{s\in
S}p_{y_{s}}\max\\{0,P(Z=1\mid
X=1,Y=s)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}\\}$

So, minimizing the above is equivalent to minimizing the following since
$p_{x}>1-p_{x}$ and probabilities are non-negative.

$\displaystyle\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}\sum_{l\in
L}p_{y_{l}}P(Z=1\mid
X=1,Y=n)+\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}\sum_{s\in
S}p_{y_{s}}P(Z=1\mid X=1,Y=n)$ $\displaystyle+\sum_{s\in
S}p_{y_{s}}\max\\{0,P(Z=1\mid
X=1,Y=s)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}\\}$

First, all the free parameters corresponding to $l$ will be minimized when set
to $0$, which is allowed based on our assumption.

Note that when the max operator is equal to $P(Z=1\mid
X=1,Y=s)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}$,
the weighted sums of the free parameter cancel each other and equal a
constant, i.e. both of them have a counterbalancing effect.

Hence the minimum is attained when each max operator is exactly $P(Z=1\mid
X=1,Y=s)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}$,
since any deviation away from this will only increase the value of the free
parameters without counterbalancing their increase with the max operator since
it would be $0$. Then this evaluates to

$\displaystyle\implies=p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}-p_{11}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}+\sum_{i\in
R}p_{y_{r}}\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$
$\displaystyle+\sum_{s\in
S}p_{y_{s}}\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}\\}$

And following a similar calculation as the previous case, this can be
simplified to

$\displaystyle\Gamma=p_{11}+p_{10}-1+\sum_{l\in
L}p_{y_{l}}\frac{(1-p_{x})-p^{\prime}_{1l}}{1-p_{x}}$

However, the above calculations assume that the constraints on the free
parameters allow it to take on values such that the max operators behave as we
describe. Specifically, this involves $P(Z=1\mid
X=1,Y=r)=\frac{p^{\prime}_{1r}}{p_{x}}$, letting all the variables
corresponding to $S$ equal
$\frac{p^{\prime}_{1s}-(1-p_{x})}{p_{x}-(1-p_{x})}$, and all the variables in
$L$ equal to $0$. In the case where $\sum_{i=1}^{N}p_{y_{N}}P(Z=1\mid
X=1,Y=i)\geq p_{11}-p_{y_{0}}$. In this case, $\Gamma$, following a similar
argument for $S$ as before, $\Gamma$ will evaluate to

$\displaystyle\Gamma=$ $\displaystyle\sum_{i\in\\{0,R\\}}P(Y=i)(P(Z=1\mid
X=1,Y=i)-P(Z=0\mid X=0,Y=i))$ $\displaystyle+\sum_{s\in S}P(Y=s)(P(Z=1\mid
X=1,Y=s)-P(Z=0\mid X=0,Y=s))$ (30)
$\displaystyle=p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}-p_{11}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}+\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)$ $\displaystyle+\sum_{i\in
R}\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}p_{y_{i}}P(Z=1\mid
X=1,Y=i)+\sum_{r\in R}p_{y_{r}}\frac{p^{\prime}_{1r}-(1-p_{x})}{1-p_{x}}$
$\displaystyle+\sum_{s\in S}p_{y_{s}}(P(Z=1\mid
X=1,Y=s)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}\\})$

And canceling out relevant terms yields

$\displaystyle=p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}-p_{11}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}+\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}\sum_{l\in
L}p_{y_{l}}P(Z=1\mid X=1,Y=l)$ $\displaystyle+\sum_{r\in
R}p_{y_{r}}\frac{p^{\prime}_{1r}-(1-p_{x})}{1-p_{x}}+\sum_{s\in
S}p_{y_{s}}\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}\\}$

To minimize this quantity, we must find the minimum allowed value of
$\sum_{l\in L}p_{y_{l}}P(Z=1\mid X=1,Y=l)$ while still respecting
$\sum_{i=1}^{N}p_{y_{N}}P(Z=1\mid X=1,Y=i)\geq p_{11}-p_{y_{0}}$ and having
the max operators behave the same way. This means $\forall r\in R$, set
$P(Z=1\mid X=1,Y=r)=1$ to the highest possible value since these cancel out.
Next, set $\forall s\in S$, set $P(Z=1\mid
X=1,S=s)=\frac{p^{\prime}_{1s}-(1-p_{x})}{p_{x}-(1-p_{x})}$. This entails the
following bounds

$\displaystyle p_{11}-p_{y_{0}}\leq\sum_{l\in L}p_{y_{l}}P(Z=1\mid
X=1,Y=l)+\sum_{s\in
S}p_{y_{s}}\frac{p^{\prime}_{1s}-(1-p_{x})}{p_{x}-(1-p_{x})}+\sum_{r\in
R}p_{y_{r}}$

Substituting the lowest possible value for $\sum_{l\in L}p_{y_{l}}P(Z=1\mid
X=1,Y=l)$ into the equation above

$\displaystyle=p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}-p_{11}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$
$\displaystyle+\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}\Bigg{(}p_{11}-p_{y_{0}}-\sum_{s\in
S}p_{y_{s}}\frac{p^{\prime}_{1s}-(1-p_{x})}{p_{x}-(1-p_{x})}-\sum_{r\in
R}p_{y_{r}}\Bigg{)}$ $\displaystyle+\sum_{r\in
R}p_{y_{r}}\frac{p^{\prime}_{1r}-(1-p_{x})}{1-p_{x}}+\sum_{s\in
S}p_{y_{s}}\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}\\}$

And this can be simplified as

$\displaystyle=p_{y_{0}}\frac{p^{\prime}_{10}-p_{x}}{1-p_{x}}+\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}\Bigg{(}-\sum_{s\in
S}p_{y_{s}}\frac{p^{\prime}_{1s}-(1-p_{x})}{p_{x}-(1-p_{x})}-\sum_{r\in
R}p_{y_{r}}\Bigg{)}$ $\displaystyle+\sum_{r\in
R}p_{y_{r}}\frac{p^{\prime}_{1r}-(1-p_{x})}{1-p_{x}}+\sum_{s\in
S}p_{y_{s}}\frac{p^{\prime}_{1s}-(1-p_{x})}{1-p_{x}}\\}$
$\displaystyle\implies=p_{y_{0}}\frac{p^{\prime}_{10}-p_{x}}{1-p_{x}}+\sum_{r\in
R}p_{y_{r}}\frac{p^{\prime}_{1r}-p_{x}}{1-p_{x}}$

And subtracting this from $p_{11}$, and applying a similar argument as before
using the one to one correspondence of the free parameter with the bounds can
be used to prove these match the bounds in Theorem 2.

Case III: Consider the following case.
$1-p_{x}<p^{\prime}_{10}<\max{p_{x},1-p_{x}}$. Partition $\\{1,\dots N\\}$
into three disjoint subsets $L$, $R$ and $S$ such that $\forall l\in
L\;p^{\prime}_{1l}\leq\min\\{p_{x},1-p_{x}\\}$, $\forall r\in
R\;p^{\prime}_{1r}\geq\max\\{p_{x},1-p_{x}\\}$, and $\forall s\in
S\;1-p_{x}<p^{\prime}_{1s}<p_{x}$.

We first consider the special case where for all $i$,
$1-p_{x}<p^{\prime}_{1i}<p_{x}$. Then, from Lemma XXX, for all max operators
to simultaneously equal $P(Z=1\mid X=1,Y=i)-P(Z=0\mid X=0,Y=i)$, then
$p_{11}+p_{10}-1\geq 0$. Here, by a similar argument as Theorem 1, if
$p_{11}+p_{10}-1\geq 0$, then all max operators will cancel out the values for
the free parameter, and any shift from this will be greater because the
counterbalancing action of the max operators will not be there.

Next, we consider the case where $p_{11}+p_{10}-1<0$. Here all bounds cannot
simultaneously open, and so we check whether the bounds on the free parameters
all allow the max operators to evaluate to $0$.

From Lemma XXX, when $P(Z=1\mid
X=1,Y=i)=\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$, then the
$\max\\{0,P(Z=1\mid X=1,Y=i)-P(Z=0\mid X=0,Y=i\\}=0$. However, we still need
to examine the behavior of $\max\\{0,P(Z=1\mid X=1,Y=0)-P(Z=0\mid X=0,Y=0\\}$
at the value. So we check whether
$\sum_{i=1}^{N}p_{y_{i}}\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}\leq\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$.

Following a similar calculation as Lemma XXX, we can show that
$p_{11}+p_{10}-1<0\implies\sum_{i=1}^{N}p_{y_{i}}\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$,
which means that there at this value of free parameters
$\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$, all the max operators can
open as $0$. When the lower bound from individual bounds group overrides the
sum bounds group, this will be a valid solution and make all max operators
equal $0$. However, when the sum of bounds lower bound overrides this, we know
this bound still alolows for $P(Y=0)$ max operator to equal $0$, and since it
has only increase the lower bound, it will only decrease already $0$
individual max operators, always allowing $0$ as a solution.

So when $p_{11}+p_{10}-1\geq 0$, all max operators open and give the bound of
$p_{11}-p_{10}-1$, and otherwise $0$. This proves the bounds we care about.

###  B.3 Proof for Lower Bound in Theorem 2

As seen in Lemma XXX, when $p_{11}-p_{10}\geq 0$, all max operators can open.
In this case, this will be the minimum since any deviation from this setting
results in one of the max operators becoming $0$ and no longer being able to
counterbalance the increase in the other, leading to an increase in the
overall value of $\Delta$.

Next, consider the case where $p_{11}-p_{10}<0$, then all max operators cannot
open simultaneously. Here we show that all max operators equaling $0$ will be
a valid point in the space of the free parameters. For $i\in\\{1,\dots,N\\}$,
each of their corresponding max operators will equal $0$ when $P(Z=1\mid
X=1,Y=i)=p^{\prime}_{1i}$. As seen in Lemma XX, the individual bounds on
$P(Z=1\mid X=1,Y=1)$ allow this point to exist. Next, we check whether this
setting of $P(Z=1\mid X=1,Y=i)$ makes the $P(Y=0)$ max operator evaluate to
$0$, i.e. $\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}\geq
p_{11}-p^{\prime}_{10}p_{y_{0}}$. And since $p_{11}-p_{10}<0$,
$\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}>p_{11}-p^{\prime}_{10}p_{y_{0}}$.

However, this still requires us to ensure
$\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}$ is a valid setting for the free
parameter, and therefore we must check whether this is less than both the
upper bounds on the weighted sum of the free parameter, i.e.

$\displaystyle\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}\leq p_{11}$
$\displaystyle\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}\leq\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$

To check the first, see that

$\displaystyle\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}\leq p_{11}$
$\displaystyle\implies
p_{11}p_{x}+p_{10}(1-p_{x})-p^{\prime}_{10}p_{y_{0}}\leq p_{11}$
$\displaystyle\implies-p^{\prime}_{10}p_{y_{0}}\leq(1-p_{x})(p_{11}-p_{10})$

And this show the point evaluating to $0$ will be contained when $p_{11}$ is
the upper bound.

Next, when $\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$ is the lower
bound, this mean this is smaller than $p_{11}$. Since the $P(Y=0)$ max
operator can still equal $0$, we set $\sum_{i=1}^{N}p_{y_{i}}P(Z=1\mid
X=1,Y=i)$ equal to $p_{11}-p^{\prime}_{10}p_{y_{0}}$. Since $p_{11}-p_{10}<0$,
then $p_{11}-p^{\prime}_{10}p_{y_{0}}<\sum_{i=1}^{N}p^{\prime}_{1i}$, this
means the values of the individual free parameter can be lowered even more
than $p^{\prime}_{1i}$, allowing the remaining max operators to equal $0$ as
well. This shows that in all cases, the solution of $0$ will be contained.

And by a similar reasoning as before, this means
$\Delta=\max\\{0,p_{11}-p_{10}\\}$.

##  Appendix C Proof of Theorem 3

To prove Theorem 3, we first state lemmas we utilize in the proof. Proofs can
be found in Section XX.

######  Lemma 27.

Let $X$ and $Z$ be binary random variables, and let $Y$ be a discrete random
variable taking on values in $0,\dots,N$. Assume access to two distributions
$P^{T}(Z,X)$ and $P^{E}(Z,Y)$, where $P^{T}(Y)=P^{E}(Y)$,
$P^{E}(X)=P^{T}(X)+\delta_{X}$, $X\perp\\!\\!\\!\perp Y$ in both $P^{E}$ and
$P^{T}$ and $P^{T}(Z=1\mid X,Y)=P^{E}(Z=1\mid X,Y)$. The conditional
distributions $P^{T}(Z\mid X,Y)$ can be expressed as a system of equations
with free parameters $P^{T}(Z=1\mid X=1,Y=i)$ for $i\in\\{1,\dots,N\\}$ as

$\displaystyle P^{T}(Z=1\mid X=0,Y=0)$
$\displaystyle=\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}P^{T}(Z=1\mid
X=1,Y=n)+\frac{p^{E}_{10}p_{y_{0}}-p^{T}_{11}(p_{x}+\delta_{X})}{(1-p_{x}-\delta_{X})p_{y_{0}}}$
$\displaystyle P^{T}(Z=1\mid X=1,Y=0)$
$\displaystyle=\frac{p^{T}_{11}}{p_{y_{0}}}-\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}P^{T}(Z=1\mid
X=1,Y=n)$ $\displaystyle P^{T}(Z=1\mid X=0,Y=1)$
$\displaystyle=\frac{p^{E}_{11}}{1-p_{x}-\delta_{X}}-\frac{p_{x}+\deltaXX}{1-p_{x}-\delta_{X}}P^{T}(Z=1\mid
X=1,Y=1)$ $\displaystyle P^{T}(Z=1\mid X=0,Y=2)$
$\displaystyle=\frac{p^{E}_{12}}{1-p_{x}-\delta_{X}}-\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}P^{T}(Z=1\mid
X=1,Y=2)$ $\displaystyle\vdots$ $\displaystyle P^{T}(Z=1\mid X=0,Y=N)$
$\displaystyle=\frac{p^{E}_{1N}}{1-p_{x}-\delta_{X}}-\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}P^{T}(Z=1\mid
X=1,Y=N)$

Where $P^{T}(X=1)$ is denoted as $p_{x}$ , $P^{T}(Y=n)=P^{E}(Y=n)$ is denoted
as $p_{y_{n}}$, $P^{T}(Z=1\mid X=1)$ is denoted as $p^{T}_{11}$,
$P^{T}(Z=1\mid X=0)$ is denoted as $p^{T}_{10}$, and $P^{T}(Z=1\mid Y=n)$ is
denoted as $p^{E}_{1n}$ for $n\in\\{0,\dots,N\\}$.

######  Lemma 28.

To ensure the solution to the system of equations in Lemma 27 form coherent
probabilities, the following bounds on the free parameters must hold

$\displaystyle\max\begin{bmatrix}\frac{p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}\\\
p^{T}_{11}-p_{y_{0}}\end{bmatrix}\leq\sum_{n=1}^{N}y_{n}P^{T}(Z=1\mid
X=1,Y=n)\leq\min\begin{bmatrix}\frac{(1-p_{x}-\delta_{X})p_{y_{0}}+p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}y_{0}}{p_{x}+\delta_{X}}\\\
p^{T}_{11}\end{bmatrix}$ (31)

And for each $i\in\\{1,\dots,N\\}$, we the bounds on the following free
parameters $P(Z=1\mid X=1,Y=i)$

$\displaystyle\max\begin{bmatrix}0\\\
\frac{p^{E}_{1i}-(1-p_{x}-\delta_{X})}{p_{x}+\delta_{X}}\end{bmatrix}\leq
P^{T}(Z=1\mid X=1,Y=i)\leq\min\begin{bmatrix}1\\\
\frac{p^{E}_{1i}}{p_{x}+\delta_{X}}\end{bmatrix}$ (32)

######  Lemma 29.

The following implications hold:

$p^{E}_{10}<p_{x}+\delta_{X}\implies\frac{p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}>p^{T}_{11}-p_{y_{0}}$
$p^{T}_{10}\geq
p_{x}+\delta_{X}\implies\frac{p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}\leq
p^{T}_{11}-p_{y_{0}}$ $p^{E}_{10}<1-p_{x}-\delta_{X}\implies
p^{T}_{11}<\frac{(1-p_{x}-\delta_{X})p_{y_{0}}+p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}$
$p^{E}_{10}\geq 1-p_{x}-\delta_{X}\implies
p^{T}_{11}\geq\frac{(1-p_{x}-\delta_{X})p_{y_{0}}+p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}$

###### Proof.

Each of these is proved using a proof by contra-positive. Starting with
$p^{E}_{10}<p_{x}+\delta_{X}\implies\frac{p_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}>p^{T}_{11}-p_{y_{0}}$,
the contra-positive of this statement is

$\frac{p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}\leq
p^{T}_{11}-p_{y_{0}}\implies p^{E}_{10}\geq p_{x}+\delta_{X}$

To see this holds, note that

$\displaystyle\frac{p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}\leq
p^{T}_{11}-p_{y_{0}}$
$\displaystyle\implies-\frac{p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}\leq-
p_{y_{0}}$ $\displaystyle\implies p^{\prime}_{10}\geq p_{x}+\delta_{X}$

This proves
$p^{E}_{10}<p_{x}+\delta_{X}\implies\frac{p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}>p^{T}_{11}-p_{y_{0}}$.
Next, for $p^{E}_{10}\geq
p_{x}+\delta_{X}\implies\frac{p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}\leq
p^{T}_{11}-p_{y_{0}}$, following a similar proof strategy, the contra-positive
can be written as

$\frac{p_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}+\delta_{X}}>p^{T}_{11}-p_{y_{0}}\implies
p^{E}_{10}<p_{x}+\delta_{X}$

To see this holds, note that

$\displaystyle\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}>p_{11}-p_{y_{0}}$
$\displaystyle\implies-\frac{p^{\prime}_{10}p_{y_{0}}}{p_{x}}>-p_{y_{0}}$
$\displaystyle\implies p^{\prime}_{10}<p_{x}$

This proves $p^{\prime}_{10}\geq
p_{x}\implies\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq
p_{11}-p_{y_{0}}$.
Next, for $p^{\prime}_{10}<1-p_{x}\implies
p_{11}<\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$,
the contra-positive is written as

$p_{11}\geq\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\implies
p^{\prime}_{10}\geq 1-p_{x}$

To see this holds, note that

$\displaystyle
p_{11}\geq\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$
$\displaystyle\implies 0\geq(1-p_{x})p_{y_{0}}-p^{\prime}_{10}p_{y_{0}}$
$\displaystyle\implies p^{\prime}_{10}\geq 1-p_{x}$

This proves $p^{\prime}_{10}<1-p_{x}\implies
p_{11}<\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$.
Next, for $p^{\prime}_{10}\geq 1-p_{x}\implies
p_{11}\geq\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$
the contra-positive is written as

$p_{11}<\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\implies
p^{\prime}_{10}<1-p_{x}$

To see this holds, note that

$\displaystyle
p_{11}<\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$
$\displaystyle\implies 0<(1-p_{x})p_{y_{0}}-p^{\prime}_{10}p_{y_{0}}$
$\displaystyle\implies p^{\prime}_{10}<1-p_{x}$

This concludes the proof. ∎

######  Lemma 30.

For $i\in\\{1,\dots,N\\}$, when
$p^{\prime}_{1i}>1-p_{x}\implies\frac{p^{\prime}_{11}-(1-p_{x})}{p_{x}}>0$.
When $p^{\prime}_{1i}<p_{x}\implies\frac{p^{\prime}_{11}}{p_{x}}<1$

######  Lemma 31.

Using the solution to the system of equations in Lemma 27, each of the terms
in $\Delta$ and $\Gamma$ defined in Lemma 5 are expressed in terms of the free
parameters below.

  1. 1.

For the term in $\Gamma$ corresponding to $Y=0$

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)$
$\displaystyle=\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$

  2. 2.

For the terms in $\Gamma$ corresponding to $Y=i$, $i\in\\{1,\dots,N\\}$

$\displaystyle P(Z=1\mid X=1,Y=i)-P(Z=0\mid X=0,Y=i)$ $\displaystyle=P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$

  3. 3.

For the term in $\Delta$ corresponding to $Y=0$:

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=1\mid X=0,Y=0)$
$\displaystyle=\frac{p_{11}-p^{\prime}_{10}p_{y_{0}}-\sum_{n=1}^{N}p_{y_{n}}\mathbb{P}(Z=1\mid
X=1,Y=n)}{(1-p_{x})p_{y_{0}}}$

  4. 4.

For the term in $\Delta$ corresponding to $Y=i$, $i\in\\{1,\dots,N\\}$

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=1)-\mathbb{P}(Z=1\mid X=0,Y=1)$
$\displaystyle=\frac{\mathbb{P}(Z=1\mid X=1,Y=i)-p^{\prime}_{1i}}{1-p_{x}}$

###### Proof.

Using the system of equations obtained in Lemma 27, each term in $\Gamma$ can
be expressed using these free parameters.

  1. 1.

$\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}$

$P^{T}(Z=1\mid
X=1,Y=0)&=\frac{p^{T}_{11}}{p_{y_{0}}}-\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}P^{T}(Z=1\mid
X=1,Y=n)$ (33) $\displaystyle P^{T}(Z=0\mid X=0,Y=0)=1-$ (34)
$\displaystyle\Bigg{(}\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}P^{T}(Z=1\mid
X=1,Y=n)+\frac{p^{E}_{10}p_{y_{0}}-p^{T}_{11}(p_{x}+\delta_{X})}{(1-p_{x}-\delta_{X})p_{y_{0}}}\Bigg{)}$
(35)

Subtracting these two and following a similar calculation as Lemma XXXX, this
simplifies to

$\frac{p^{E}_{10}-(1-p_{x}-\delta_{X})}{1-p_{x}-\delta_{X}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P^{T}(Z=1\mid
X=1,Y=n)-p^{T}_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}-1\Bigg{)}$

  2. 2.

$\max\\{0,P(Z=1\mid X=1,Y=i)-P(Z=0\mid X=0,Y=i)\\}$: The probability
$P(Z=0\mid X=0,Y=i)$ for $i\in\\{1,\dots,N\\}$ can be expressed in terms of
the free parameters as

$\displaystyle P(Z=0\mid
X=0,Y=i)=1-\Bigg{(}\frac{p^{E}_{1i}}{1-p_{x}-\delta_{X}}-\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}P^{T}(Z=1\mid
X=1,Y=i)\Bigg{)}$ $\displaystyle\implies P(Z=1\mid X=1,Y=i)-P(Z=0\mid
X=0,Y=i)$ $\displaystyle=P^{T}(Z=1\mid
X=1,Y=i)-1+\frac{p^{E}_{1i}}{1-p_{x}-\delta_{X}}-\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}P(Z=1\mid
X=1,Y=i)$ $\displaystyle=P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}\Bigg{)}+\frac{p^{E}_{11}-(1-p_{x}-\delta_{X})}{1-p_{x}-\delta_{X}}$

This concludes the proof for the terms in $\Gamma$. Next, enumerating the
calculations for the terms in $\Delta$.

  1. 1.

$\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=1\mid X=0,Y=0)$

$\displaystyle=\frac{p^{T}_{11}}{p_{y_{0}}}-\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}P^{T}(Z=1\mid
X=1,Y=n)$
$\displaystyle-\Bigg{(}\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n)+\frac{p^{E}_{10}p_{y_{0}}-p^{T}_{11}(p_{x}+\delta_{X})}{(1-p_{x}-\delta_{X}))p_{y_{0}}}\Bigg{)}$
$\displaystyle=\frac{p^{T}_{11}-p^{E}_{10}p_{y_{0}}-\sum_{n=1}^{N}p_{y_{n}}P^{T}(Z=1\mid
X=1,Y=n)}{(1-p_{x}-\delta_{X})p_{y_{0}}}$

  2. 2.

$\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=1\mid X=0,Y=i)\\}$ for
$i\in\\{1,\dots,N\\}$

$\displaystyle P^{T}(Z=1\mid
X=0,Y=i)=\frac{p^{E}_{1i}}{1-p_{x}-\delta_{X}}-\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}P^{T}(Z=1\mid
X=1,Y=i)$ $\displaystyle\implies P^{T}(Z=1\mid X=1,Y=i)-P^{T}(Z=1\mid
X=0,Y=i)$ $\displaystyle=P^{T}(Z=1\mid
X=1,Y=i)-\frac{p^{E}_{1i}}{1-p_{x}-\delta_{X}}+\frac{p_{x}+\delta_{X}}{1-p_{x}-\delta_{X}}P^{T}(Z=1\mid
X=1,Y=i)$ $\displaystyle=\frac{P^{T}(Z=1\mid
X=1,Y=i)-p^{E}_{1i}}{1-p_{x}-\delta_{X}}$

This concludes the proof of the Lemma. ∎

###  C.1 Behavior of Max Operators in $\Gamma$

The behavior of this function must be analyzed in two cases, one where
$p_{x}>1-p_{x}$, and vice-versa. We present results for $p_{x}>1-p_{x}$, and
analogous results can be derived for $p_{x}<1-p_{x}$.

######  Lemma 32.

Assume $p_{x}+\delta_{X}>1-p_{x}-\delta_{X}$. The function
$\max\\{0,P^{T}(Z=1\mid X=1,Y=0)-P^{T}(Z=0\mid X=0,Y=0)\\}\geq 0$ when

$\displaystyle\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)\geq\frac{p_{y_{0}}((1-p_{x}-\delta_{X})-p^{\prime}_{10})}{(p_{x}+\delta_{X})-(1-p_{x}-\delta_{X})}+p^{T}_{11}$

###### Proof.

From the result of Lemma LABEL:, $\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)$ can be expressed in terms of the free
parameter as

$\displaystyle\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$

Now, we use a proof by contra-positive to first show that

$\displaystyle\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}<0$
$\displaystyle\implies\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$

To see this, note that

$\displaystyle\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}<0$
$\displaystyle\implies
p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{p_{y_{0}}(1-p_{x})}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}-(1-p_{x})}{1-p_{x}}\Bigg{)}<0$
$\displaystyle\implies
p_{y_{0}}(p^{\prime}_{10}-(1-p_{x}))+(\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11})\Bigg{(}p_{x}-(1-p_{x})\Bigg{)}<0$
$\displaystyle\implies\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$

This concludes the proof. ∎

######  Lemma 33.

Assume $p_{x}+\delta_{X}>1-p_{x}-\delta_{X}$. If $p^{E}_{10}\geq
p_{x}+\delta_{X}$, then

$p^{T}_{11}-y_{0}\geq\frac{p_{y_{0}}((1-p_{x}-\delta_{X})-p^{E}_{10})}{(p_{x}+\delta_{X})-(1-p_{x}-\delta_{X})}+p^{T}_{11}$

###### Proof.

Following a proof by contra-positive, the contra-positive is given as

$\displaystyle
p_{11}-y_{0}<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}\implies
p^{\prime}_{10}<p_{x}$

To see this, note that

$\displaystyle
p_{11}-p_{y_{0}}<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$
$\displaystyle\implies-1<\frac{((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}$
$\displaystyle\implies p_{x}>p^{\prime}_{10}$

This concludes the proof. ∎

These two Lemmas imply that when $p_{x}>1-p_{x}$,
$p^{\prime}_{10}\geq\max\\{p_{x},1-p_{x}\\}$ then

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)\\}$ $\displaystyle=\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)$

Analogously, when $p^{\prime}_{10}\leq\min\\{p_{x},1-p_{x}\\}$, i.e.
$p^{\prime}_{10}\leq 1-p_{x}$, we first consider the following Lemma.

######  Lemma 34.

Assume $p_{x}>1-p_{x}-\delta_{X}$. If $p^{E}<p_{x}$, then

$\frac{p^{T}_{11}(p_{x}+\delta_{X})-p^{E}_{10}p_{y_{0}}}{p_{x}}<\frac{p_{y_{0}}((1-p_{x}-\delta_{X})-p^{E}_{10})}{(p_{x}+\delta_{X})-(1-p_{x}-\delta_{X})}+p^{T}_{11}$

###### Proof.

Following a proof by contra-positive, the contra-positive is given as

$\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\geq\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}\implies
p^{\prime}_{10}\geq p_{x}$

To see this, note that

$\displaystyle\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\geq\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$
$\displaystyle\implies\frac{-p^{\prime}_{10}}{p_{x}}\geq\frac{((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}$
$\displaystyle\implies-p^{\prime}_{10}p_{x}+p^{\prime}_{10}(1-p_{x})\geq(1-p_{x})p_{x}-p^{\prime}_{10}p_{x}$
$\displaystyle\implies p^{\prime}_{10}\geq p_{x}$

This concludes the proof. ∎

######  Lemma 35.

Assume $p_{x}>1-p_{x}$. If $p^{\prime}_{10}\leq 1-p_{x}$, then

$p_{11}\leq\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$

These two Lemmas imply that when $p_{x}>1-p_{x}$,
$p^{\prime}_{10}\leq\min\\{p_{x},1-p_{x}\\}$ then

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid
X=0,Y=0)\\}=0$

Next, consider the case when $1-p_{x}<p^{\prime}_{10}<p_{x}$. Then the
following bounds hold

$\displaystyle\frac{p_{11}x-p^{\prime}_{10}y_{0}}{p_{x}}\leq\sum_{n=1}^{N}y_{n}\mathbb{P}(Z=1\mid
X=1,Y=n)\leq\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$

From Lemma 9,
$\frac{p_{11}x-p^{\prime}_{10}y_{0}}{x}<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$.
And under these conditions,

$\displaystyle\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}<\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$

Now, we provide lemmas that similarly examine the behavior of
$\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}$. As
before, the behavior of this function needs to be analyzed in two case, and we
provide lemmas for $p_{x}>1-p_{x}$, and lemmas for $p_{x}<1-p_{x}$ can be
analogously derived.

######  Lemma 36.

Assume $p_{x}>1-p_{x}$. The function $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}\geq 0$ for $i\in\\{1,\dots,N\\}$ when

$\displaystyle P(Z=1\mid
X=1,Y=i)\leq\frac{p^{\prime}_{1i}-(1-p_{x}-\delta_{X})}{(p_{x}+\delta_{X})-(1-p_{x}-\delta_{X})}$

###### Proof.

From the result of Lemma LABEL:, $\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}$ can be expressed in terms of the free
parameter as

$P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$

Following a proof by contra-positive, we write the contra-positive as

$\displaystyle P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}<0$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)>\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

To see this, note that

$\displaystyle P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}<0$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)\Bigg{(}\frac{(1-p_{x})-p_{x}}{1-p_{x}}\Bigg{)}<\frac{(1-p_{x})-p^{\prime}_{11}}{1-p_{x}}$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)\Bigg{(}(1-p_{x})-p_{x}\Bigg{)}<(1-p_{x})-p^{\prime}_{11}$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)>\frac{p^{\prime}_{11}-(1-p_{x})}{p_{x}-(1-p_{x})}$

This concludes the proof. ∎

######  Lemma 37.

Assume $p_{x}>1-p_{x}$. If $p^{\prime}_{1i}\geq x$ for $i\in\\{1,\dots,N\\}$,
then

$\displaystyle 1\leq\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

This implies that when $p^{\prime}_{1i}\geq\max\\{p_{x},1-p_{x}\\}$, then

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid
X=0,Y=i)\\}$ $\displaystyle=\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid
X=0,Y=i)$

Next, when $p^{\prime}_{1i}\leq\min\\{p_{x},1-p_{x}\\}$, then consider the
following Lemmas.

######  Lemma 38.

Assume $p_{x}>1-p_{x}$. If $p^{\prime}_{1i}<p_{x}$ for $i\in\\{1,\dots,N\\}$,
then

$\displaystyle\frac{p^{\prime}_{11}}{p_{x}}>\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

######  Lemma 39.

Assume $p_{x}>1-p_{x}$. If $p^{\prime}_{1i}\leq 1-p_{x}$ for
$i\in\\{1,\dots,N\\}$, then

$\displaystyle 0\geq\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

This implies that when $p^{\prime}_{1i}\leq\min\\{p_{x},1-p_{x}\\}$, then

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=0\mid
X=0,Y=i)\\}=0$

And when $1-p_{x}<p^{\prime}_{1i}<p_{x}$, then
$\frac{p^{\prime}_{11}}{p_{x}}>\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$
and
$\frac{p^{\prime}_{11}-(1-p_{x})}{p_{x}}<\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$.

###  C.2 Behavior of Max Operators in $\Delta$

######  Lemma 40.

The function $\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=1\mid
X=0,Y=0)\\}\geq 0$ when

$\displaystyle
p_{11}-p^{\prime}_{10}p_{y_{0}}\geq\sum_{n=1}^{N}p_{y_{n}}\mathbb{P}(Z=1\mid
X=1,Y=n)$

######  Lemma 41.

The following inequalities hold

$p_{11}\geq p_{11}-p^{\prime}_{10}p_{y_{0}}$ (36)
$\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}\geq
p_{11}-p^{\prime}_{10}y_{0}$ (37) $p_{11}-p_{y_{0}}\leq
p_{11}-p^{\prime}_{10}y_{0}$
$\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq
p_{11}-p^{\prime}_{10}y_{0}$

###### Proof.

The upper bound is $\frac{p_{11}}{y_{1}}$: Assume

$\displaystyle\frac{p_{11}}{y_{1}}$
$\displaystyle<\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$
$\displaystyle\implies$ $\displaystyle 0<-\frac{p^{\prime}_{10}y_{0}}{y_{1}}$

This is a contradiction, hence

$\frac{p_{11}}{y_{1}}\geq\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$

The upper bound is $\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$: Assume

$\displaystyle\frac{p_{11}-p^{\prime}_{10}y_{0}}{y_{1}}$
$\displaystyle>\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{xy_{1}}$
$\displaystyle p_{11}-p^{\prime}_{10}y_{0}$
$\displaystyle>\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$
$\displaystyle p_{11}x-p^{\prime}_{10}xy_{0}$
$\displaystyle>(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}$
$\displaystyle-p^{\prime}_{10}xy_{0}$
$\displaystyle>(1-x)y_{0}-p^{\prime}_{10}y_{0}$ $\displaystyle
p^{\prime}_{10}y_{0}(1-x)$ $\displaystyle>(1-x)y_{0}$ $\displaystyle\implies
p^{\prime}_{10}$ $\displaystyle>1$

∎

This Lemma implies that $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=1\mid X=0,Y=0)\\}$ can be either zero or non-zero over
the range of the free parameters.

Now, we similarly examine the behavior of $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=1\mid X=0,Y=i)\\}$.

######  Lemma 42.

The function $\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=1\mid
X=0,Y=i)\\}\geq 0$ for $i\in\\{1,\dots,N\\}$ when

$p^{\prime}_{1i}\leq P(Z=1\mid X=1,Y=1)$

######  Lemma 43.

The following inequalities hold

$\displaystyle 1$ $\displaystyle\geq p^{\prime}_{1i}$
$\displaystyle\frac{p^{\prime}_{1i}}{p_{x}}$ $\displaystyle\geq
p^{\prime}_{1i}$ $\displaystyle 0$ $\displaystyle\leq p^{\prime}_{1i}$
$\displaystyle\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}}$ $\displaystyle\leq
p^{\prime}_{1i}$

This Lemma implies that $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=1\mid X=0,Y=i)\\}$ can be either zero or non-zero over
the range of the free parameters.

###  C.3 Behavior of Upper Bound on PNS Under Special Conditions

Here we analyze the behavior of the upper bound on the PNS in Theorem 1 under
certain conditions, since these will be used in the proof of Theorem 1.

######  Lemma 44.

Given the upper bound in Theorem 2 on PNS, when $p_{x}>1-p_{x}$ and all
$p^{\prime}_{1i}\geq p_{x}$ for $i\in\\{0,\dots,N\\}$ and , then

$p_{00}<p_{11}-\sum_{i=0}^{N}\Phi_{i}$

###### Proof.

Since $p^{\prime}_{1i}\geq p_{x}$ for all $i$, then all the indicators will
evaluate to $1$, as a result $p_{11}-\sum_{i=0}^{N}\Phi_{i}$ will equal

$\displaystyle
p_{11}-\sum_{i=0}^{N}\frac{p_{y_{i}}(p^{\prime}_{1i}-p_{x})}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{11}(1-p_{x})-\sum_{i=0}^{N}p_{y_{i}}(p^{\prime}_{1i}-p_{x})}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{11}(1-p_{x})-p_{11}p_{x}-p_{10}(1-p_{x})+p_{x}}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{11}(1-p_{x})-p_{11}p_{x}+p_{00}(1-p_{x})-(1-p_{x})+p_{x}}{1-p_{x}}$
$\displaystyle\implies=p_{01}(\frac{p_{x}}{1-p_{x}}-1)+p_{00}$

And since $p_{x}>1-p_{x}$, this quantity will be greater than $p_{00}$. ∎

######  Lemma 45.

Given the upper bound in Theorem 2 on PNS, when $p_{x}>1-p_{x}$ and
$p^{\prime}_{1i}\leq 1-p_{x}$ for $i\in\\{0,\dots,N\\}$ and , then

$p_{00}-\sum_{i=0}^{N}\Theta_{i}>p_{11}$

###### Proof.

Since $p^{\prime}_{1i}\leq 1-p_{x}$ for all $i$, then all the indicators will
evaluate to $1$, as a result $p_{00}-\sum_{i=0}^{N}\Theta_{i}$ will equal

$\displaystyle
p_{00}-\sum_{i=0}^{N}\frac{p_{y_{i}}((1-p_{x})-p^{\prime}_{1i})}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{00}(1-p_{x})-(1-p_{x})+\sum_{i=0}^{N}p_{y_{i}}p^{\prime}_{1i}}{1-p_{x}}$
$\displaystyle\implies=\frac{-p_{10}(1-p_{x})+\sum_{i=0}^{N}p_{y_{i}}p^{\prime}_{1i}}{1-p_{x}}$
$\displaystyle\implies=\frac{p_{11}p_{x}}{1-p_{x}}$

And since $p_{x}>1-p_{x}$, this concludes the proof. ∎

######  Lemma 46.

Given the upper bound in Theorem 2 on PNS, when $p_{x}<1-p_{x}$ and all
$p^{\prime}_{1i}\geq 1-p_{x}$ for $i\in\\{0,\dots,N\\}$ and , then

$p_{00}<p_{11}-\sum_{i=0}^{N}\Phi_{i}$

###### Proof.

Since $p^{\prime}_{1i}\geq 1-p_{x}$ for all $i$, then all the indicators will
evaluate to $1$, as a result $p_{11}-\sum_{i=0}^{N}\Phi_{i}$ will equal

$\displaystyle
p_{11}-\sum_{i=0}^{N}\frac{p_{y_{i}}(p^{\prime}_{1i}-(1-p_{x}))}{p_{x}}$
$\displaystyle\implies=\frac{p_{11}p_{x}-\sum_{i=0}^{N}p_{y_{i}}(p^{\prime}_{1i}-(1-p_{x}))}{p_{x}}$
$\displaystyle\implies=\frac{p_{11}p_{x}-p_{11}p_{x}-p_{10}(1-p_{x})+(1-p_{x})}{p_{x}}$
$\displaystyle\implies=\frac{p_{00}(1-p_{x})}{p_{x}}$

And since $p_{x}<1-p_{x}$, this quantity will be greater than $p_{00}$. ∎

######  Lemma 47.

Given the upper bound in Theorem 2 on PNS, when $p_{x}<1-p_{x}$ and
$p^{\prime}_{1i}\leq p_{x}$ for $i\in\\{0,\dots,N\\}$ and , then

$p_{00}-\sum_{i=0}^{N}\Theta_{i}>p_{11}$

###### Proof.

Since $p^{\prime}_{1i}\leq p_{x}$ for all $i$, then all the indicators will
evaluate to $1$, as a result $p_{00}-\sum_{i=0}^{N}\Theta_{i}$ will equal

$\displaystyle
p_{00}-\sum_{i=0}^{N}\frac{p_{y_{i}}(p_{x}-p^{\prime}_{1i})}{p_{x}}$
$\displaystyle\implies=\frac{p_{00}p_{x}-p_{x}+\sum_{i=0}^{N}p_{y_{i}}p^{\prime}_{1i}}{p_{x}}$
$\displaystyle\implies=\frac{-p_{10}p_{x}+p_{10}(1-p_{x})}{p_{x}}+p_{11}$
$\displaystyle\implies=p_{10}(\frac{1-p_{x}}{p_{x}}-1)+p_{11}$

And since $1-p_{x}>p_{x}$, the ineqality holds. ∎

######  Lemma 48.

Assume $p_{x}>1-p_{x}$. Assume all $1-p_{x}<p^{\prime}_{1i}<p_{x}$. Then all
max operators to can open simultaneously if and only if $\Phi_{X}\geq 0$.

###### Proof.

To prove an if and only if, we first show that all max operators opening
implies $p_{11}+p_{10}-1\geq 0$, and then the other way round.

Starting with the first, note that for all max operators to open
simultaneously, the following conditions must hold

$\displaystyle\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)\geq\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$

And for all $i\in\\{1,\dots N\\}$

$\displaystyle P(Z=1\mid
X=1,Y=i)\leq\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

This is equivalent to

$\displaystyle\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}\leq\sum_{i=1}^{N}p_{y_{i}}\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$
$\displaystyle\implies
p_{y_{0}}((1-p_{x})-p^{\prime}_{10})+p_{11}(p_{x}-(1-p_{x}))+\leq\sum_{i=1}^{N}p_{y_{i}}(p^{\prime}_{1i}-(1-p_{x}))$
$\displaystyle\implies(1-p_{x})+p_{11}(p_{x}-(1-p_{x}))+\leq\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}+p^{\prime}_{10}p_{y_{0}}$
$\displaystyle\implies(1-p_{x})-p_{11}(1-p_{x})+\leq p_{10}(1-p_{x})$
$\displaystyle\implies 0\leq p_{11}+p_{10}-1$

Next, to prove the backward implication, we utilize a proof by contrapositive,
i.e. we must prove that .

$\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}>\sum_{i=1}^{N}p_{y_{i}}\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}\implies
p_{11}+p_{10}-1<0$

To see this, note that

$\displaystyle\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}>\sum_{i=1}^{N}p_{y_{i}}\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$
$\displaystyle\implies
p_{y_{0}}((1-p_{x})-p^{\prime}_{10})+p_{11}(p_{x}-(1-p_{x}))>\sum_{i=1}^{N}p_{y_{i}}(p^{\prime}_{1i}-(1-p_{x}))$
$\displaystyle\implies(1-p_{x})-p_{11}(1-p_{x})>p_{10}p_{x}$
$\displaystyle\implies 0>p_{11}+p_{10}-1$

∎

######  Lemma 49.

All max operators in $\Delta$ can open simultaneously if and only if
$p_{11}-p_{10}\geq 0$.

###### Proof.

To prove an if and only if, we first show that all max operators opening
implies $p_{11}-p_{10}\geq 0$, and then the other way round.

Starting with the first, note that for all max operators to open
simultaneously, the following conditions must hold

$\displaystyle
p_{11}-p^{\prime}_{10}p_{y_{0}}\geq\sum_{n=1}^{N}p_{y_{n}}\mathbb{P}(Z=1\mid
X=1,Y=n)$

And for all $i\in\\{1,\dots N\\}$

$\displaystyle P(Z=1\mid X=1,Y=i)\geq p^{\prime}_{1i}$

This is equivalent to

$\displaystyle\sum_{i=1}^{N}p_{y_{i}}p^{\prime}_{1i}\leq
p_{11}-p^{\prime}_{10}p_{y_{0}}$
$\displaystyle\implies\sum_{i=0}^{N}p_{y_{i}}p^{\prime}_{1i}\leq p_{11}$
$\displaystyle\implies p_{11}p_{x}+p_{10}(1-p_{x})\leq p_{11}$
$\displaystyle\implies 0\leq(1-p_{x})(p_{11}-p_{10})$

This proves the forward implication. A similar proof for the backward
implication can be provided using a proof by contra positive as well,
concluding the proof for this lemma. ∎

##  Appendix D Proof of Theorem 4

We start by expressing bounds on the joint probability
$P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0,C,Y)$ as

$\max\begin{bmatrix}0\\\
P(Z_{\mathbf{x}}=1,C,Y)-P(Z_{\mathbf{x^{\prime}}}=1,C,Y)\end{bmatrix}\leq
P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0,C,Y)\leq\min\begin{bmatrix}P(Z_{\mathbf{x}}=1,C,Y)\\\
P(Z_{\mathbf{x^{\prime}}}=0,C,Y)\end{bmatrix}\par$

Where the upper bound follows from $P(A,B)\leq\min\\{P(A),P(B)\\}$ for random
variables $A$ and $B$. The lower bound is proved below.

$\displaystyle P(Z_{\mathbf{x}}=1,C,Y)-P(Z_{\mathbf{x^{\prime}}}=1,C,Y)$
$\displaystyle=P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0,C,Y)+P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=1,C,Y)$
$\displaystyle-P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=1,C,Y)-P(Z_{\mathbf{x}}=0,Z_{\mathbf{x^{\prime}}}=1,C,Y)$
$\displaystyle=P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0,C,Y)-P(Z_{\mathbf{x}}=0,Z_{\mathbf{x^{\prime}}}=1,C,Y)$

And since probabilities are non-negative, we obtain the lower bound

$\max\begin{bmatrix}0\\\
P(Z_{\mathbf{x}}=1,C,Y)-P(Z_{\mathbf{x^{\prime}}}=1,C,Y)\end{bmatrix}\leq
P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0,C,Y)$

Next, the $PNS$ is obtained by marginalizing out $C$ and $Y$, giving a lower
bound of

$\displaystyle\sum_{C,Y}\max\begin{bmatrix}0\\\
P(Z_{\mathbf{x}}=1,C,Y)-P(Z_{\mathbf{x^{\prime}}}=1,C,Y)\end{bmatrix}\leq
P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0)$

And the upper bound is given as

$\displaystyle
P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0)\leq\sum_{C,Y}\min\begin{bmatrix}P(Z_{\mathbf{x}}=1,C,Y)\\\
P(Z_{\mathbf{x^{\prime}}}=0,C,Y)\end{bmatrix}$ Since
$Z_{\mathbf{x}}\perp\\!\\!\\!\perp X$, an application of consistency allows
the above bounds to be re-written as
$\displaystyle\sum_{C,Y}P(C,Y)\max\begin{bmatrix}0\\\ P(Z=1\mid
X=1,C,Y)-P(Z=1\mid X=0,C,Y)\end{bmatrix}\leq
P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0)$ $\displaystyle
P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0)\leq\sum_{C,Y}P(C,Y)\min\begin{bmatrix}P(Z=1\mid
X=1,C,Y)\\\ P(Z=0\mid X=0,C,Y)\end{bmatrix}$

Exploiting the independence of $C$ and $Y$, the lower bound is written as

$\displaystyle\sum_{C}P(C)\Delta_{C}\leq$ $\displaystyle
P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0)$ Where
$\displaystyle\Delta_{C}=P(Y)\max\\{0,P(Z=1\mid X=1,C,Y)$
$\displaystyle-P(Z=1\mid X=0,C,Y)\\}$

Next, the minimum operator in the upper bound can be re-written as

$\displaystyle\min\begin{bmatrix}P(Z=1\mid X=1,C,Y)\\\ P(Z=0\mid
X=0,C,Y)\end{bmatrix}$ $\displaystyle=P(Z=1\mid
X=1,C,Y)-\max\begin{bmatrix}0\\\ P(Z=1\mid X=1,C,Y)-P(Z=0\mid
X=0,C,Y)\end{bmatrix}$

Consequently, the upper bound is expressed as

$\displaystyle P(Z_{\mathbf{x}}=1,Z_{\mathbf{x^{\prime}}}=0)\leq P(Z=1\mid
X=1)-\sum_{C}P(C)\Gamma_{C}$ Where
$\displaystyle\Gamma_{C}=P(Y)\max\\{0,P(Z=1\mid X=1,C,Y)-P(Z=0\mid
X=0,C,Y)\\}$

This concludes the proof of Theorem 4.

##  Appendix E Proof of Lemma 5

The bounds on PNS in Equation 2 are given as

$\Delta\leq PNS\leq P(Z=1\mid X=1)-\Gamma$ (38)

Where

$\displaystyle\Delta$
$\displaystyle=\sum_{c}\mathbb{P}(C=c)\max\\{0,\mathbb{P}(Z=1\mid
X=1,C=c)-\mathbb{P}(Z=1\mid X=0,C=c)\\}$ $\displaystyle\Gamma$
$\displaystyle=\sum_{c}\mathbb{P}(C=c)\max\\{0,\mathbb{P}(Z=1\mid
X=1,C=c)-\mathbb{P}(Z=0\mid X=0,C=c)\\}$

And the bounds in Lemma 5 are given as

$\sum_{C}P(C)\Delta_{C}\leq PNS\leq P(Z=1\mid X=1)-\sum_{C}P(C)\Gamma_{C}$
(39)

Where

$\displaystyle\Delta_{C}$
$\displaystyle=\sum_{y}\mathbb{P}(Y=y)\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=y,C)-\mathbb{P}(Z=1\mid X=0,Y=y,C)\\}$ $\displaystyle\Gamma_{C}$
$\displaystyle=\sum_{y}\mathbb{P}(Y=y)\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=y,C)-\mathbb{P}(Z=0\mid X=0,Y=y,C)\\}$

Starting with the lower bound, note that both lower bounds consist of an
identical weighted sum $P(C)$, hence understanding the difference of these
bounds comes down to examining $\max\\{0,\mathbb{P}(Z=1\mid
X=1,C=c)-\mathbb{P}(Z=1\mid X=0,C=c)\\}$ versus
$\sum_{y}\mathbb{P}(Y=y)\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=y,C)-\mathbb{P}(Z=1\mid X=0,Y=y,C)\\}$. First, note that

$\displaystyle\mathbb{P}(Z=1\mid X=1,C=c)-\mathbb{P}(Z=1\mid X=0,C=c)=$
$\displaystyle\sum_{y}P(Y=y)\Big{(}\mathbb{P}(Z=1\mid
X=1,Y=y,C)-\mathbb{P}(Z=1\mid X=0,Y=y,C)\Big{)}$

Consequently, $\max\\{0,\mathbb{P}(Z=1\mid X=1,C=c)-\mathbb{P}(Z=1\mid
X=0,C=c)\\}$ can be written as

$\displaystyle\max\\{0,\mathbb{P}(Z=1\mid X=1,C=c)-\mathbb{P}(Z=1\mid
X=0,C=c)\\}$
$\displaystyle=\max\Bigg{\\{}0,\sum_{y}P(Y=y)\Big{(}\mathbb{P}(Z=1\mid
X=1,Y=y,C)-\mathbb{P}(Z=1\mid X=0,Y=y,C)\Big{)}\Bigg{\\}}$

And $\sum_{y}\mathbb{P}(Y=y)\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=y,C)-\mathbb{P}(Z=1\mid X=0,Y=y,C)\\}$ is written as

$\displaystyle\sum_{y}\max\\{0,\mathbb{P}(Y=y)\Big{(}\mathbb{P}(Z=1\mid
X=1,Y=y,C)-\mathbb{P}(Z=1\mid X=0,Y=y,C)\Big{)}\\}$

Since the maximum of a sum is less than or equal to the sum of maximums, the
lower bound in Equation 39 will be greater than or equal to the lower bound in
Equation 38. And when for any $C$, if for some values of $Y$,
$\mathbb{P}(Z=1\mid X=1,Y=y,C)$ is greater than $\mathbb{P}(Z=1\mid
X=0,Y=y,C)$, and form some values $\mathbb{P}(Z=1\mid X=1,Y=y,C)$ is less than
$\mathbb{P}(Z=1\mid X=0,Y=y,C)$, than the lower bound in Equation 39 will be
greater than the lower bound in 38.

A similar approach can be utilized for the upper bound as well, thereby
completing the proof.

##  Appendix F Proof of Theorem 6

######  Lemma 50.

Let $X$ and $Z$ be binary random variables, and let $C$ and $Y$ be discrete
random variables taking values in $\\{0,\dots,M\\}$ and $\\{0,\dots,N\\}$
respectively. Let $\delta^{C}_{X}$ represent the link between the treatment
assignment mechaism between the $P^{E}$ and $P^{T}$ as follows

$P^{E}(X=1\mid C)=P^{T}(X=1)+\delta^{C}_{X}$

For notational ease, we introduce the following terms. Let $P^{T}(Z=1\mid
X=j,C=i)$ be denoted by $p^{T}{1ji}$ and let $P^{E}(Z=1\mid Y=j,C=i)$ be
denoted as $p^{E}_{1ji}$. Given distributions $P^{T}(Z,X,C)$ and
$P^{E}(Z,Y,C)$ obeying the following contraints

$\displaystyle p^{T}_{10i}$ $\displaystyle=\sum_{j=0}^{N}P(Z=1\mid
X=0,Y=j,C=i)p_{y_{j}}$ $\displaystyle p^{T}_{11i}$
$\displaystyle=\sum_{j=0}^{N}P(Z=1\mid X=1,Y=j,C=i)p_{y_{j}}$ $\displaystyle
p^{E}_{10i}$ $\displaystyle=P(Z=1\mid X=0,Y=0,C=i)(1-p_{x}-\delta^{i}_{X})$
$\displaystyle\hskip 14.45377pt+P(Z=1\mid X=1,Y=0,C=i)(p_{x}+\delta^{i}_{X})$
$\displaystyle\vdots$ $\displaystyle p^{E}_{1Ni}$ $\displaystyle=P(Z=1\mid
X=0,Y=N,C=i)(1-p_{x}-\delta^{i}_{X})$ $\displaystyle\hskip
14.45377pt+P(Z=1\mid X=1,Y=N,C=i)(p_{x}+\delta^{i}_{X})$

Then this system of equations can be expressed in terms of free parameters
$P(Z=1\mid X=1,Y=i,C)$ for $i\in\\{1,\dots,N\\}$ and all $C$ as

$\displaystyle\mathbb{P}(Z=1\mid X=0,Y=0,C)$
$\displaystyle=\frac{p_{x}+\delta^{C}_{X}}{1-p_{x}-\delta^{C}_{X}}\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n,C)+\frac{p^{E}_{10C}p_{y_{0}}-p^{T}_{11C}(p_{x}+\delta^{C}_{X})}{(1-p_{x}-\delta^{C}_{X})p_{y_{0}}}$
$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0,C)$
$\displaystyle=\frac{p^{T}_{11C}}{p_{y_{0}}}-\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n,C)$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=1,C)$
$\displaystyle=\frac{p^{E}_{11C}}{1-p_{x}-\delta^{C}_{X}}-\frac{p_{x}+\delta^{C}_{X}}{1-p_{x}-\delta^{C}_{X}}\mathbb{P}(Z=1\mid
X=1,Y=1,C)$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=2,C)$
$\displaystyle=\frac{p^{E}_{12C}}{1-p_{x}-\delta^{C}_{X}}-\frac{p_{x}+\delta^{C}_{X}}{1-p_{x}-\delta^{C}_{X}}\mathbb{P}(Z=1\mid
X=1,Y=2,C)$ $\displaystyle\vdots$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=N,C)$
$\displaystyle=\frac{p^{E}_{1N}}{1-p_{x}-\delta^{C}_{X}}-\frac{p_{x}+\delta^{C}_{X}}{1-p_{x}-\delta^{C}_{X}}\mathbb{P}(Z=1\mid
X=1,Y=N,C)$

######  Lemma 51.

To ensure the solution to the system of equations in Lemma LABEL:lemma:RREF-
y-c form coherent probabilities, the following bounds on the free parameters
must hold for all $C$

$\displaystyle\max\begin{bmatrix}\frac{p^{T}_{11C}(p_{x}+\delta^{C}_{X})-p^{E}_{10C}p_{y_{0}}}{p_{x}+\delta^{C}_{X}}\\\
p^{T}_{11C}-p_{y_{0}}\end{bmatrix}\leq\sum_{n=1}^{N}y_{n}P^{T}(Z=1\mid
X=1,Y=n,C)\leq\min\begin{bmatrix}\frac{(1-p_{x}-\delta^{C}_{X})p_{y_{0}}+p^{T}_{11C}(p_{x}+\delta^{C}_{X})-p^{E}_{10C}p_{y_{0}}}{p_{x}+\delta^{C}_{X}}\\\
p^{T}_{11C}\end{bmatrix}$ (40)

And for each $i\in\\{1,\dots,N\\}$, we the bounds on the following free
parameters $P(Z=1\mid X=1,Y=i,C)$

$\displaystyle\max\begin{bmatrix}0\\\
\frac{p^{E}_{1iC}-(1-p_{x}-\delta^{C}_{X})}{p_{x}+\delta^{C}_{X}}\end{bmatrix}\leq
P^{T}(Z=1\mid X=1,Y=i,C)\leq\min\begin{bmatrix}1\\\
\frac{p^{E}_{1iC}}{p_{x}+\delta^{C}_{X}}\end{bmatrix}$ (41)

######  Lemma 52.

Using the solution to the system of equations in Lemma 27, each of the terms
in $\Delta_{C}$ and $\Gamma_{C}$ defined in Lemma XXXX are expressed in terms
of the free parameters below.

  1. 1.

For the term in $\Gamma$ corresponding to $Y=0$

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0,C)-\mathbb{P}(Z=0\mid X=0,Y=0,C)$
$\displaystyle=\frac{p^{E}_{10C}-(1-p_{x}-\delta^{C}_{X})}{1-p_{x}-\delta^{C}_{X}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P^{T}(Z=1\mid
X=1,Y=n,C)-p^{T}_{11C}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}+\delta^{C}_{X}}{1-p_{x}-\delta^{C}_{X}}-1\Bigg{)}$

  2. 2.

For the terms in $\Gamma$ corresponding to $Y=i$, $i\in\\{1,\dots,N\\}$

$\displaystyle P(Z=1\mid X=1,Y=i,C)-P(Z=0\mid X=0,Y=i,C)$
$\displaystyle=P(Z=1\mid
X=1,Y=i,C)\Bigg{(}1-\frac{p_{x}+\delta^{C}_{X}}{1-p_{x}-\delta^{C}_{X}}\Bigg{)}+\frac{p^{E}_{11C}-(1-p_{x}-\delta^{C}_{X})}{1-p_{x}-\delta^{C}_{X}}$

  3. 3.

For the term in $\Delta$ corresponding to $Y=0$:

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0,C)-\mathbb{P}(Z=1\mid X=0,Y=0,C)$
$\displaystyle=\frac{p^{T}_{11C}-p^{E}_{10C}p_{y_{0}}-\sum_{n=1}^{N}p_{y_{n}}P^{T}(Z=1\mid
X=1,Y=n,C)}{(1-p_{x}-\delta^{C}_{X})p_{y_{0}}}$

  4. 4.

For the term in $\Delta$ corresponding to $Y=i$, $i\in\\{1,\dots,N\\}$

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=i,C)-\mathbb{P}(Z=1\mid X=0,Y=i,C)$
$\displaystyle=\frac{P^{T}(Z=1\mid
X=1,Y=i,C)-p^{E}_{1iC}}{1-p_{x}-\delta^{C}_{X}}$

##  Appendix G Proofs For Lemmas

Proof for Lemma 1: This lemma is proved using mathematical induction performed
on the the Reduced Row Echelon Form (RREF) of the matrix representation of the
system of equations that in Equation X that impose constraints on $P(Z\mid
X,Y)$ using $P(Z,X)$ and $P(Z,Y)$.

Using the invariances defined in Section X, we obtain the following equations
for $P(Z=1\mid X,Y)$ in terms of $P(Z,X)$ and $P(Z,Y)$. For ease of notation,
we introduce the following terms. $P(X=1)$ is denoted as $p_{x}$ , $P(Y=n)$ is
denoted as $p_{y_{n}}$, $P(Z=1\mid X=1)$ is denoted as $p_{11}$, $P(Z=1\mid
X=0)$ is denoted as $p_{10}$, and $P(Z=1\mid Y=n)$ is denoted as
$p^{\prime}_{1n}$ for $n\in\\{0,\dots,N\\}$.

$\displaystyle p_{10}$ $\displaystyle=\sum_{i=0}^{N}P(Z=1\mid
X=0,Y=n)p_{y_{n}}$ $\displaystyle p_{11}$
$\displaystyle=\sum_{n=0}^{N}P(Z=1\mid X=1,Y=n)p_{y_{n}}$ $\displaystyle
p^{\prime}_{10}$ $\displaystyle=P(Z=1\mid X=0,Y=0)(1-p_{x})+P(Z=1\mid
X=1,Y=0)p_{x}$ $\displaystyle\vdots$ $\displaystyle p^{\prime}_{1N}$
$\displaystyle=P(Z=1\mid X=0,Y=N)(1-p_{x})+P(Z=1\mid X=1,Y=N)p_{x}$

The above equations can be represented in matrix form $A\mathbf{x}=b$ as

$\displaystyle A$
$\displaystyle=\begin{bmatrix}p_{y_{0}}&0&p_{y_{1}}&0&\dots&p_{y_{N-1}}&0&p_{y_{N}}&0\\\
0&p_{y_{0}}&0&p_{y_{1}}&\dots&0&p_{y_{N-1}}&0&p_{y_{N}}\\\
1-p_{x}&p_{x}&0&0&\dots&0&0&0&0\\\ 0&0&1-p_{x}&p_{x}&\dots&0&0&0&0\\\
\vdots&\ddots&&&&&&&\vdots\\\ 0&0&\dots&0&0&1-p_{x}&p_{x}&0&0\\\
0&0&\dots&0&&0&0&1-p_{x}&p_{x}\\\ \end{bmatrix}$ $\displaystyle b$
$\displaystyle=\begin{bmatrix}p_{10}\\\ p_{11}\\\ p^{\prime}_{10}\\\
p^{\prime}_{11}\\\ p^{\prime}_{12}\vdots\\\ p^{\prime}_{1(N-1)}\\\
p^{\prime}_{1N}\\\ \end{bmatrix}\hskip
36.135pt\mathbf{x}=\begin{bmatrix}P(Z=1\mid X=0,Y=0)\\\ P(Z=1\mid X=1,Y=0)\\\
P(Z=1\mid X=0,Y=1)\\\ P(Z=1\mid X=1,Y=1)\\\ \vdots\\\ P(Z=1\mid X=0,Y=N)\\\
P(Z=1\mid X=1,Y=N)\\\ \end{bmatrix}$

Next, denote the augmented matrix $A|b$ as

$\displaystyle\begin{bmatrix}[ccccccccc|c]p_{y_{0}}&0&p_{y_{1}}&0&\dots&p_{y_{N-1}}&0&p_{y_{N}}&0&p_{10}\\\
0&p_{y_{0}}&0&p_{y_{1}}&\dots&0&p_{y_{N-1}}&0&p_{y_{N}}&p_{11}\\\
1-p_{x}&p_{x}&0&0&\dots&0&0&0&0&p^{\prime}_{10}\\\
0&0&1-p_{x}&p_{x}&\dots&0&0&0&0&p^{\prime}_{11}\\\
\vdots&\ddots&&&&&&&\vdots&\vdots\\\
0&0&\dots&0&0&1-p_{x}&p_{x}&0&0&p^{\prime}_{1(N-1)}\\\
0&0&\dots&0&&0&0&1-p_{x}&p_{x}&p^{\prime}_{1N}\\\ \end{bmatrix}$

The augmented matrix $A|b$ when expressed in RREF will express the system of
equations in terms of basic variables and free parameters. Then, this can be
compared to the system of equations presented in the Lemma to complete the
proof.

First, we utilize mathematical induction to provide a general form for the
RREF of $A|b$ for any $N$. Formally, let $P(N)$ denote the following
proposition.
Proposition: Let $P(N)$ denote the proposition that when $X$ and $Z$ are
binary, and $Y$ has support in $\\{0,\dots,N\\}$, then $A|b$ will be a matrix
with $N+3$ rows and $2(N+1)+1$ columns. The following steps when executed will
put $A|b$ in RREF, where $R_{i}$ denotes the $i$-th row of $A|b$

  1. 1.

$\displaystyle R_{1}$ $\displaystyle=R_{1}/p_{y_{0}}$ (42) $\displaystyle
R_{3}$ $\displaystyle=R_{3}-(1-p_{x})R_{1}$ (43)

  2. 2.

$\displaystyle R_{2}$ $\displaystyle=R_{2}/p_{y_{0}}$ (44) $\displaystyle
R_{3}$ $\displaystyle=R_{3}-p_{x}R_{2}$ (45)

  3. 3.

$\displaystyle R_{3}$
$\displaystyle=R3/(-\frac{(1-p_{x})p_{y_{1}}}{p_{y_{0}}})$ (46) $\displaystyle
R_{1}$ $\displaystyle=R_{1}-\frac{p_{y_{1}}}{p_{y_{0}}}R3$ (47) $\displaystyle
R_{4}$ $\displaystyle=R4-(1-p_{x})R3$ (48)

  4. 4.

If $N\geq 2$, then loop through the following steps for $i\in\\{2,\dots,N\\}$:

$\displaystyle R_{2+i}=R_{2+i}/(-\frac{p_{y_{i}}(1-p_{x})}{p_{y_{i-1}}})$ (49)
$\displaystyle R_{1+i}=R_{1+i}-\frac{p_{y_{i}}}{p_{y_{i-1}}}R_{2+i}$ (50)
$\displaystyle R_{3+i}=R_{3+i}-(1-p_{x})R_{2+i}$ (51)

And the corresponding matrix will evaluate to

$\displaystyle\begin{bmatrix}1&0&0&-\frac{p_{x}p_{y_{1}}}{(1-p_{x})p_{y_{0}}}&\dots&0&-\frac{p_{x}p_{y_{N-1}}}{(1-p_{x})p_{y_{0}}}&0&-\frac{p_{x}p_{y_{N}}}{(1-p_{x})p_{y_{0}}}&\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}\\\
0&1&0&\frac{p_{y_{1}}}{p_{y_{0}}}&\dots&0&\frac{p_{y_{N-1}}}{p_{y_{0}}}&0&\frac{p_{y_{N}}}{p_{y_{0}}}&\frac{p_{11}}{p_{y_{0}}}\\\
0&0&1&\frac{p_{x}}{1-p_{x}}&\dots&0&0&0&0&\frac{p^{\prime}_{11}}{1-p_{x}}\\\
\vdots&&&&&&&\ddots\\\
0&0&0&0&\dots&0&0&1&\frac{p_{x}}{1-p_{x}}&\frac{p_{10}(1-p_{x})+p_{11}p_{x}-\sum_{i=0}^{N-1}p^{\prime}_{1i}p_{y_{i}}}{p_{y_{N}}(1-p_{x})}\\\
0&0&0&0&\dots&0&0&0&0&\frac{\sum_{i=0}^{N}p^{\prime}_{1i}p_{y_{i}}-p_{10}(1-p_{x})-p_{11}p_{x}}{p_{y_{N}}}\end{bmatrix}$
(52)

Base Case: Starting with the base case of $N=1$, i.e. $Y$ is binary. For the
case when $Y$ is binary, we can enumerate the following equations for the
$P(Z,X,Y)$

$\displaystyle\mathbb{P}(Z=1\mid X=1)$ $\displaystyle=\mathbb{P}(Z=1\mid
X=1,Y=1)\mathbb{P}(Y=1)+\mathbb{P}(Z=1\mid X=1,Y=0)\mathbb{P}(Y=0)$
$\displaystyle\mathbb{P}(Z=1\mid X=0)$ $\displaystyle=\mathbb{P}(Z=1\mid
X=0,Y=1)\mathbb{P}(Y=1)+\mathbb{P}(Z=1\mid X=0,Y=0)\mathbb{P}(Y=0)$
$\displaystyle\mathbb{P}(Z=1\mid Y=1)$ $\displaystyle=\mathbb{P}(Z=1\mid
X=0,Y=1)\mathbb{P}(X=0)+\mathbb{P}(Z=1\mid X=1,Y=1)\mathbb{P}(X=1)$
$\displaystyle\mathbb{P}(Z=1\mid Y=0)$ $\displaystyle=\mathbb{P}(Z=1\mid
X=0,Y=0)\mathbb{P}(X=0)+\mathbb{P}(Z=1\mid X=1,Y=0)\mathbb{P}(X=1)$

And the augmented matrix $A|b$ will be written as

$\displaystyle A|b$
$\displaystyle=\begin{bmatrix}p_{y_{0}}&0&p_{y_{1}}&0&p_{10}\\\
0&p_{y_{0}}&0&p_{y_{1}}&p_{11}\\\ 1-p_{x}&p_{x}&0&0&p^{\prime}_{10}\\\
0&0&1-p_{x}&p_{x}&p^{\prime}_{11}\end{bmatrix}\hskip
18.06749pt\mathbf{x}=\begin{bmatrix}P(Z=1\mid X=0,Y=0)\\\ P(Z=1\mid
X=1,Y=0)\\\ P(Z=1\mid X=0,Y=1)\\\ P(Z=1\mid X=1,Y=1)\\\ \end{bmatrix}$

Executing the row operations on $A|b$ gives the following matrix

$\displaystyle\begin{bmatrix}1&0&0&-\frac{p_{x}p_{y_{1}}}{(1-p_{x})p_{y_{0}}}&\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}\\\
0&1&0&\frac{p_{y_{1}}}{p_{y_{0}}}&\frac{p_{11}}{p_{y_{0}}}\\\
0&0&1&\frac{p_{x}}{1-p_{x}}&a\\\ 0&0&0&0&b\end{bmatrix}$

Where $a$ is:

$\displaystyle a$
$\displaystyle=\frac{p_{10}(1-p_{x})+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{y_{1}}(1-p_{x})}$

And $b$ is

$\displaystyle b$
$\displaystyle=\frac{-p_{10}(1-p_{x})-p_{11}p_{x}+p^{\prime}_{10}p_{y_{0}}+p^{\prime}_{11}p_{y_{1}}}{p_{y_{1}}}$

This proves that the $A|b$ for $N=1$ satisfies $P(1)$, proving the base case.

Induction Step: Next, we prove that if $P(N-1)$ holds, then $P(N)$ holds as
well. For $P(N)$, $A|b$ will look like

$\displaystyle\begin{bmatrix}p_{y_{0}}&0&p_{y_{1}}&0&\dots&p_{y_{N-1}}&0&y_{N}&0&p_{10}\\\
0&p_{y_{0}}&0&p_{y_{1}}&\dots&0&p_{y_{N-1}}&0&p_{y_{N}}&p_{11}\\\
1-p_{x}&p_{x}&0&0&\dots&0&0&0&0&p^{\prime}_{10}\\\
0&0&1-p_{x}&p_{x}&\dots&0&0&0&0&p^{\prime}_{11}\\\
\vdots&\ddots&&&&&&&&\vdots\\\
0&0&0&0&\dots&1-p_{x}&p_{x}&0&0&p^{\prime}_{1(N-1)}\\\
0&0&0&0&\dots&0&0&1-p_{x}&p_{x}&p^{\prime}_{1N}\\\ \end{bmatrix}$

Now, since we assume $P(N-1)$ holds, the submatrix of $A|b$ corresponding to
$P(N-1)$ can be put into the assumed RREF form. However, since we added two
extra columns to $A\mid b$ the $P(N)$ compared to $a\mid b$ for $P(N-1)$, all
of the row operations performed on the submatrix corresponding to $P(N-1)$
must be performed on these added columns as well. None of these row operations
apply to the final row, since it is newly added and therefore not touched by
RREF computations for $P(N-1)$.

The row operations must be applied to the newly added columns, and we
calculate these now. We use $c_{N}$ to denote the matrix of the newly added
columns, and track the results on $c_{N}$ of the row operations applied to
$P(N-1)$.
Applying the row operations in 1 to $c_{N}$

$\displaystyle c_{N}=\begin{bmatrix}\frac{y_{N}}{y_{0}}&0\\\ 0&y_{N}\\\
-\frac{(1-x)y_{N}}{y_{0}}&0\\\ 0&0\\\ \vdots\\\ 1-x&x\\\ \end{bmatrix}$

Next, applying the operations in 2 to $c_{N}$

$\displaystyle c_{N}=\begin{bmatrix}\frac{y_{N}}{y_{0}}&0\\\
0&\frac{y_{N}}{y_{0}}\\\ -\frac{(1-x)y_{N}}{y_{0}}&-\frac{xy_{N}}{y_{0}}\\\
0&0\\\ \vdots\\\ 1-x&x\\\ \end{bmatrix}$

Next, applying the operations in 3 to $c_{N}$

$\displaystyle c_{N}=\begin{bmatrix}0&-\frac{xy_{N}}{(1-x)y_{0}}\\\
0&\frac{y_{N}}{y_{0}}\\\ \frac{y_{N}}{y_{1}}&\frac{xy_{N}}{(1-x)y_{1}}\\\
-\frac{y_{N}(1-x)}{y_{1}}&-\frac{xy_{N}}{y_{1}}\\\ \vdots\\\ 1-x&x\\\
\end{bmatrix}$

Next, applying the operations in 4 to $c_{N}$ for $i=2$, we get

$\displaystyle c_{N}=\begin{bmatrix}0&-\frac{xy_{N}}{(1-x)y_{0}}\\\
0&\frac{y_{N}}{y_{0}}\\\ 0&0\\\
\frac{y_{N}}{y_{2}}&\frac{xy_{N}}{(1-x)y_{2}}\\\
-\frac{(1-x)y_{N}}{y_{2}}&-\frac{xy_{N}}{y_{2}}\\\ 0&0\\\ \vdots\\\ 1-x&x\\\
\end{bmatrix}$

As we repeat the row operations in 4 for $i\in\\{3,\dots,N-1\\}$, $c_{N}$ will
ultimately become

$\displaystyle c_{N}=\begin{bmatrix}0&-\frac{xy_{N}}{(1-x)y_{0}}\\\
0&\frac{y_{N}}{y_{0}}\\\ 0&0\\\ 0&0\\\ \vdots\\\ 0&0\\\
\frac{y_{N}}{y_{N-1}}&\frac{xy_{N}}{y_{N-1}(1-x)}\\\
-\frac{(1-x)y_{N}}{y_{N-1}}&-\frac{xy_{N}}{y_{N-1}}\\\ 1-x&x\\\ \end{bmatrix}$

Consequently, the matrix $A\mid b$ corresponding to $P(N)$ will contain a
submatrix corresponding to the RREF in $P(N-1)$, with the resulting $c_{N}$
and extra row appended. Formally, it will look like the matrix presented
below.

$\displaystyle\begin{bmatrix}[ccccccccc|c]1&0&0&-\frac{p_{x}p_{y_{1}}}{(1-p_{x})p_{y_{0}}}&\dots&0&-\frac{p_{x}p_{y_{N-1}}}{(1-p_{x})p_{y_{0}}}&0&-\frac{p_{x}p_{y_{N}}}{(1-p_{x})p_{y_{0}}}&\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}\\\
0&1&0&\frac{p_{y_{1}}}{p_{y_{0}}}&\dots&0&\frac{p_{y_{N-1}}}{p_{y_{0}}}&0&\frac{p_{y_{N}}}{p_{y_{0}}}&\frac{p_{11}}{p_{y_{0}}}\\\
0&0&1&\frac{p_{x}}{1-p_{x}}&\dots&0&0&0&0&\frac{p^{\prime}_{11}}{1-p_{x}}\\\
\vdots&&&&&&&\ddots&&\vdots\\\
0&0&0&0&\dots&1&\frac{p_{x}}{1-p_{x}}&\frac{p_{y_{N}}}{p_{y_{N-1}}}&\frac{p_{x}p_{y_{N}}}{p_{y_{N-1}}(1-p_{x})}&\frac{p_{10}(1-p_{x})+p_{11}p_{x}-\sum_{i=0}^{N-2}p^{\prime}_{1i}y_{i}}{y_{N-1}(1-x)}\\\
0&0&0&0&\dots&0&0&-\frac{(1-x)y_{N}}{y_{N-1}}&-\frac{xy_{N}}{y_{N-1}}&\frac{\sum_{i=0}^{N-1}p^{\prime}_{1i}y_{i}-p_{10}(1-x)-p_{11}x}{y_{N-1}}\\\
0&0&0&0&\dots&0&0&1-x&x&p^{\prime}_{1N}\end{bmatrix}$ (53)

This matrix is not in RREF yet, so we perform the following row operations to
put the matrix in RREF

$\displaystyle
R_{N+2}=\frac{R_{N+2}}{-\frac{(1-p_{x})p_{y_{N}}}{p_{y_{N-1}}}}$
$\displaystyle R_{N+1}=R_{N+1}-\frac{p_{y_{N}}}{p_{y_{N-1}}}R_{N+2}$
$\displaystyle R_{N+3}=R_{N+3}-(1-p_{x})R_{N+2}$

Resulting in the following matrix:

$\displaystyle\begin{bmatrix}[ccccccccc|c]1&0&0&-\frac{p_{x}p_{y_{1}}}{(1-p_{x})p_{y_{0}}}&\dots&0&-\frac{p_{x}p_{y_{N-1}}}{(1-p_{x})p_{y_{0}}}&0&-\frac{[_{x}p_{y_{N}}}{(1-p_{x})p_{y_{0}}}&\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}\\\
0&1&0&\frac{p_{y_{1}}}{p_{y_{0}}}&\dots&0&\frac{p_{y_{N-1}}}{p_{y_{0}}}&0&\frac{p_{y_{N}}}{p_{y_{0}}}&\frac{p_{11}}{p_{y_{0}}}\\\
0&0&1&\frac{p_{x}}{1-p_{x}}&\dots&0&0&0&0&\frac{p^{\prime}_{11}}{1-p_{x}}\\\
\vdots&&&&&&&\ddots&&\vdots\\\
0&0&0&0&\dots&1&\frac{p_{x}}{1-p_{x}}&0&0&\frac{p^{\prime}_{1(N-1)}}{1-p_{x}}\\\
0&0&0&0&\dots&0&0&1&\frac{p_{x}}{1-p_{x}}&\frac{p_{10}(1-p_{x})+p_{11}p_{x}-\sum_{i=0}^{N-1}p^{\prime}_{1i}p_{y_{i}}}{p_{y_{N}}(1-p_{x})}\\\
0&0&0&0&\dots&0&0&0&0&p^{\prime}_{1N}-\frac{p_{10}(1-p_{x})+p_{11}p_{x}-\sum_{i=0}^{N-1}p^{\prime}_{1i}p_{y_{i}}}{p_{y_{N}}}\end{bmatrix}$
(54)

And by comparison, this matrix is equal to the matrix stated in our
proposition. So, if $P(N-1)$, then $P(N)$ holds, and this concludes the
induction proof.

Finally, since $P(Z,X)$ and $P(Z,Y)$ are marginalized distributions obtained
from marginalizing out $Y$ and $X$ from $P(Z,X,Y)$ respectively, they must
agree on $P(Z)$. This gives the identity

$p_{11}x+p_{10}(1-x)-\sum_{i=0}^{N}p^{\prime}_{1i}y_{i}=0$

And substituting this identity into the RREF form of $A|b$, we obtain

$\displaystyle\begin{bmatrix}[ccccccccc|c]1&0&0&-\frac{p_{x}p_{y_{1}}}{(1-p_{x})p_{y_{0}}}&\dots&0&-\frac{p_{x}p_{y_{N-1}}}{(1-p_{x})p_{y_{0}}}&0&-\frac{p_{x}p_{y_{N}}}{(1-p_{x})p_{y_{0}}}&\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}\\\
0&1&0&\frac{p_{y_{1}}}{p_{y_{0}}}&\dots&0&\frac{p_{y_{N-1}}}{p_{y_{0}}}&0&\frac{p_{y_{N}}}{p_{y_{0}}}&\frac{p_{11}}{p_{y_{0}}}\\\
0&0&1&\frac{p_{x}}{1-p_{x}}&\dots&0&0&0&0&\frac{p^{\prime}_{11}}{1-p_{x}}\\\
\vdots&&&&&&&\ddots&&\vdots\\\
0&0&0&0&\dots&1&\frac{p_{x}}{1-p_{x}}&0&0&\frac{p^{\prime}_{1(N-1)}}{1-p_{x}}\\\
0&0&0&0&\dots&0&0&1&\frac{p_{x}}{1-p_{x}}&\frac{p^{\prime}_{1N}}{1-p_{x}}\\\
0&0&0&0&\dots&0&0&0&0&0\end{bmatrix}$ (55)

Expressing this matrix in the form of its corresponding equations completes
the proof for this Lemma.

Proof of Lemma 2: Using the result presented in Lemma 1, when $Y$ has support
$\\{0,\dots,N\\}$ and we are given marginals $P(Z,X)$ and $P(Z,Y)$, we can
write the system of equations using free parameters as

$\displaystyle\mathbb{P}(Z=1\mid X=0,Y=0)$
$\displaystyle=\frac{x}{1-x}\sum_{n=1}^{N}\frac{y_{n}}{y_{0}}\mathbb{P}(Z=1\mid
X=1,Y=n)+\frac{p^{\prime}_{10}y_{0}-p_{11}x}{(1-x)y_{0}}$
$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0)$
$\displaystyle=\frac{p_{11}}{y_{0}}-\sum_{n=1}^{N}\frac{y_{n}}{y_{0}}\mathbb{P}(Z=1\mid
X=1,Y=n)$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=1)$
$\displaystyle=\frac{p^{\prime}_{11}}{1-x}-\frac{x}{1-x}\mathbb{P}(Z=1\mid
X=1,Y=1)$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=2)$
$\displaystyle=\frac{p^{\prime}_{12}}{1-x}-\frac{x}{1-x}\mathbb{P}(Z=1\mid
X=1,Y=2)$ $\displaystyle\vdots$ $\displaystyle\mathbb{P}(Z=1\mid X=0,Y=N)$
$\displaystyle=\frac{p^{\prime}_{1N}}{1-x}-\frac{x}{1-x}\mathbb{P}(Z=1\mid
X=1,Y=N)$

Now, each of the basic variables in the system above must be a valid
probability, i.e. between zero and one, inclusive. Employing these constraints
on the free parameters gives

$\displaystyle 0\leq P(Z=1\mid X=0,Y=0)\leq 1$ $\displaystyle\implies
0\leq\frac{x}{1-x}\sum_{n=1}^{N}\frac{y_{n}}{y_{0}}\mathbb{P}(Z=1\mid
X=1,Y=n)+\frac{p^{\prime}_{10}y_{0}-p_{11}x}{(1-x)y_{0}}\leq 1$

Solving for the lower bound first, we have

$\displaystyle
0\leq\frac{x}{1-x}\sum_{n=1}^{N}\frac{y_{n}}{y_{0}}\mathbb{P}(Z=1\mid
X=1,Y=n)+\frac{p^{\prime}_{10}y_{0}-p_{11}x}{(1-x)y_{0}}$
$\displaystyle\implies\frac{p_{11}x-p^{\prime}_{10}y_{0}}{x}\leq\sum_{n=1}^{N}P(Z=1\mid
X=1,Y=n)$

Next, with the upper bound

$\displaystyle\frac{x}{1-x}\sum_{n=1}^{N}\frac{y_{n}}{y_{0}}\mathbb{P}(Z=1\mid
X=1,Y=n)+\frac{p^{\prime}_{10}y_{0}-p_{11}x}{(1-x)y_{0}}\leq 1$
$\displaystyle\implies x\sum_{n=1}^{N}y_{n}\mathbb{P}(Z=1\mid
X=1,Y=n)+p^{\prime}_{10}y_{0}-p_{11}x\leq(1-x)y_{0}$
$\displaystyle\implies\sum_{n=1}^{N}y_{n}\mathbb{P}(Z=1\mid
X=1,Y=n)\leq\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}$

Following a similar calculation for $P(Z=1\mid X=1,Y=0)$, we have

$\displaystyle p_{11}-y_{0}\leq\sum_{n=1}^{N}y_{n}\mathbb{P}(Z=1\mid
X=1,Y=n)\leq p_{11}$

Since all of the bounds need to hold simultaneously, we can re-express them
using using maximum and minimum operators as

$\displaystyle\max\begin{bmatrix}\frac{p_{11}x-p^{\prime}_{10}y_{0}}{x}\\\
p_{11}-y_{0}\end{bmatrix}\leq\sum_{n=1}^{N}y_{n}\mathbb{P}(Z=1\mid
X=1,Y=n)\leq\min\begin{bmatrix}\frac{(1-x)y_{0}+p_{11}x-p^{\prime}_{10}y_{0}}{x}\\\
p_{11}\end{bmatrix}$

Next, for $i\in\\{1,\dots,N\\}$, we have the following constrain on the basic
variables $P(Z=1\mid X=0,Y=i)$

$\displaystyle 0\leq P(Z=1\mid X=0,Y=i)\leq 1$ $\displaystyle
0\leq\frac{p^{\prime}_{11}}{1-x}-\frac{x}{1-x}\mathbb{P}(Z=1\mid X=1,Y=1)\leq
1$ $\displaystyle\implies\frac{p^{\prime}_{1i}-(1-x)}{x}\leq P(Z=1\mid
X=1,Y=i)\leq\frac{p^{\prime}_{1i}}{x}$

And since the free parameters are probabilities themselves, they must be
between $0$ and $1$ and hence the bounds for $P(Z=1\mid X=1,Y=i)$ become

$\displaystyle\max\begin{bmatrix}0\\\
\frac{p^{\prime}_{1i}-(1-x)}{x}\end{bmatrix}\leq P(Z=1\mid
X=1,Y=i)\leq\min\begin{bmatrix}1\\\ \frac{p^{\prime}_{1i}}{x}\end{bmatrix}$

######  Lemma 53.

Given $P(Z,X)$ and $P(Z,Y)$, using the solution to the system of equations in
Lemma 1, each of the terms in $\Delta$ and $\Gamma$ defined in Lemma 5 are
expressed in terms of the free parameters below. First, for $\Gamma$, each of
the terms can be written as

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)$
$\displaystyle=\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$

And for the terms in $\Gamma$ corresponding to $Y=i$, $i\in\\{1,\dots,N\\}$

$\displaystyle P(Z=1\mid X=1,Y=i)-P(Z=0\mid X=0,Y=i)$ $\displaystyle=P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$

Similarly, the terms in $\Delta$ can be expressed in terms of the free
parameter as

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=1\mid X=0,Y=0)$
$\displaystyle=\frac{p_{11}-p^{\prime}_{10}p_{y_{0}}-\sum_{n=1}^{N}p_{y_{n}}\mathbb{P}(Z=1\mid
X=1,Y=n)}{(1-p_{x})p_{y_{0}}}$

And for the terms in $\Delta$ corresponding to $Y=i$, $i\in\\{1,\dots,N\\}$

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=1)-\mathbb{P}(Z=1\mid X=0,Y=1)$
$\displaystyle=\frac{\mathbb{P}(Z=1\mid X=1,Y=i)-p^{\prime}_{1i}}{1-p_{x}}$

###### Proof.

Using the system of equations obtained in Lemma 1, each term in $\Gamma$ can
be expressed using these free parameters. Starting with
$\max\\{0,\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}$. First,
expressing each of these terms using the free parameters, we get

$\displaystyle P(Z=1\mid X=1,Y=0)$
$\displaystyle=\frac{p_{11}}{p_{y_{0}}}-\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n)$ $\displaystyle P(Z=0\mid X=0,Y=0)$
$\displaystyle=1-\Bigg{(}\frac{p_{x}}{1-p_{x}}\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n)+\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}\Bigg{)}$

Subtracting these two,

$\displaystyle=\frac{p_{11}}{p_{y_{0}}}-\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n)-1$
$\displaystyle+\frac{p_{x}}{1-p_{x}}\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n)+\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}$
$\displaystyle=\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}+\frac{p_{11}}{p_{y_{0}}}-1+\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}P(Z=1\mid
X=1,Y=n)\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$
$\displaystyle=\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}+p_{11}(1-p_{x})-(1-p_{x})p_{y_{0}}}{(1-p_{x})p_{y_{0}}}+\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}P(Z=1\mid
X=1,Y=n)\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$
$\displaystyle=\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{p_{11}}{p_{y_{0}}}\Big{(}1-\frac{p_{x}}{1-p_{x}}\Big{)}+\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}P(Z=1\mid
X=1,Y=n)\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$
$\displaystyle=\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$

Moving on to $\max\\{0,P(Z=1\mid X=1,Y=i)-P(Z=0\mid X=0,Y=i)\\}$, the
probability $P(Z=0\mid X=0,Y=i)$ for $i\in\\{1,\dots,N\\}$ can be expressed in
terms of the free parameters as

$\displaystyle P(Z=0\mid
X=0,Y=i)=1-\Bigg{(}\frac{p^{\prime}_{1i}}{1-p_{x}}-\frac{p_{x}}{1-p_{x}}\mathbb{P}(Z=1\mid
X=1,Y=i)\Bigg{)}$ $\displaystyle\implies P(Z=1\mid X=1,Y=i)-P(Z=0\mid
X=0,Y=i)$ $\displaystyle=P(Z=1\mid
X=1,Y=i)-1+\frac{p^{\prime}_{1i}}{1-p_{x}}-\frac{p_{x}}{1-p_{x}}\mathbb{P}(Z=1\mid
X=1,Y=i)$ $\displaystyle=P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$

This concludes the proof for the terms in $\Gamma$. Following a similar
approach for the terms in $\Delta$, first consider

$\displaystyle\mathbb{P}(Z=1\mid X=1,Y=0)-\mathbb{P}(Z=1\mid X=0,Y=0)$
$\displaystyle=\frac{p_{11}}{p_{y_{0}}}-\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n)-\Bigg{(}\frac{p_{x}}{1-p_{x}}\sum_{n=1}^{N}\frac{p_{y_{n}}}{p_{y_{0}}}\mathbb{P}(Z=1\mid
X=1,Y=n)$
$\displaystyle+\frac{p^{\prime}_{10}p_{y_{0}}-p_{11}p_{x}}{(1-p_{x})p_{y_{0}}}\Bigg{)}$
$\displaystyle=\frac{p_{11}-p^{\prime}_{10}p_{y_{0}}-\sum_{n=1}^{N}p_{y_{n}}\mathbb{P}(Z=1\mid
X=1,Y=n)}{(1-p_{x})p_{y_{0}}}$

And for the terms of the form $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=1\mid X=0,Y=i)\\}$ for $i\in\\{1,\dots,N\\}$

$\displaystyle\mathbb{P}(Z=1\mid
X=0,Y=i)=\frac{p^{\prime}_{1i}}{1-p_{x}}-\frac{p_{x}}{1-p_{x}}\mathbb{P}(Z=1\mid
X=1,Y=i)$ $\displaystyle\implies\mathbb{P}(Z=1\mid X=1,Y=i)-\mathbb{P}(Z=1\mid
X=0,Y=i)=$ $\displaystyle\mathbb{P}(Z=1\mid
X=1,Y=i)-\frac{p^{\prime}_{1i}}{1-p_{x}}+\frac{p_{x}}{1-p_{x}}\mathbb{P}(Z=1\mid
X=1,Y=i)$ $\displaystyle=\frac{\mathbb{P}(Z=1\mid
X=1,Y=i)-p^{\prime}_{1i}}{1-p_{x}}$

This concludes the proof of the Lemma. ∎

######  Lemma 54.

The following implications hold:

$p^{\prime}_{10}<p_{x}\implies\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}>p_{11}-p_{y_{0}}$
$p^{\prime}_{10}\geq
p_{x}\implies\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq
p_{11}-p_{y_{0}}$ $p^{\prime}_{10}<1-p_{x}\implies
p_{11}<\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$
$p^{\prime}_{10}\geq 1-p_{x}\implies
p_{11}\geq\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$

###### Proof.

Each of these is proved using a proof by contra-positive. Starting with
$p^{\prime}_{10}<p_{x}\implies\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}>p_{11}-p_{y_{0}}$,
the contra-positive of this statement is

$\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq
p_{11}-p_{y_{0}}\implies p^{\prime}_{10}\geq p_{x}$

To see this holds, note that

$\displaystyle\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq
p_{11}-p_{y_{0}}$
$\displaystyle\implies-\frac{p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq-p_{y_{0}}$
$\displaystyle\implies p^{\prime}_{10}\leq p_{x}$

This proves
$p^{\prime}_{10}<p_{x}\implies\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}>p_{11}-p_{y_{0}}$.
Next, for $p^{\prime}_{10}\geq
p_{x}\implies\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq
p_{11}-p_{y_{0}}$, following a similar proof strategy, the contra-positive can
be written as

$\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}>p_{11}-p_{y_{0}}\implies
p^{\prime}_{10}<p_{x}$

To see this holds, note that

$\displaystyle\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}>p_{11}-p_{y_{0}}$
$\displaystyle\implies-\frac{p^{\prime}_{10}p_{y_{0}}}{p_{x}}>-p_{y_{0}}$
$\displaystyle\implies p^{\prime}_{10}<p_{x}$

This proves $p^{\prime}_{10}\geq
p_{x}\implies\frac{p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\leq
p_{11}-p_{y_{0}}$.
Next, for $p^{\prime}_{10}<1-p_{x}\implies
p_{11}<\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$,
the contra-positive is written as

$p_{11}\geq\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\implies
p^{\prime}_{10}\geq 1-p_{x}$

To see this holds, note that

$\displaystyle
p_{11}\geq\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$
$\displaystyle\implies 0\geq(1-p_{x})p_{y_{0}}-p^{\prime}_{10}p_{y_{0}}$
$\displaystyle\implies p^{\prime}_{10}\geq 1-p_{x}$

This proves $p^{\prime}_{10}<1-p_{x}\implies
p_{11}<\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$.
Next, for $p^{\prime}_{10}\geq 1-p_{x}\implies
p_{11}\geq\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$
the contra-positive is written as

$p_{11}<\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}\implies
p^{\prime}_{10}<1-p_{x}$

To see this holds, note that

$\displaystyle
p_{11}<\frac{(1-p_{x})p_{y_{0}}+p_{11}p_{x}-p^{\prime}_{10}p_{y_{0}}}{p_{x}}$
$\displaystyle\implies 0<(1-p_{x})p_{y_{0}}-p^{\prime}_{10}p_{y_{0}}$
$\displaystyle\implies p^{\prime}_{10}<1-p_{x}$

This concludes the proof. ∎

######  Lemma 55.

For $i\in\\{1,\dots,N\\}$, when
$p^{\prime}_{1i}>1-p_{x}\implies\frac{p^{\prime}_{11}-(1-p_{x})}{p_{x}}>0$.
When $p^{\prime}_{1i}<p_{x}\implies\frac{p^{\prime}_{11}}{p_{x}}<1$

###### Proof.

The proof follows from properties of probability. ∎

######  Lemma 56.

Assume $p_{x}>1-p_{x}$. The function $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}\geq 0$ when

$\displaystyle\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)\geq\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$

###### Proof.

From the result of Lemma LABEL:, $\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)$ can be expressed in terms of the free
parameter as

$\displaystyle\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$

Now, we use a proof by contra-positive to first show that

$\displaystyle\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}<0$
$\displaystyle\implies\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$

To see this, note that

$\displaystyle\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}<0$
$\displaystyle\implies
p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{p_{y_{0}}(1-p_{x})}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}-(1-p_{x})}{1-p_{x}}\Bigg{)}<0$
$\displaystyle\implies
p_{y_{0}}(p^{\prime}_{10}-(1-p_{x}))+(\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11})\Bigg{(}p_{x}-(1-p_{x})\Bigg{)}<0$
$\displaystyle\implies\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$

This concludes the proof. ∎

######  Lemma 57.

Assume $p_{x}>1-p_{x}$. The function $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}\geq 0$ for $i\in\\{1,\dots,N\\}$ when

$\displaystyle P(Z=1\mid
X=1,Y=i)\leq\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

###### Proof.

From the result of Lemma LABEL:, $\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}$ can be expressed in terms of the free
parameter as

$P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$

Following a proof by contra-positive, we write the contra-positive as

$\displaystyle P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}<0$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)>\frac{p^{\prime}_{1i}-(1-p_{x})}{p_{x}-(1-p_{x})}$

To see this, note that

$\displaystyle P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}<0$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)\Bigg{(}\frac{(1-p_{x})-p_{x}}{1-p_{x}}\Bigg{)}<\frac{(1-p_{x})-p^{\prime}_{11}}{1-p_{x}}$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)\Bigg{(}(1-p_{x})-p_{x}\Bigg{)}<(1-p_{x})-p^{\prime}_{11}$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)>\frac{p^{\prime}_{11}-(1-p_{x})}{p_{x}-(1-p_{x})}$

This concludes the proof. ∎

######  Lemma 58.

Assume $p_{x}<1-p_{x}$. The function $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)\\}\geq 0$ when

$\displaystyle\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)\leq\frac{p_{y_{0}}(p^{\prime}_{10}-(1-p_{x}))}{(1-p_{x})-p_{x}}+p_{11}$

###### Proof.

From the result of Lemma LABEL:, $\mathbb{P}(Z=1\mid
X=1,Y=0)-\mathbb{P}(Z=0\mid X=0,Y=0)$ can be expressed in terms of the free
parameter as

$\displaystyle\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}$

Following a proof by contra-positive, we write the contra-positive as

$\displaystyle\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}<0$
$\displaystyle\implies\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)>\frac{p_{y_{0}}(p^{\prime}_{10}-(1-p_{x}))}{(1-p_{x})-p_{x}}+p_{11}$

To see this, note that

$\displaystyle\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{p_{x}}{1-p_{x}}-1\Bigg{)}<0$
$\displaystyle\implies-\frac{p^{\prime}_{10}-(1-p_{x})}{1-p_{x}}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}>0$
$\displaystyle\implies-
p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{p_{y_{0}}(1-p_{x})}+\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{(1-p_{x})-p_{x}}{1-p_{x}}\Bigg{)}>0$
$\displaystyle\implies\frac{\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)-p_{11}}{p_{y_{0}}}\Bigg{(}\frac{(1-p_{x})-p_{x}}{1-p_{x}}\Bigg{)}>p_{y_{0}}\frac{p^{\prime}_{10}-(1-p_{x})}{p_{y_{0}}(1-p_{x})}$
$\displaystyle\implies\sum_{n=1}^{N}p_{y_{n}}P(Z=1\mid
X=1,Y=n)>\frac{p_{y_{0}}(p^{\prime}_{10}-(1-p_{x}))}{(1-p_{x})-p_{x}}+p_{11}$

This concludes the proof. ∎

######  Lemma 59.

Assume $p_{x}<1-p_{x}$. The functions $\max\\{0,\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}\geq 0$ for $i\in\\{1,\dots,N\\}$ when

$\displaystyle P(Z=1\mid
X=1,Y=i)\geq\frac{(1-p_{x})-p^{\prime}_{1i}}{(1-p_{x})-p_{x}}$

###### Proof.

From the result of Lemma LABEL:, $\mathbb{P}(Z=1\mid
X=1,Y=i)-\mathbb{P}(Z=0\mid X=0,Y=i)\\}$ can be expressed in terms of the free
parameter as

$P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}$

Following a proof by contra-positive, we can write the contra-positive as

$\displaystyle P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}<0$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)<\frac{(1-p_{x})-p^{\prime}_{1i}}{(1-p_{x})-p_{x}}$

To see this, note that

$\displaystyle P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}+\frac{p^{\prime}_{11}-(1-p_{x})}{1-p_{x}}<0$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)\Bigg{(}1-\frac{p_{x}}{1-p_{x}}\Bigg{)}<\frac{(1-p_{x})-p^{\prime}_{11}}{1-p_{x}}$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)\Bigg{(}\frac{(1-p_{x})-p_{x}}{1-p_{x}}\Bigg{)}<\frac{(1-p_{x})-p^{\prime}_{11}}{1-p_{x}}$
$\displaystyle\implies P(Z=1\mid
X=1,Y=i)<\frac{(1-p_{x})-p^{\prime}_{11}}{(1-p_{x})-p_{x}}$

This concludes the proof. ∎

######  Lemma 60.

Assume $p_{x}>1-p_{x}$. If $p^{\prime}_{10}\geq p_{x}$, then

$p_{11}-y_{0}\geq\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}$

###### Proof.

Following a proof by contra-positive, the contra-positive is given as

$\displaystyle
p_{11}-y_{0}<\frac{p_{y_{0}}((1-p_{x})-p^{\prime}_{10})}{p_{x}-(1-p_{x})}+p_{11}\implies