Douglas R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: In a matched two-sample statistical test, items in each given pair of n experimental units are randomly assigned to either the control or the treatment group. A randomization test can then be used to assess the efficacy of the treatment by computing the p-value of a certain test statistic. That is, we are interested in determining the probability, under the randomization assumption, of obtaining a value for the test statistic at least as extreme as that observed. Exact calculation of this tail probability theoretically involves looking at 2^n possible interchanges of data values between treatment and control groups. We view this problem in terms of a certain (distributive) lattice. An algorithm for generating relevant values of the test statistic is based on studying the Hasse diagram of this lattice. A rooted spanning tree of the Hasse diagram is then used to guide the generation algorithm, which produces values of the test statistic in monotone order. When the data are integer, a variant of Dijkstra's shortest path algorithm can be adapted to carry out the computations in a relatively efficient manner.

Key Words: algebraic structure, lattice, randomization, state generation, statistics