The Monte Carlo Test Technique
An Exact Randomized Test Procedure
If there were a machine that could check 10 permutations a second, the job would run something on the order of 1,000 years. The point is, then, that an impossible test can be made possible, if not always practical.
The Monte Carlo (MC) test procedure was first proposed by Dwass (1957) in the following context. Consider two independent samples X1,…, Xm and Y1,…, Yn, where X1,…, Xm ~ F(x), Y1,…, Yn ~ F(x – 5) and the cdf F(-) is continuous. No further distributional assumptions are imposed. To test H0 : 5 = 0, the following procedure may be applied. •
• Let r denote the number of s(j)s for which s < s(j). Reject the null (e. g. against HA : 5 > 0) if r < k, where k is a predetermined integer.
It is easy to see that P(r < k) = k/Q under the null because the Xs and the Ys are exchangeable. In other words, the test just described is exactly of size k/Q.
The procedure is intuitively appealing, yet there are (n + m)! permutations to examine. To circumvent this problem, Dwass (1957) proposed to apply the same principle to a sample of P permutations s(1),…, s(P), in a way that will preserve the size of the test. The modified test may be applied as follows.
• Let > denote the number of s(j)s for which s < s(j). Reject the null (against 5 > 0) if r < d, where d is chosen such that
d + 1 _ k_
P + 1 _ Q ‘
Dwass formally shows that with this choice for d, the size of the modified test is exactly k/Q = the size of the test based on all permutations. This means that, if we wish to get a 5 percent-level permutation test, and 99 random permutations can be generated, then d + 1 should be set to 5. The latter decision rule may be restated as follows: reject the null if the rank of s in the series s, s(1),…, s(P) is less than or equal to 5. Since each s(j) is "weighted" by the probability that it is sampled from all possible permutations, the modification due to Dwass yields a randomized test procedure.
The principles underlying the MC test procedure are highly related to the randomized permutation test just described. Indeed, this technique is based on the above test strategy where the sample of permutations is replaced by simulated samples. Note that Barnard (1963) later proposed a similar idea.4