# Algorithm Providing Ordered Integer Sequences for Sampling with Replacement Confidence Intervals
## 3 Balanced CI with Ordered Integer Sequences  
The way in which a confidence interval for a discrete distribution is constructed should be changed. In the case of a binomial distribution, a mathematical formula is not able to encompass the complexity of the issue. Three algorithms have been proposed in [11].  
Here, one solution is given, balancing between the imposed and actual level of residual error.  
To fix the terminology, \(\alpha\) is the imposed level, \(x\) is the number of successes, \(m\) is the number of trials, \([i,j]\) is the confidence interval, and \(q\) is its actual coverage.  
Algorithm 1 systematically keeps the error closest to the imposed level. There is a symmetry in the confidence intervals provided by the algorithm. For each significance level \(\alpha\) and sample size \(m\), the solution provided by running Algorithm 1 is a series of numbers, \(N_{0}\),..., \(N_{m}\). The CI of a pair of data \((x,m)\) for \(\alpha\) is \([N_{x},m-N_{m-x}]\), where \(x=0,1,\ldots,m\). Some \(N_{x}\) series are listed in the Appendix A for convenience.  
The \(N_{x}\) series provided by Algorithm 1 are monotonic. The actual coverage probability series are symmetric. Any of the series defined by \(\{i:(i,j,q)\leftarrow\texttt{BalancedCI}(x,m,\alpha),0\leq x\leq m\}\) and by \(\{j:(i,j,q)\leftarrow\texttt{BalancedCI}(x,m,\alpha),0\leq x\leq m\}\) provide the same but in the reversed order, and this is the beauty of the proposed solution.  
The values of the numbers constructing CIs with \([N_{x},30-N_{30-x}]\) are given in Appendix A at \(m=30\) entry and designated as \(N_{0}\),..., \(N_{30}\). The plot of Algorithm 1 CI non-coverage probabilities is given in Figure 1.  
```
Input:\(x,m,\alpha\) / \(z,m\in\mathbb{N},2\leq x,m\); \(\alpha\in\mathbb{R},0<\alpha<1\) for\(y\leftarrow\overline{1,n}\)do \(r_{y}\gets f_{\text{R}n}(y;x,m)\) end \(\beta\gets 1-\alpha;i\gets x;j\gets x;q\gets r_{x}\) while\(I\)do if\(j\leq i\)then Break end if\(r_{i}=r_{j}\)then if\(|\beta-q|>|\beta-q+r_{i}+r_{j}|\)then\(q\gets q-r_{i}-r_{j}i\gets i+1;j\gets j-1\) end  Break Break
```  
**Algorithm 1**BalancedCI  
The actual non-coverage of CIs provided by Algorithm 1 is not monotone (it alternates, on average, around the imposed level) but symmetric and convergent to it. With data in Appendix A, Table 2 statistics  
In terms of computational complexity, Algorithm 1 for given \(\alpha\), \(m\), and \(x\) requires a number of steps to arrive from \(x\) (\(i\gets x\) and \(j\gets x\) in Algorithm 1) to \(N_{x}\) and \(N_{m-x}\) (see the series of \(N_{x}\) for \(m=30\), \(45\), \(100\), and \(900\) in Appendix A). The solution is nearby. In fact, Equation (2) is an estimate of the asymptotic interval. Computational time is then proportional to \(2z_{\alpha}\sqrt{x(m-x)/m}\). The shortest computational time is for \(x=0\) and \(x=m\) (near 0; only evaluation of the \(f_{RB}\) function time since \(N_{0}=0\) and \(N_{m}=m\) always), while the longest is for \(x\) near \(\frac{m}{2}\) (where \(\sqrt{m}\) evaluations are needed). Thus, Algorithm 1 complexity is \(\mathcal{O}(\sqrt{m})\). The algorithm speed can be increased too if an approximate solution is provided before the While loop. Algorithm 1 from [11] or \(\max(W_{L},0)\), \(\lfloor\min(W_{L},m)\rfloor\) with Equation (2) can be used for this task.