III.14 Designs
Peter J. Cameron
Block designs were first used in the design of experiments in statistics, as a method for coping with systematic differences in the experimental material. Suppose, for example, that we want to test seven different varieties of seed in an agricultural experiment, and that we have twenty-one plots of land available for the experiment. If the plots can be regarded as identical, then the best strategy is clearly to plant three plots with each variety. Suppose, however, that the available plots are on seven farms in different regions, with three plots on each farm. If we simply plant one variety on each farm, we lose information, because we cannot distinguish systematic differences between regions from differences in the seed varieties. It is better to follow a scheme like this: plant varieties 1, 2, 3 on the first farm; 1, 4, 5 on the second; and then 1, 6, 7; 2, 4, 6; 2, 5, 7; 3, 4, 7; and 3, 5, 6. This design is represented in figure 1.
This arrangement is called a balanced incomplete-block design, or BIBD for short. The blocks are the sets of seed varieties used on the seven farms. The blocks are “incomplete” because not every variety can be planted on every farm; the design is “balanced” because each pair of varieties occurs in the same block the same number of times (just once in this case). This is a (7, 3, 1) design: there are seven varieties; each block contains three of them; and two varieties occur together in a block once. It is also an example of a finite projective plane. Because of the connection with geometry, varieties are usually called “points.”
Mathematicians have developed an extensive theory of BIBDs and related classes of designs. Indeed, the study of such designs predates their use in statistics. In 1847, T. P. Kirkman showed that a (v, 3, 1) design exists if and only if v is congruent to 1 or 3 mod 6. (Such designs are now called Steiner triple systems, although Steiner did not pose the problem of their existence until 1853.)
Kirkman also posed a more difficult problem. In his own words,
Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast.
The solution requires a (15, 3, 1) Steiner triple system with the extra property that the thirty-five blocks can be partitioned into seven sets called “replicates,” each replicate consisting of five blocks that partition the set of points. Kirkman himself gave a solution, but it was not until the late 1960s that Ray-Chaudhuri and Wilson showed that (v, 3, 1) designs with this property exist whenever v is congruent to 3 mod 6.
For which v, k, λ do designs exist? Counting arguments show that, given k and λ, the values of v for which (v, k, λ) designs exist are restricted to certain congruence classes. (We noted above that (v, 3, 1) designs exist only if v is congruent to 1 or 3 mod 6.) An asymptotic existence theory developed by Richard Wilson shows that this necessary condition is sufficient for the existence of a design, apart from finitely many exceptions, for each value of k and λ.
The concept of design has been further generalized: a t–(v, k, λ) design has the property that any t points are contained in exactly λ blocks. Luc Teirlinck showed that nontrivial t-designs exist for all t, but examples for t > 3 are comparatively rare.
The statisticians concerns are a bit different. In our introductory example, if only six farms were available, we could not use a BIBD for the experiment, but would have to choose the most “efficient” possible design (allowing the most information to be obtained from the experimental results). A BIBD is most efficient if it exists; but not much is known in other cases.
There are other types of design; these can be important to statistics and also lead to new mathematics. Here, for example, is an orthogonal array: if you take any two rows of this matrix you obtain a 2 × 9 matrix in which each ordered pair of symbols from {0, 1, 2} occurs exactly once as a column.
It could be used if we had four different treatments, each of which could be applied at three different levels, and if we had nine plots available for testing.
Design theory is closely related to other combinatorial topics such as error-correcting codes; indeed, Fisher “discovered” the Hamming codes as designs five years before R. W. Hamming found them in the context of error correction. Other related subjects include packing and covering problems, and especially finite geometry, where many finite versions of classical geometries can be regarded as designs.