This article presents an algorithm that generates an exact (conservative)
confidence interval of a specified length and coverage probability for the
power of a Monte Carlo test (such as a bootstrap or permutation test). It is
the first method that achieves this aim for almost any Monte Carlo test. The
existing research on power estimation for Monte Carlo tests has focused on
obtaining as accurate a result as possible for a fixed computational effort.
However, the methods proposed do not provide any guarantee of precision, in the
sense that they cannot report a confidence interval to accompany their estimate
of the power. Conversely in this article the computational effort is random.
The algorithm operates until a confidence interval can be constructed that
meets the requirements of the user, in terms of length and coverage
probability. We show that, surprisingly, by generating two more datasets that
what might have been assumed to be sufficient, the expected number of steps
required by the algorithm is finite in many cases of practical interest. These
include, for instance, any situation where the distribution of the p-value is
absolutely continuous or if it is discrete with finite support. The algorithm
is implemented in the R package simctest.