## Appendix B Sort II Error Analysis
\[\overset{(b)}{\leq}\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j) \cap\mathcal{F}_{\delta_{\beta}}(i)\Big{)}+\Pr\Big{(}\mathcal{F}_{\delta_{ \beta}}^{c}(i)\Big{)} \tag{18}\]8 (A42)  
Observe that (A42) yield the following chain of expressions:  
\[\overset{(b)}{\leq}\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j) \cap\mathcal{F}_{\delta_{\beta}}(i)\Big{)}+\Pr\Big{(}\mathcal{F}_{\delta_{ \beta}}^{c}(i)\Big{)} \tag{18}\]9 (A43) \[\overset{(c)}{=}\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j)\cap \mathcal{F}_{\delta_{\beta}}(i)\Big{)}+\Pr\Big{(}d_{\text{H}}(\mathbf{Y}(i), \mathbf{c}_{i})>\Big{\lfloor}n\delta_{\beta}\Big{\rfloor}\Big{)}\]0 (A44) \[\overset{(c)}{=}\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j)\cap \mathcal{F}_{\delta_{\beta}}(i)\Big{)}+\Pr\Big{(}d_{\text{H}}(\mathbf{Y}(i), \mathbf{c}_{i})>\Big{\lfloor}n\delta_{\beta}\Big{\rfloor}\Big{)}\]1 (A45) \[\overset{(c)}{=}\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j)\cap \mathcal{F}_{\delta_{\beta}}(i)\Big{)}+\Pr\Big{(}d_{\text{H}}(\mathbf{Y}(i), \mathbf{c}_{i})>\Big{\lfloor}n\delta_{\beta}\Big{\rfloor}\Big{)}\]2 (A46) \[\overset{(c)}{=}\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j)\cap \mathcal{F}_{\delta_{\beta}}(i)\Big{)}+\Pr\Big{(}d_{\text{H}}(\mathbf{Y}(i), \mathbf{c}_{i})>\Big{\lfloor}n\delta_{\beta}\Big{\rfloor}\Big{)}\]3 (A47)  
which is trivial, since it is already proved in (A32). Now, observe that for \(0<\frac{k}{n-d}<\tau<\varepsilon\), the following holds  
\[\overset{(c)}{=}\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j)\cap \mathcal{F}_{\delta_{\beta}}(i)\Big{)}+\Pr\Big{(}d_{\text{H}}(\mathbf{Y}(i), \mathbf{c}_{i})>\Big{\lfloor}n\delta_{\beta}\Big{\rfloor}\Big{)}\]4 (A48)  
see \[\overset{(c)}{=}\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j)\cap \mathcal{F}_{\delta_{\beta}}(i)\Big{)}+\Pr\Big{(}d_{\text{H}}(\mathbf{Y}(i), \mathbf{c}_{i})>\Big{\lfloor}n\delta_{\beta}\Big{\rfloor}\Big{)}\]5 Therefore, since \(\tau\) always yield a smaller exponent, we obtain an upper bound on the sum in (A41) as follows  
\[ \begin{split}\sum_{p_{2}=0}^{\lfloor n\delta_{\delta}\rfloor-d+ \lfloor d/2\rfloor}\binom{n-d}{p_{2}}e^{p_{2}}(1-\varepsilon)^{n-d-p_{2}}& \leq\frac{\varepsilon((n-d)-k)}{\varepsilon(n-d)-k}\cdot 2^{n\big{[}H( \frac{k}{n-d})-T_{\varepsilon}(\frac{k}{n-d})\big{]}}\\ &\stackrel{{(a)}}{{<}}\frac{\varepsilon(1-\tau)}{ \varepsilon-\tau}\cdot 2^{n\big{[}H(\frac{k}{n-d})-T_{\varepsilon}(\frac{k}{n-d})\big{]}} {\varepsilon-\frac{k}{n-d}}\cdot 2^{n\big{[}H(\tau)-T_{\varepsilon}(\tau)\big{]}} \\ &\triangleq\zeta_{0,n},\end{split} \] (A49)  
where \((a)\) exploits (A42), and \((b)\) follows by (A48). Thereby, recalling (A28) and employing (A29), we obtain  
\[\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j)\cap\mathcal{F}_{\delta_{\beta}}(i) \Big{)}\leq 1\cdot\sum_{j=0}^{k}\binom{n-d}{j}\varepsilon^{j}(1-\varepsilon)^{ n-d-j}<\frac{\varepsilon(1-\tau)}{\varepsilon-\tau}\cdot 2^{n\big{[}H(\tau)-T_{ \varepsilon}(\tau)\big{]}}\triangleq\zeta_{0,n}.\] (A50)  
Hence, recalling (A15) and (A18), we obtain  
\[ \begin{split}& P_{e,2}(i,K)\\ &\leq K\cdot\left[\Pr\bigg{(}d_{\mathrm{H}}(\mathbf{Y}(i), \mathbf{c}_{j})\leq\Big{\lfloor}n\delta_{\beta}\Big{\rfloor}\bigg{)}\right] \\ &\leq K\cdot\left[\Pr\Big{(}\mathcal{F}_{\delta_{\beta}}(i,j)\cap \mathcal{F}_{\delta_{\beta}}(i)\Big{)}+\zeta_{1,n}\right]\end{split}