  Estimating the probability of the binomial distribution is a basic problem,
which appears in almost all introductory statistics courses and is performed
frequently in various studies. In some cases, the parameter of interest is a
difference between two probabilities, and the current work studies the
construction of confidence intervals for this parameter when the sample size is
small. Our goal is to find the shortest confidence intervals under the
constraint of coverage probability being larger than a predetermined level. For
the two-sample case, there is no known algorithm that achieves this goal, but
different heuristics procedures have been suggested, and the present work aims
at finding optimal confidence intervals. In the one-sample case, there is a
known algorithm that finds optimal confidence intervals presented by Blyth and
Still (1983). It is based on solving small and local optimization problems and
then using an inversion step to find the global optimum solution. We show that
this approach fails in the two-sample case and therefore, in order to find
optimal confidence intervals, one needs to solve a global optimization problem,
rather than small and local ones, which is computationally much harder. We
present and discuss the suitable global optimization problem. Using the Gurobi
package we find near-optimal solutions when the sample sizes are smaller than
15, and we compare these solutions to some existing methods, both approximate
and exact. We find that the improvement in terms of lengths with respect to the
best competitor varies between 1.5\% and 5\% for different parameters of the
problem. Therefore, we recommend the use of the new confidence intervals when
both sample sizes are smaller than 15. Tables of the confidence intervals are
given in the Excel file in this link.
