2 - Combinatorics of optimal designs

Summary

Abstract

To a combinatorialist, a design is usually a 2-design or balanced incomplete-block design. However, 2-designs do not necessarily exist in all cases where a statistician might wish to use one to design an experiment. As a result, statisticians need to consider structures much more general than the combinatorialist's designs, and to decide which one is “best” in a given situation. This leads to the theory of optimal designs. There are several concepts of optimality, and no general consensus about which one to use in any particular situation.

For block designs with fixed block size k, all these optimality criteria are determined by a graph, the concurrence graph of the design, and more specifically, by the eigenvalues of the Laplacian matrix of the graph. It turns out that the optimality criteria most used by statisticians correspond to properties of this graph which are interesting in other contexts: D-optimality involves maximizing the number of spanning trees; A-optimality involves minimizing the sum of resistances between all pairs of terminals (when the graph is regarded as an electrical circuit, with each edge being a one-ohm resistor); and E-optimality involves maximizing the smallest eigenvalue of the Laplacian (the corresponding graphs are likely to have good expansion and random walk properties). If you are familiar with these properties, you may expect that related “nice” properties such as regularity and large girth (or even symmetry) may tend to hold; some of our examples may come as a surprise!