We are concerned with multiple testing in the setting where p-values are
unknown and can only be approximated using Monte Carlo simulation. This
scenario occurs widely in practice. We are interested in obtaining the same
rejections and non-rejections as the ones obtained if the p-values for all
hypotheses had been available. The present article introduces a framework for
this scenario by providing a generic algorithm for a general multiple testing
procedure. We establish conditions which guarantee that the rejections and
non-rejections obtained through Monte Carlo simulations are identical to the
ones obtained with the p-values. Our framework is applicable to a general class
of step-up and step-down procedures which includes many established multiple
testing corrections such as the ones of Bonferroni, Holm, Sidak, Hochberg or
Benjamini-Hochberg. Moreover, we show how to use our framework to improve
algorithms available in the literature in such a way as to yield theoretical
guarantees on their results. These modifications can easily be implemented in
practice and lead to a particular way of reporting multiple testing results as
three sets together with an error bound on their correctness, demonstrated
exemplarily using a real biological dataset.