# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## Appendix D Proofs of Results about Refinement Comparison
: _Let \(R^{\varepsilon}\), \(R^{\varepsilon^{\prime}}\) be randomized response mechanisms with \(\mathcal{X}\subset\mathcal{Y}\). Then, \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\) iff \(\varepsilon\geq\varepsilon^{\prime}\)._  
Proof. : The channel matrix \(R^{\varepsilon}\) is equivalent to the square randomized response mechanism \(S^{\varepsilon}\) of dimension \(\|\mathcal{Y}\|\times\|\mathcal{Y}\|\) with the bottom \(\|\mathcal{Y}\|-\|\mathcal{X}\|\) rows removed (and similarly for \(R^{\varepsilon^{\prime}}\)). This meansany solution \(R\) for \(S^{\varepsilon}\) is a solution for \(R^{\varepsilon}\). Thus, for the reverse direction, if \(\varepsilon\geq\varepsilon^{\prime}\), we can always find an \(R\) such that \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\). For the forward direction, we prove the contrapositive. Note that in this case we cannot assume a partial order relation for \(\sqsubseteq^{\mathrm{avg}}\), since there may be columns of \(R^{\varepsilon}\) which are identical. If \(\varepsilon<\varepsilon^{\prime}\), we want to show that \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\). To do this, we need to find a gain function and prior \(\pi\) such that \(V_{g}(\pi,R^{\varepsilon})<V_{g}(\pi,R^{\varepsilon^{\prime}})\). The min-entropy leakage will do: this is simply the sum of the column maxima of the channel matrix. For the randomized response channels, this is given by  
\[V(R^{\varepsilon})=\frac{ae^{\varepsilon}+b}{e^{\varepsilon}+a+b-1}\] (A32)  
for a channel with dimensions \(a\times(a+b)\). This is an increasing function of \(\varepsilon\) (for \(a\geq 1\)), in fact the derivative is always positive for \(a>1\), hence we must have \(\varepsilon<\varepsilon^{\prime}\implies V(R^{\varepsilon})<V(R^{\varepsilon^{ \prime}})\). Thus, \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\). We can now conclude the following theorem from the main body of the paper:  
**Theorem A13**. : _Let \(R^{\varepsilon}\) be a randomized response mechanism. Then, decreasing \(\varepsilon\) in \(R\) produces a refinement. That is, \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\) iff \(\varepsilon\geq\varepsilon^{\prime}\)._  
Proof. : Follows from Lemmas A6-A8. **Theorem A14**. : _Let \(R\) be a randomized response mechanism, \(E\) an exponential mechanism and \(TG\) a truncated geometric mechanism. Then, \(TG^{\varepsilon}\sqsubseteq^{\mathrm{Prv}}R^{\varepsilon}\) and \(TG^{\varepsilon}\sqsubseteq^{\mathrm{Prv}}E^{\varepsilon}\). However, \(\sqsubseteq^{\mathrm{Prv}}\) does not hold between \(E^{\varepsilon}\) and \(R^{\varepsilon}\)._  
Proof. : We first show that \(TG^{\varepsilon}\sqsubseteq^{\mathrm{Prv}}R^{\varepsilon}\), which is equivalent to showing that \(d_{R}\leq d_{TG}\). For the geometric mechanism, we have \(d_{TG}(x,x^{\prime})=\varepsilon d(x,x^{\prime})\) for all \(x,x^{\prime}\in\mathcal{X}\). For the randomized response mechanism, we have \(d_{R}(x,x^{\prime})=\varepsilon\) or \(d_{R}(x,x^{\prime})=0\) (when \(x,x^{\prime}\
ot\in\mathcal{Y}\)). Thus, \(d_{R}\leq d_{TG}\) and so \(TG^{\varepsilon}\sqsubseteq^{\mathrm{Prv}}R^{\varepsilon}\). We now show \(TG^{\varepsilon}\sqsubseteq^{\mathrm{Prv}}E^{\varepsilon}\). Recall that we parametrize the exponential mechanism by the smallest possible \(\varepsilon\) such that it satisfies \(\varepsilon d\)-privacy. In this case, we find that, for any pair \(x,x^{\prime}\) we have \(d_{E}(x,x^{\prime})\leq\varepsilon d(x,x^{\prime})\), whereas, for the geometric mechanism, we have \(d_{TG}(x,x^{\prime})=\varepsilon d(x,x^{\prime})\). Therefore, \(d_{E}\leq d_{TG}\) and so \(TG^{\varepsilon}\sqsubseteq^{\mathrm{Prv}}E^{\varepsilon}\). The proof of \(\sqsubseteq^{\mathrm{Prv}}\) not holding between \(E^{\varepsilon}\) and \(R^{\varepsilon}\) was provided in the main body of the paper. **Theorem A15**. : _Every (truncated geometric, randomized response, exponential) mechanism is 'the safest possible mechanism' when parametrized by \(\varepsilon=0\).