Verifying rejection rate of a statistical test I want to check whether a statistical test truly rejects at the specified significance level of $\alpha=0.05$ under the null hypothesis. I'm going to verify this result using simulations with a $0.5\%$ margin of error. What hypothesis would be appropriate for an exact test (non-asymptotic)? And exactly how many simulations do I need for the desired accuracy?
 A: If you do $N$ simulations of a test, with probability of rejection $q$, the number of rejections will be binomial$(N,q)$.
When checking this against the hypothesis that the true rejection rate is $\alpha$, that would simply be a matter of taking $q=\alpha$.
Your margin of error is pretty large, but let's go with that (you don't state what confidence level you want that margin to correspond to though). 
The number N should be easily large enough that one can reasonably employ asymptotics. 
If you have a margin of error of $0.5\%$ and if we assume that's a 95% interval, for an $\alpha=5\%$ test the asymptotic approximation would give an N of at least 7300. (10000 is a common sample size to use and gives just a little under that margin. I tend to look for considerably smaller margins and so I often tend to use $10^5$ to $10^6$ simulations if it's not too slow -- sometimes $10^7$ or more)
If we try to use the binomial we run into problems -- qbinom in R, for example, won't do the calculations. We can do them on the log scale in R directly from the pmf using lchoose and then exponentiate and add*, and this suggests that for that asymptotic interval there's about 0.0236 in the left tail and about 0.0263 in the right tail (giving almost exactly a 5% test); alternatively you can shift up by 1 and (roughly) swap the proportions in each tail). If you want no more than 2.5% in each tail, you're stuck with a 4.7% test; alternatively you could alter N a little from there depending on which properties you want to compromise on, but it won't change the discreteness of the binomial, so you'll have to compromise on something.
* an alternative approach would be to use the relationship between the regularized incomplete beta function and the binomial cdf.
