  We are concerned with a situation in which we would like to test multiple
hypotheses with tests whose p-values cannot be computed explicitly but can 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.
