# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## Appendix D Proofs of Results about Refinement Comparison
(In fact, for this gain function, we have \(V_{\mathrm{G}}[\pi^{u},A^{\varepsilon}]=V_{\mathrm{G}}(\pi^{u})\) and so the adversary learns nothing from observing the output of \(A^{\varepsilon}\)). **Theorem A12**. : _Let \(OTG^{\varepsilon}\) be an over-truncated geometric mechanism. Then, reducing \(\varepsilon\) does **not** produce a \(\sqsubseteq^{\mathrm{max}}\) refinement; however, it **does** produce a \(\sqsubseteq^{\mathrm{prv}}\) refinement._  
**Proof. ** We show the first part using a counter-example. Consider the following channels:  
\[ \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} \] (A23)Channels \(A^{\varepsilon}\) and \(B^{\varepsilon^{\prime}}\) are over-truncated geometric mechanisms using \(\varepsilon=2\log 2\), \(\varepsilon^{\prime}=\log 2\), respectively. We can define the (prior) vulnerability \(V\) as the usual (convex) \(g\)-vulnerability. Then, under a uniform prior \(\pi^{u}\), the gain function given by:  
\[g(w,x_{1}) =\frac{1}{5} \tag{114}\] \[g(w,x_{2}) =-1\] (115) \[g(w,x_{3}) =\frac{4}{5} \tag{116}\]  
yields \(V^{\max}[\pi^{u},A]=0\) and \(V^{\max}[\pi^{u},B]=\frac{2}{55}\). Thus, \(A\
ot\subseteq^{\max}B\). For the second part, we first note that for any square geometric channel \(A^{\varepsilon}\) we have \(d_{A}(x,x^{\prime})=\varepsilon\) exactly when \(x,x^{\prime}\) are adjacent rows in the matrix (this can be seen from the construction of the square channel). Now, the over-truncated geometric is obtained by summing columns of the square geometric. By construction, the square geometric \(A\) has adjacent elements \(A_{x,y},A_{x^{\prime},y}\) satisfying \(\
icefrac{{A_{x,y}}}{{A_{x^{\prime},y}}}=e^{\varepsilon}\) when \(x>x^{\prime}\) and \(x\) is _above_ (or on) the diagonal of the channel matrix; otherwise, \(\
icefrac{{A_{x,y}}}{{A_{x^{\prime},y}}}=e^{-\varepsilon}\). This means that each (over)-truncation step maintains the \(\
icefrac{{A_{x,y}}}{{A_{x^{\prime},y}}}\) ratio except when \(x,y\) and \(x^{\prime},y^{\prime}\) occur on diagonal elements, in which case their sum is between \(e^{-\varepsilon}\) and \(e^{\varepsilon}\). Since this affects only two elements in each row, we still have that \(d_{A}(x,x^{\prime})=\varepsilon\) (until the final truncation step to produce a single 1 vector). Therefore, since \(\sqsubseteq^{\mathrm{prv}}\) holds for the square matrix, and it holds under truncation, we must have that it holds for over-truncated geometric mechanisms. Thus, reducing \(\varepsilon\) corresponds to refinement under \(\sqsubseteq^{\mathrm{prv}}\) as required. We show that the randomized response mechanism behaves well with respect to \(\sqsubseteq^{\mathrm{avg}}\) by considering three cases. Firstly, we consider the case where \(\mathcal{X}=\mathcal{Y}\). We use the following lemmas:  
**Lemma A4**. : _Let \(R^{\alpha}\), \(R^{\beta}\) be'square' randomized response mechanisms. Then, \(B=R^{\alpha}R^{\beta}\) is a randomized response mechanism with parameter \(\varepsilon=log\frac{e^{\alpha+\beta}+k}{e^{\alpha}+e^{\beta}+k-1}\) where \(k+1\) is the dimension of \(R^{\alpha}\), \(R^{\beta}\) and \(B\)._  
Proof. : Observe that \(R^{\alpha}\) can be factorised as \(\frac{1}{e^{\alpha}+k}R\) where \(R\) has the form:  
\[ \begin{array}{|c|cccc|}\hline R&x_{1}&x_{2}&\ldots&x_{k+1}\\ \hline x_{1}&e^{\alpha}&1&\ldots&1\\ x_{2}&1&e^{\alpha}&\ldots&1\\ x_{k+1}&1&1&\ldots&e^{\alpha}\\ \hline\end{array}  \tag{117}\]  
and similarly for \(R^{\beta}\). Multiplying out gives the matrix:  
\[ \begin{array}{|c|cccc|}\hline B&x_{1}&x_{2}&\ldots&x_{k+1}\\ \hline x_{1}&e^{\alpha+\beta}+k&e^{\alpha}+e^{\beta}+(k-1)&\ldots&e^{\alpha}+ e^{\beta}+(k-1)\\ x_{2}&e^{\alpha}+e^{\beta}+(k-1)&e^{\alpha+\beta}+k&\ldots&e^{\alpha}+e^{\beta}+(k-1) \\ x_{k+1}&e^{\alpha}+e^{\beta}+(k-1)&e^{\alpha}+e^{\beta}+(k-1)&\ldots&e^{\alpha+ \beta}+k\\ \hline\end{array}