1 files changed, 35 insertions, 0 deletions
diff --git a/ACSAC/proofs/proof_egd_eo.tex b/ACSAC/proofs/proof_egd_eo.tex
new file mode 100644
index 0000000..435add2
--- /dev/null
+++ b/ACSAC/proofs/proof_egd_eo.tex
@@ -0,0 +1,35 @@
+\begin{theorem}
+\label{th:eoo}
+If $\hat{Y}$ satisfies \eo for $Y$ and $S$ then the balanced accuracy of \aia in \ref{tm:hard} is $\frac{1}{2}$ iff $Y$ is independent of $S$ or $\hat{Y}$ is independent of $Y$.
+\end{theorem}
+
+\begin{proof}
+Let $\attackmodel$ be the attack model trained for AS: $\hat{S}=a\circ \hat{Y}$.
+By the total probability formula
+{\footnotesize
+\begin{align*}
+P(\hat{S}=0|S=0)=&P(\hat{S}=0|S=0Y=0)P(Y=0|S=0)\\
++&P(\hat{S}=0|S=0Y=1)P(Y=1|S=0)
+\end{align*}
+}
+and as well
+{\footnotesize
+\begin{align*}
+P(\hat{S}=1|S=1)=&P(\hat{S}=1|S=1Y=0)P(Y=0|S=1)\\
+        +&P(\hat{S}=1|S=1Y=1)P(Y=1|S=1)
+\end{align*}
+}
+Then we substitute those terms in the definition of the balanced accuracy of $\targetmodel$.
+{\footnotesize
+\begin{align*}
+        &\frac{P(\hat{S}=0|S=0)+P(\hat{S}=1|S=1)}{2}\\
+        =&\frac{1}{2}+\frac{1}{2}\left(P(Y=0|S=0)-P(Y=0|S=1)\right)\\
+        &\left(P(\hat{Y}\in \attackmodel^{-1}(\{1\})|S=1Y=0) -
+        P(\hat{Y}\in \attackmodel^{-1}(\{1\})|S=1Y=1)\right)
+\end{align*}
+}
+The balanced accuracy is equal to 0.5 if and only if $P(Y=0|S=0)=P(Y=0|S=1)$
+or $\forall \attackmodel~P(\hat{Y}\in \attackmodel^{-1}(\{1\})|S=1Y=0)=P(\hat{Y}\in \attackmodel^{-1}(\{1\})|S=1Y=1)$.
+The first term indicates that $Y$ is independent of $S$ and the second term indicates that $S=1$ the $\targetmodel$ random guess utility.
+We can do the same computing for $S=0$ and obtain a similar conclusion. 
+\end{proof}
+\ No newline at end of file