Fisher's inequality

Ronald Fisher

Fisher's inequality, is a necessary condition for the existence of a balanced incomplete block design which satisfies certain prescribed conditions in combinatorial mathematics. Outlined by Ronald Fisher, a population geneticist and statistician, it concerns with the design of experiments studying the differences among several different varieties of plants, under each of a number of different growing conditions, called "blocks".

Let:

• v be the number of varieties of plants;
• b be the number of blocks.

It was required that:

• k different varieties are in each block, k < v; no variety occurs twice in any one block;
• any two varieties occur together in exactly λ blocks;
• each variety occurs in exactly r blocks.

Fisher's inequality states simply that

$b \ge v.\,$

Proof

Let the incidence matrix M be a v×b matrix defined so that M_i,j is 1 if element i is in block j and 0 otherwise. Then B = MM^T is a v×v matrix such that B_i,i = r and B_i,j = λ for i ≠ j. Since r ≠ λ, det(B) ≠ 0, so rank(B) = v; on the other hand, rank(B) = rank(M) ≤ b, so v ≤ b.

Generalization

Fisher's inequality is valid for more general classes of designs. A "pairwise balanced design" (or PBD) is a set X together with a family of subsets of X (which need not have the same size and may contain repeats) such that every pair of distinct elements of X is contained in exactly λ (a positive integer) subsets. The set X is allowed to be one of the subsets, and if all the subsets are copies of X, the PBD is called "trivial". The size of X is v and the number of subsets in the family (counted with multiplicity) is b.

Theorem: For any non-trivial PBD, v ≤ b.

This result also generalizes the Erdős–De Bruijn theorem:

For a PBD with λ = 1 having no blocks of size 1 or size v, v ≤ b, with equality if the PBD is a projective plane or a near-pencil (meaning that exactly n − 1 of the points are collinear).

In another direction, Ray-Chaudhuri and Wilson proved in 1975 that in a $2s-(v, k, \lambda)$ design, the number of blocks is at least $\binom{v}{s}$.

References

• R. C. Bose, "A Note on Fisher's Inequality for Balanced Incomplete Block Designs", Annals of Mathematical Statistics, 1949, pages 619–620.
• R. A. Fisher, "An examination of the different possible solutions of a problem in incomplete blocks", Annals of Eugenics, volume 10, 1940, pages 52–75.