# Refinement Orders for Quantitative Information Flow and Differential Privacy +
## Appendix D Proofs of Results about Refinement Comparison
 \tag{118}\]  
(Note that the constant co-efficient factorised out the front does not affect the \(\varepsilon\) calculation for the channel). This is exactly the randomized response mechanism required. **Lemma A5**. : _For any \(a\geq 1,b\geq 0\), the function_  
\[f(x)=\frac{ae^{x}+b}{e^{x}+a+b-1}\] (A29)  
_defined for \(x\geq 0\) is increasing and has range \([1,a)\)._  
Proof. : We can see that \(f(x)\) is continuous for the given domain and the derivative \(f^{\prime}(x)=\frac{e^{x}(a-1)(a+b)}{(e^{x}+a+b-1)^{2}}\) is \(\geq 0\) for all \(a\geq 1,b\geq 0\). Additionally, at \(x=0\), the function is defined and equal to \(1\). In addition,  
\[\lim_{x\to\infty}\frac{ae^{x}+b}{e^{x}+a+b-1} =\lim_{x\to\infty}\frac{ae^{x}}{e^{x}}\] (A30) \[=a\] (A31)  
**Lemma A6**. : _Let \(R^{\varepsilon}\), \(R^{\varepsilon^{\prime}}\) be randomized response mechanisms represented by square matrices (that is, \(\mathcal{X}=\mathcal{Y}\)). Then, \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\) iff \(\varepsilon\geq\varepsilon^{\prime}\)._  
Proof. : Note first that \(R^{\varepsilon}\), \(R^{\varepsilon^{\prime}}\) are in reduced (abstract channel) form and so the partial order of \(\sqsubseteq^{\mathrm{avg}}\) holds. From Lemma A4, we know that the composition of two randomized response mechanisms is another randomized response mechanism. Therefore, for the reverse direction, if \(\varepsilon>\varepsilon^{\prime}\) then Lemma A5 tells us that we can find a randomized response mechanism \(R^{\prime}\) such that \(R^{\varepsilon}R^{\prime}=R^{\varepsilon^{\prime}}\). In the case of equality, we can choose the identity mechanism. For the forward direct, we show the contrapositive. If \(\varepsilon<\varepsilon^{\prime}\), then we know there exists an \(R\) such that \(R^{\varepsilon^{\prime}}R=R^{\varepsilon}\). However, this means that \(R^{\varepsilon^{\prime}}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\). Since the matrices are reduced (as channels), then \(\sqsubseteq^{\mathrm{avg}}\) is a partial order and so this implies \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\). Thus, we must have \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\implies \varepsilon\geq\varepsilon^{\prime}\). Interestingly, we can use this result to show the second case where we consider 'over-truncated' mechanisms. **Lemma A7**. : _Let \(R^{\varepsilon}\), \(R^{\varepsilon^{\prime}}\) be randomized response mechanisms with \(\mathcal{Y}\subset\mathcal{X}\). Then, \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\) iff \(\varepsilon\geq\varepsilon^{\prime}\)._  
Proof. : Notice that this 'over-truncated' randomized response mechanism is just a square randomized response mechanism 'glued' onto a matrix containing all values \(\frac{1}{n+1}\). Denote the corresponding square mechanisms by \(S^{\varepsilon}\), \(S^{\varepsilon^{\prime}}\) (note the parameters are the same) and denote by \(N\) the matrix containing only \(\frac{1}{n+1}\) (note that this is the same matrix for both \(R^{\varepsilon}\) and \(R^{\varepsilon^{\prime}}\)). From Lemma A6, we can find a square randomized response mechanism \(R\) satisfying \(S^{\varepsilon}R=S^{\varepsilon^{\prime}}\) iff \(\varepsilon\geq\varepsilon^{\prime}\). Notice that \(R\) must be doubly symmetric, since its \(i\)th row is the same as its \(i\)th column. Thus, the dot product of any column of \(R\) with any row vector containing only \(\frac{1}{n+1}\) must yield \(\frac{1}{n+1}\). In addition, we must have \(N*R=N\). Now, we have that \(R^{\varepsilon}R\) is just \(S^{\varepsilon}R\) glued onto \(N\) which is the same as \(S^{\varepsilon^{\prime}}\) glued onto \(N\). In addition, thus \(R\) also satisfies \(R^{\varepsilon}R=R^{\varepsilon^{\prime}}\). In addition, following the same arguments as for Lemma A6, we have \(R^{\varepsilon}\sqsubseteq^{\mathrm{avg}}R^{\varepsilon^{\prime}}\) iff \(\varepsilon\geq\varepsilon^{\prime}\). Finally, we consider the case where \(\mathcal{X}\subset\mathcal{Y}\). **Lemma A8**.