# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## Appendix D Proofs of Results about Refinement Comparison
 \tag{121}\]  
Recalling that  
\[TG^{\varepsilon}\sqsubseteq^{\rm avg}TG^{\varepsilon^{\prime}}\text{ iff }TG^{ \varepsilon^{\prime}}=TG^{\varepsilon}R \tag{122}\]  
for some channel \(R\), we can construct a suitable \(R\) using \((TG^{\varepsilon})^{-1}\), namely \(R=(TG^{\varepsilon})^{-1}\cdot TG^{\varepsilon^{\prime}}\). It suffices to show that \(R\) is a valid channel. It is clear that the rows of \(R\) sum to 1, since it is the product of matrices with rows summing to 1. Multiplying out the matrix \(R\) yields:  
\[ \begin{array}{|c|cccc|}\hline R&x_{1}&x_{2}&x_{3}&\ldots\\ \hline x_{1}&\frac{1-\alpha\beta}{(1-\alpha)(1+\beta)}&\frac{(\beta-\alpha)(1- \beta)}{(1-\alpha)(1+\beta)}&\frac{\beta(\beta-\alpha)(1-\beta)}{(1-\alpha)( 1+\beta)}&\ldots\\ x_{2}&\frac{(1-\alpha\beta)(\beta-\alpha)}{(1-\alpha)^{2}(1+\beta)}&\frac{(1- 2\alpha\beta+2^{2})(1-\beta)}{(1-\alpha)^{2}(1+\beta)}&\frac{(1-\alpha\beta)( 1-\beta)(\beta-\alpha)}{(1-\alpha)^{2}(1-\beta)}&\ldots\\ x_{3}&\frac{\beta(1-\alpha\beta)(\beta-\alpha)}{(1-\alpha)^{2}(1-\beta)}&\frac{ (1-\alpha\beta)(1-\beta)(\beta-\alpha)}{(1-\alpha)^{2}(1-\beta)}&\frac{(1-2 \alpha\beta+\alpha^{2})(1-\beta)}{(1-\alpha)^{2}(1+\beta)}&\ldots\\ \ldots&\ldots&\ldots&\ldots&\ldots\\ \hline\end{array}  \tag{123}\]  
where \(\alpha=e^{-\varepsilon}\) and \(\beta=e^{-\varepsilon^{\prime}}\). The only way that any of these matrix entries can be less than 0 is if \(\alpha>\beta\), or \(\varepsilon<\varepsilon^{\prime}\). Thus, \(R\) is a valid channel precisely when \(\varepsilon\geq\varepsilon^{\prime}\) and so \(TG^{\varepsilon}\sqsubseteq^{\rm avg}TG^{\varepsilon^{\prime}}\) as required. The following theorems now follow from the previous lemmas. **Theorem A9**. : _Let \(G^{\varepsilon},G^{\varepsilon^{\prime}}\) be geometric mechanisms. Then, \(G^{\varepsilon}\sqsubseteq^{\rm avg}G^{\varepsilon^{\prime}}\) iff \(\varepsilon\geq\varepsilon^{\prime}\). That is, decreasing \(\varepsilon\) produces a refinement of the mechanism._  
**Proof. ** Using Lemma A1, we can express \(G^{\varepsilon}\) as a square channel and from Lemma A3 it follows that the refinement holds. **Theorem A10**. : _Let \(TG^{\varepsilon},TG^{\varepsilon^{\prime}}\) be truncated geometric mechanisms. Then, \(TG^{\varepsilon}\sqsubseteq^{\mathrm{avg}}TG^{\varepsilon^{\prime}}\) iff \(\varepsilon\geq\varepsilon^{\prime}\). That is, decreasing \(\varepsilon\) produces a refinement of the mechanism._  
**Proof. ** As above, using Lemmas A2 and A3. **Theorem A11**. : _Let \(OTG^{\varepsilon},OTG^{\varepsilon^{\prime}}\) be over-truncated geometric mechanisms. Then, \(OTG^{\varepsilon}\
ot\sqsubseteq^{\mathrm{avg}}OTG^{\varepsilon^{\prime}}\) for any \(\varepsilon\
eq\varepsilon^{\prime}\). That is, decreasing \(\varepsilon\) does **not** produce a refinement._  
**Proof. ** Consider the following counter-example:  
\[ \begin{array}{|c|cc|}\hline A^{\varepsilon}&x_{1}&x_{2}\\ \hline x_{1}&4/5&1/5\\ x_{2}&1/5&4/5\\ x_{3}&1/20&19/20\\ \hline\end{array} \quad \begin{array}{|c|cc|}\hline B^{\varepsilon^{\prime}}&x_{ 1}&x_{2}\\ \hline x_{1}&2/3&1/3\\ x_{2}&1/3&2/3\\ x_{3}&1/6&5/6\\ \hline\end{array} \] (A21)  
Channels \(A^{\varepsilon}\) and \(B^{\varepsilon^{\prime}}\) are over-truncated geometric mechanisms parametrized by \(\varepsilon=2\log 2\), \(\varepsilon^{\prime}=\log 2\), respectively. We expect \(B^{\varepsilon^{\prime}}\) to be safer than \(A^{\varepsilon}\), that is, \(V_{\mathrm{G}}[\pi^{u},B^{\varepsilon^{\prime}}]<V_{\mathrm{G}}[\pi^{u},A^{ \varepsilon}]\). However, under the uniform prior \(\pi^{u}\), the gain function  
\[ \begin{array}{|c|cc|}\hline G&w_{1}&w_{2}\\ \hline x_{1}&1/5&0\\ x_{2}&0&1\\ x_{3}&4/5&0\\ \hline\end{array} \] (A22)  
yields \(V_{\mathrm{G}}[\pi^{u},A^{\varepsilon}]=0.33\) and \(V_{\mathrm{G}}[\pi^{u},B^{\varepsilon^{\prime}}]=0.36\), thus \(B^{\varepsilon^{\prime}}\) leaks more than \(A^{\varepsilon}\) for this adversary.